Game: two pots with coins

455 Views Asked by At

Rules of the game with two players.

First player puts any number of coins in the first pot. Then second player, knowing that number, puts any amount of coins in the second pot.

Then they in turns (beginning with the first player) do one of these things: take any amount of coins from one pot OR take equal amount from both pots. Whoever cannot take a coin loses. Players always know how many coins there are in the pots.

Who wins and what is the perfect strategy?

I managed to solve it, but the solution is very complicated and is based on fact which I just randomly guessed, but cannot deduct without the full solution. So I am looking for a nice approach to this problem.

The easy part is determining that player two wins: if there is a smallest winning initial donation by the first player, then the first move of player one cannot be taking just from the second pot, and this fact leads to infinite count of winning positions for player two for bounded number in the first pot, which is impossible (since there cannot be two winning positions for player two with the same amount of coins in the first pot).

1

There are 1 best solutions below

4
On BEST ANSWER

The game they play after the coin numbers are chosen is known as Wythoff's game. Here's a plot of the losing positions (from the Wikipedia article):

enter image description here

The two lines are complementary Beatty sequences, which implies that for every number chosen by the first player, the second player can choose a number such that the resulting position is a losing position for the first player.