5
$\begingroup$

I have a challenge: to win the game with the following rules:

  1. There are exactly two players and their turns alternate;
  2. At each turn, a player removes 1, 2, 3 or 4 counters from a pile that was initially 27 counters;
  3. The games ends when all counters have been removed;
  4. The player having an even number of counters when all the counters have been taken wins.

Who wins? What is the strategy for winning?

$\endgroup$
3
  • $\begingroup$ Maybe instead of 27 counters, you should work out what happens with 5, 7, 9, etc., counters, and see whether there's a pattern. $\endgroup$ – Gerry Myerson Mar 29 '14 at 12:04
  • $\begingroup$ (i) If there are 6 counters, the first player removes 1 counter (odd number) leaving 5. In this case, the first player wins, no matter how the second play; (ii) If there are 8 counters, the first player removes 2 counters (an even number), leaving 6. In this case, the first player wins, it doesn't matter as the second player to play. I observed that: (a) if the first player has a even number of counters when there are only 6, the first one always wins. (b) if the first player has an odd number of counters and 5 remain, the first always wins. How to control the initial moves? $\endgroup$ – benedito Mar 29 '14 at 12:29
  • $\begingroup$ I'm not sure the game makes sense with 6 counters, as either both players get an even number of counters, or neither player does. With an odd number of counters, you always get a winner and a loser; with an even number of counters, never. $\endgroup$ – Gerry Myerson Mar 29 '14 at 22:27
4
$\begingroup$

Describe the position of the game at any point by the pair $(n,o)$, meaning that there are $n$ counters left and the player whose turn it is to move has an odd number of counters, or $(n,e)$, meaning that there are $n$ counters left and the player whose turn it is to move has an even number of counters. We say a position is a winning position if the player whose turn it is to move can force a win no matter what his opponent does.

  • $(1,o)$ is a winning position because the player to move takes the last counter and ends with an even number.
  • $(1,e)$ is a losing position because the player to move is forced to take the last counter and ends with an odd number.
  • $(2,o)$ is a winning position because taking one counter puts the opponent into position $(1,e)$ and he must then lose.
  • $(2,e)$ is a winning position because the player to move can take both counters and finish with an even number.
  • For similar reasons, $(3,o)$ and $(3,e)$ and $(4,o)$ and $(4,e)$ are all winning positions. For example, in position $(3,e)$ the opponent has an even number of counters, taking two counters puts him into position $(1,e)$ and, as above, he must then lose. Now it gets a bit more interesting.
  • $(5,o)$ is a losing position as the opponent has an odd number of counters, so any move will leave him in one of the winning positions $(4,o)$ or $(3,o)$ or $(2,o)$ or $(1,o)$.
  • $(5,e)$ is a winning position because taking $4$ counters puts the opponent in the losing position $(1,e)$.
  • $(6,o)$ is a losing position because the opponent has an even number of counters, so any move will leave him in one of the winning positions $(5,e)$ or $(4,e)$ or $(3,e)$ or $(2,e)$.
  • $(6,e)$ is a winning position because taking $1$ counter puts the opponent in the losing position $(5,o)$.

If you keep going like this you will find that the situation now repeats: the winning and losing positions for $n$ counters are the same as for $n-6$ counters. For example, if $n=7$ then $(n,o)$ wins and $(n,e)$ loses, same as for $n=1$; if $n=8$ then both $(n,o)$ and $(n,e)$ win, same as for $n=2$; and so on.

Therefore $n=27$, starting with an even number of counters ($0$ is even), is essentially the same as position $(3,e)$, and the first player wins by taking two counters.

The winning strategy is simply to follow the table of instructions given above. As there are really only twelve different positions going from $(1,o)$ to $(6,e)$, and three of these are losing positions so it doesn't matter what you do, there are in effect nine winning moves to be memorised. Here they are: in case you have never seen the notation, $n\,\hbox{mod}\,6$ means the remainder when $n$ is divided by $6$. The moves in brackets are alternatives but they cannot be used once you are down to the last six counters. $$\matrix{n\,\hbox{mod}\,6&0&1&2&3&4&5\cr o&\hbox{none}&1\,(2)&1&3\,(4)&3&\hbox{none}\cr e&1&\hbox{none}&2\,(3)&2&4&4\cr}$$ Probably a simple way of remembering them could be devised but I'll leave that up to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.