How to win this game?

Question

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?

Answer 1

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.