A Game with the Devil
My former student, Dai Yang, sent me the following cute puzzle:
Share:Puzzle. You are playing a game with the Devil. There are n coins in a line, each showing either H (heads) or T (tails). Whenever the rightmost coin is H, you decide its new orientation and move it to the leftmost position. Whenever the rightmost coin is T, the Devil decides its new orientation and moves it to the leftmost position. This process repeats until all coins face the same way, at which point you win. What’s the winning strategy?
Andrew:
Incomplete thoughts: heads are opportunities for you to decide, and tails are opportunities for the devil to decide, but you can never increase the number of heads, and the devil can never increase the number of tails, so it seems like you should win by achieving all tails. If all of the heads (however few or many they may be) were contiguous, then you could win by flipping all — but I don’t see how you force a win.
21 March 2020, 9:56 pmlvps1000vm:
Assign the coins in playing order the value 1, 2, 4, 8, 16, 32, etc. From now on, the coins keep their value even if moved to the left. Whenever coin 1 is played we say that a new round has started.
Call “the Devil’s value” the sum of the values of coins in position T.
When a new round starts, keep on switching H coins to T, until the Devil switches a T to H. Then make H remain H until the end of the round.
If the Devil didn’t switch, all coins are now T and you win.
If the Devil did switch, the value of his switched coins is greater than the value of your switched coins, so the Devil’s value decreased. Keep this strategy round after round until the Devil’s value reaches zero.
23 March 2020, 1:32 am