5
$\begingroup$

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).

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Wow. I did the same plot and all the same about golden ratio. But can the strategy be described simply as f(n, m)? $\endgroup$
    – Serge Seredenko
    Mar 31, 2016 at 18:01
  • $\begingroup$ @Serge: Did you read the Wikipedia article? It describes the strategy. $\endgroup$
    – joriki
    Mar 31, 2016 at 18:01
  • $\begingroup$ I did, but the strategy there involves computation of all winning cells above current position. I wonder if there's a simpler way. Anyway, this is the answer to my question. $\endgroup$
    – Serge Seredenko
    Mar 31, 2016 at 18:09
  • 2
    $\begingroup$ @SergeSeredenko: You don't have to compute all winning positions -- you can intersect the three lines that represent the available strategies with the lines $m=\phi n$ and $n=\phi m$, and then you only need $O(1)$ operations to find the winning positions near the intersections. $\endgroup$
    – joriki
    Mar 31, 2016 at 18:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .