A and B are going to play a game: two pots are filled with stones, one with 57 stones and the other with 62 stones.

A legal move consists of emptying a pot - throwing away all the stones it contains - and splitting the stones of the other pot among the two pots, so that each pot contains at least one stone.

Players A and B alternate their moves, and player A is the first to make a move.

If a player is unable to make a legal move, then he loses.

Who wins this game and what is his optimal play strategy?

let the state of the game at the begining of each turn be (x,y) with x and y the number of stones in each pot and with x<=y.

Now at any of A's turns if it is given the state (x,y) it then gives B the state (1,y-1).  Now to show how this always ends with a win for A.

The only losing state is when a player gets (1,1) because regardless of which pot they empty they only have 1 stone left to split between 2 pots and thus are unable continue and thus lose.  So for A to win A wants to Give B the state (1,1) at some point,  Now in order to be able to do this at some point A must get a state of (2,x) for some x.  So B does not want to ever give A a state of (2,x) or else he is forcing his own loss.  So if B is playing optimally then A will always have a state of (x,y) with x>2 and x<=y and so y>=3 so by A always giving B (1,y-1) from (x,y) then it will eventually degenerate down to a state where B is forced to give A the winning move.  Thus A always wins by going from (x,y) to (1,y-1) until it has a position of (2,x) and then it gives B the end position of (1,1).

I'm sure there are some holes in my proof but I am fairly confident that this is the optimal strategy.

Posted by Daniel on 2009-02-21 18:43:08