Imagine a game in which you have the integers from 1 to 12 written on slips of paper. You roll 2 dice and take their sum. You can then flip over any combination of pieces of paper with a sum equal to the sum of the dice. (For example, if you roll a 5 and a 2, you could flip over the 7; the 6 and 1; the 5 and 2; the 4 and 3; or the 4, 2, and 1.) Once a piece of paper is flipped over, you cannot use that number anymore. You win if you flip over all 12 pieces of paper.
Two questions:
What is the best strategy? (I believe you should always avoid flipping small numbers and try to flip the single number equal to the sum you rolled, if possible. I base this on the fact that if you roll a 12, you’d be foolish to flip anything other than the 12, and so on.)
Is there an easy way to calculate the probability of winning the game? (This seems to me to be a situation with way too many branches to really evaluate, but maybe there’s some trick to think about it from the right perspective.)
For clarity: you lose if you cannot flip over pieces of paper with a sum equal to the sum of your dice (i.e., if you roll a 2 and the 2 is already flipped over.)
There actually isn’t all that much in the way of branching: there are only 2^12=4096 possible board states. Easily within range of a computer or even dedicated human.
You start with the win case–all slips flipped–and work backwards. Each board with just one remaining slip has odds of winning of rolling that number (1/36 for a 12, etc.). With two slips remaining, I can either roll one number or the other to reduce it to a one-slip case, or roll their sum to win immediately. For instance, with a [2 3] set remaining:
[2 3] + roll 2 (1/36) => [3] roll 3 (2/36) => (win, 1/648)
[2 3] + roll 3 (2/36) => [2] roll 2 (1/36) => (win, 1/648)
[2 3] + roll 5 (4/36) => (win, 1/9)
The odds sum to 37/324.
Maybe there’s some less brute-force way to do this, but in any case it would take a computer a fraction of a second to compute back to the start case.
BTW, once you compute the probability of winning for each board, the correct strategy is to make the move that leaves you with the best one.
It does seem like you’re always better off flipping the highest numbers you can. Extending my earlier example, suppose you have a [2 3 5] and roll a 5. You’re better off flipping the 5 right then, since with the [2 3] you get the odds of both another 5 and the odds of getting the 2 and 3 individually, whereas with a [5] you must roll another 5 (a small difference, but not zero).
Oh, right! I do remember that. Well, this page pretty much lays out the optimal strategy for every situation and says the probability of winning is 36%.