Nim, symmetry strategies and who wins

Two-player games with no chance and no hidden information always have a winner determined from the start. The interview question is which player, and the answer comes from one of three techniques: find the pattern in small cases, apply the XOR rule for Nim, or find a symmetry you can mirror.

Definition 6.1

Winning and losing positions

P-position and N-position — A position is *losing* (a P-position, good for the previous player) if every move from it leads to a winning position. It is *winning* (an N-position, good for the player to move) if some move leads to a losing one. Under normal play the terminal position — no moves available — is losing, and everything else is built up from there.

Proposition 6.2

Tabulate the small cases

For a take-away game, write out positions $0, 1, 2, \dots$ and mark each as winning or losing using the definition. A pattern almost always emerges within the first half dozen, and once you have it you can state the answer for any size and prove it by induction in one sentence.

Holds when

Subtraction game allowing 1, 2 or 3: the losing positions are the multiples of 4.
Generally, if you may remove 1 to $k$ , the losing positions are the multiples of $k+1$ .
The strategy follows from the pattern: always move *to* a losing position.

Example 6.3

Twenty-one coins are on the table. Players alternate removing one, two or three, and whoever takes the last coin wins. Who wins, and how?

Show the worked solutionHide the worked solution

Worked solution

Formula $\text{losing positions} = \text{multiples of } k+1 = 4$
Substitute $21 = 4 \times 5 + 1$
Solve $21 \not\equiv 0 \pmod 4 \Rightarrow \text{the first player wins}$
$\text{take } 1, \text{ leaving } 20$
Answer $\text{first player, by taking 1 then restoring a multiple of 4}$

Sanity check. After the opening move, whatever the opponent takes — $t$ coins, with $1 \le t \le 3$ — reply with $4 - t$ . The total falls by exactly four each round, so the opponent always faces a multiple of four and eventually faces zero.

Equation 6.4

Nim

Several piles; a move removes any positive number from one pile; the player taking the last object wins. The XOR — the "Nim-sum" — of the pile sizes decides everything.

\text{losing position} \iff a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0

$\oplus$: Bitwise exclusive or: add the binary digits without carrying.
$= 0$: Every pile size cancels in every bit position, so the player to move loses.

Why XOR of all things. Two facts do all the work. From a Nim-sum of zero, *any* move breaks it — you have changed one pile, so at least one bit position no longer cancels. From a non-zero Nim-sum, there is always a move back to zero: look at the highest set bit, find a pile with that bit set, and reduce it so the remaining piles cancel. Together these say the zero positions are exactly the losing ones, and the winning strategy is "always hand your opponent a zero". The Sprague–Grundy theorem extends this to every impartial game, by assigning each position a Nim-value.

Nim, symmetry strategies and who wins

After this lesson you should be able to

Winning and losing positions

Tabulate the small cases

Nim

The rest of this lesson is in Premium