1

There is a simple game with coins that goes as follows.

You have $x$ coins and two players who take turns. Each player can either remove one or two coins. The winner is the person who removes the last coin(s).

A little experimentation will show that the first player always wins unless $x$ is a multiple of $3$. You can convince yourself this is true by solving for $x=1,2,3$ and then noticing that you can win if and only if at least one of $x-1$ and $x-2$ coins is a loss for the first player.

This explanation isn't quite as elegant as I was hoping however. Is there nicer or more elegant explanation for the fact that you can always win unless $x$ is a multiple of $3$?

  • 2
    What's wrong with that explanation? If it's my turn and I see $N$ coins, where $N$ is not a multiple of $3$ then I take out one or two, whichever leaves you with a multiple of $3$. You can't win from there nor can you leave me with a multiple of $3$ (as neither $1,2$ are multiples of three) Sooner or later I'll leave you with $3$ exactly and I'll win on the next round. – lulu Jun 12 '16 at 20:23
  • @lulu A fully rigorous proof by induction would be nice but is this the only way to prove it? –  Jun 12 '16 at 20:25
  • 2
    Easy to turn my comment into a proof by induction. You can also deduce the result from the general theory of Nim-like games. In that article the game you want is called "the subtraction game". People also call it "poison". – lulu Jun 12 '16 at 20:28
  • 1
    @Lembik I'm curious to know what you think is inelegant about this approach: it fits into one line, how much nicer do you expect it to be? In general, the winning strategy is not something that can be immediately perceived from the rules of the game. In the classical Nim game, it's certainly not obvious (without the development of Sprague-Grundy theory) that binary representation should play an essential role in the solution. – Erick Wong Jun 12 '16 at 23:11
  • @ErickWong I was looking for something that was either more rigorous, more direct or which proved that this was the only winning strategy. Basically something that tells you something more about the problem. –  Jun 13 '16 at 08:20

2 Answers2

1

He who starts with a multiple of three loses because his opponent can maintain this property until the end. He who starts with a non multiple of three wins by leaving the opponent with a multiple of three.

$\color{blue}9\to8|7\to\color{blue}6\to5|4\to\color{blue}3\to2|1\to\color{blue}0$

$\color{blue}{10}\to9\to\color{blue}{8|7}\to6\to\color{blue}{5|4}\to3\to\color{blue}{2|1}\to0$

$\color{blue}{11}\to9\to\color{blue}{8|7}\to6\to\color{blue}{5|4}\to3\to\color{blue}{2|1}\to0$

0

The key to this game is modular arithmetic. It is essentially the same game if it has $0,3,6,...,$ or $3k$ coins, $1,4,...,$ or $3k+1$ coins, and $2,5, ... ,$ or $3k+2$ coins.

The optimal strategy is to always keep the number of coins $n$ on the table such that $n\equiv 0\pmod 3.$ This guarantees that when there are only $3$ coins left, it is the other player's turn. Then they will have to pick up either one or two coins, making the final player the winner.

If both players play optimally, and the game starts with $3m$ coins for some positive integer $m$, then the first player cannot keep the number of coins congruent to $0\pmod 3,$ as they must take one or two coins. This then enables the second player to keep the number of coins congruent to $0\pmod 3,$ and thus winning.

Only when the game starts with $n$ coins where $n\equiv 1\pmod 3$ or $n\equiv 2 \pmod 3$ can the first player force the number of coin on the table to always be congruent to $0\pmod 3$, and so only then can the first player force a win.

M47145
  • 4,106
  • This explanation tells you how to win but it's a little unclear to me how it proves this is the only winning strategy. –  Jun 13 '16 at 08:19
  • 1
    I didn't show that it is the only winning strategy. By optimal strategy, I mean that it guarantees that you win if you can use it. If there are $3k$ coins on the table, you cannot use it, and your opponent can, and so you lose. Only when there are $3k+1$ or $3k+2$ coins in the beginning, can the first player use the winning strategy and thereby win. – M47145 Jun 13 '16 at 17:40