Nim With Three Piles

  • Hard
  • Game strategy puzzles
  • Tests: Finding the invariant a winning move restores

The puzzle

Three piles hold 3, 5 and 7 counters. Players alternate; a move is to take any number of counters, at least one, from a single pile. Whoever takes the last counter wins.

Who wins, and what is the first move?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Write the pile sizes in binary and add each column without carrying - that is, XOR them.

Hint 2

3 = 011, 5 = 101, 7 = 111. Column by column, mod 2: 001. Not zero, so the player to move can win.

Show the answer Hide the answer

The first player wins. Take one counter from the pile of 7, leaving 3, 5 and 6 - whose nim-sum is zero.

How to get there

Compute the nim-sum: XOR the pile sizes. 3 XOR 5 = 6, and 6 XOR 7 = 1. It is non-zero, which means the position is a win for the player about to move.

A winning move makes the nim-sum zero. Note that 3 XOR 5 = 6, so changing the third pile from 7 to 6 leaves 3 XOR 5 XOR 6 = 0. Taking one counter from the seven does exactly that.

Why zero is losing: from a zero position every move changes exactly one pile, and changing one pile must change the nim-sum away from zero - so the opponent always hands you a non-zero position, and you hand back a zero one. The game strictly shrinks, so it ends, and it ends on the player facing 0, 0, 0 - a nim-sum of zero with nothing to take. That is Bouton's theorem, and it makes Nim one of the few games solved completely.

The technique worth keeping

Look for a quantity that is zero exactly at the losing positions and that every move must disturb. If you can always restore it and your opponent never can, you have a complete strategy rather than a heuristic.