Exercise 607Combinatorics › Counting principlesM1Added 4 Nov 2026

Two take-away games

#games#winning positions#pairing strategy#Nim

Statement

A pile contains $n$ stones. Two players alternately remove between $1$ and $5$ stones. The player who takes the last stone wins. For which $n$ does the first player have a winning strategy?
There are two piles with the same number $m\ge1$ of stones. Two players alternately remove any positive number of stones from one pile of their choice. The player who takes the last stone wins. Who wins?

Hint

For part 1, find the positions that are lost for the player to move, starting from small $n$ . For part 2, think of a pairing strategy.

Show solutionHide solution

Solution

1. Winning positions. Positions $n=1,\dots,5$ are winning for the player to move. The position $n=6$ is losing. We claim the first player loses if and only if $6\mid n$ .

*If $6\mid n$ :* the second player answers each move "remove $k$ " by "remove $6-k$ ", which is legal. After each of his moves the number of stones is a multiple of $6$ . The first player can never take the last stone.
*If $6\nmid n$ :* the first player removes $r=n\bmod6\in\{1,\dots,5\}$ stones, leaving a multiple of $6$ and then plays the second player's strategy above.

Answer 1. The first player wins iff $n$ is not a multiple of $6$ .

2. Pairing. The second player wins. After each move of the first player, he removes the same number of stones from the other pile. Then the piles are equal after each of his moves. The first player can never take the last stone; the second player finishes by taking the last stones of the second pile.

Remark. These are the simplest cases of impartial game theory (Sprague–Grundy); the general sum-of-piles result is Bouton's solution of Nim.

Lesson. Compute the losing positions from the end of the game, then find a complement strategy.

Two take-away games

Statement

Solution

More problems in Counting principles