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 both players try to extend the game as long as possible, the person who makes the first move wins.  There are 8 (2^3), or generally 2^n possible configurations for the coins.  If the players so choose, they can all be  visited in sequence, for instance in the fashion of the Gray Codes (http://en.wikipedia.org/wiki/Gray_code).  Discounting the initial configuration, an odd number of configurations remains, and the same player makes the last allowed move as the first.

But what if one of the players cuts the game short by some skilful move?  To see what happens then, imagine the game as an n-dimensional hypercube.  Each of its corners represents a configuration of the coins, with each of the n-dimensional coordinates associated with one coin and the hypercube aligned with the axes.  Each move transforms the configuration at one corner to the configuration at a different corner linked to it by an edge.  In this picture one can see (certainly for 3 dimensions, a bit less easily for more coins) that every loop contains an even number of edges.  So it takes an even number of moves to recreate the same configuration, and again the player who starts wins.

A different (perhaps easier) way to see this is to define the parity of a configuration to be 1 if an odd number of coins shows heads and -1 otherwise.  Every move changes the parity, so again returning to the same configuration takes an even number of moves.

If the player who can't move is the winner, the one who does not open the game wins.

As Steve points out later, this is only correct if the losing (for 3: winning) player returns to the starting configuration, not to some other configuration.

Edited on September 15, 2006, 3:02 pm

Posted by vswitchs on 2006-09-13 13:13:42