Alex and Bert are going to play a variation of Two players, two pots
. This time there are three pots and the pots start with 58, 62, and 68 stones.
A legal move consists choosing two of the pots and of emptying one of them and then splitting the stones from the second chosen pots among the two pots so that each pot contains at least one stone. The third pot is untouched.
Alex and Bert alternate their moves and Alex 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 the general situation, say we have a, b and c stones in the pots and let's call this game state (a,b,c). Obviously (1,1,1) is losing, as there is no move left.
Now assume a game state where there is at least one odd and at least one even number of stones. (Call it (e,o,o) or (e,e,o)). From there, we can create a situation where there are only odd numbers left everywhere. How? Just leave the pot with the odd number untouched, empty one pot and distribute the even number of stones into two uneven partitions.
On the other hand, if there is a game state (o,o,o) with only odd numbers, you cannot avoid a (e,o,o) or a (e,e,o) game state for your opponent. Since (1,1,1) is of the (o,o,o)-type and losing, this shows that all game states of the form (o,o,o) are losing and all with (e,e,o) or (e,o,o) are winning.
So what if the game state is (g,g,g), i.e. an even number of stones everywhere? Here we use divisibility by 4 (versus 2) and the same arguments works. I.e. when no number is divisible by 4, you lose, when there is one number divisible and one isn't, you win. This does not say, what happens when all numbers are divisible by 4 , but luckily the initial game state is such that 68 can be divided by 4 whereas 58 and 62 cannot, so we are done.
Alex is winning and a good next move would be (58,62,68) => (58,34,34)
In the general situation, we'd have to also consider divisibility by 8, 16, 32...
Edited on January 4, 2020, 12:45 pm
Edited on January 4, 2020, 12:46 pm
Posted by JLo
on 2020-01-04 12:44:53