Andrew and Betty play a game in which they lay out a row of three coins, heads up. They take turns, begining with Andrew, turning over one of the coins at a time. They must not produce a pattern of heads and tails which has already occurred earlier in the game. The first person who cannot make a move is the loser.

1. If they each play as well as possible, who is the winner?

2. If the game were played with four coins instead of three, who would be the winner?

3. If the game is played with three coins but the player who cannot make a move is declared the winner, who wins now?

If the player who makes the last move is declared the winner, there is a simple winning strategy for player 1 for any number of coins: The first play just keeps flipping the same coin until he wins. Here is why this works: Let's say we have n coins, then write the initial coin configuration as

b_1 0

where b_1 is simply an abreviation for 0 ... 0 n-1 times. Now the game goes like this:

b_1 0
b_1 1
b_2 1
b_2 0
b_3 1
b_3 0
....
....

Obviously player 2 can never flip the coin that player 1 flips. Instead player 1 needs to come up with new configurations b_1, b_2, b_3 etc. for the other n-1 coins. Because these are NEW configurations for the n-1 coins, player 1 can conveniently flip back coin number 1 each time without visiting the same configuration again. When player 2 runs out of b_i's, player 1 has won.

Posted by JLo on 2006-09-14 18:05:53