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?
(In reply to
almost complete solution by Daniel)
You can't give your opponent a 1-6 combination, though ... he'll give you a 3-3 and you're in trouble.
Drawing out the results for small values of x and y, a pattern becomes clear fast. Winning situations (what you get from your opponent) are those with at least one even number, losing positions have x and y both odd. Given the initial values, A wins if both players play optimally.
Proof:
If you get an even number (2x,y), give your opponent (1,x-1) or any other combination of two odd numbers.
If you get two odd numbers, you can only give your opponent a combination of an odd and an even number, unless you get (1,1) where you immediately lose. If the opponent plays according to this strategy, you get two odd numbers back. The sum of the two numbers will always decrease, so eventually the dreaded (1,1) must be reached.
An example for the setting as stated in the problem:
A gets (57,62) and gives (31,31) to B.
B gives (15,16) to A. A gives (3,13) to B. B gives (10,3) to A. A gives (5,5) to B. B gives (3,2) to A. A gives (1,1) to B and wins the game.
re: almost complete solution
