Nice explanation for simple puzzle

871 Views Asked by At

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

There are 2 best solutions below

2
On BEST ANSWER

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.

0
On

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$