Exercise 1312Combinatorics › Counting principlesM1Added 5 Nov 2026

Nim and the XOR rule

#combinatorial games#Nim#XOR#binary

Statement

In the game of Nim there are several piles of stones. Two players alternately remove any positive number of stones from one pile; the player who cannot move loses. Prove that the player to move wins if and only if the bitwise XOR of the pile sizes is non-zero. Which move wins from $(3,4,5)$ ?

Hint

Show that from XOR $=0$ every move produces XOR $\ne0$ , and that from XOR $\ne0$ there is a move to XOR $=0$ (look at the leading bit of the XOR).

Show solutionHide solution

Solution

Idea. Call a position *balanced* if the XOR $s$ of the pile sizes is $0$ . Show that balanced positions are exactly the losing ones.

Balanced to unbalanced. If the position is balanced and a pile $a$ is replaced by $a'<a$ , the new XOR is $a\oplus a'\ne0$ .

Unbalanced to balanced. Let $s\ne0$ and let $t$ be the position of its leading bit. Some pile $a$ has bit $t$ set. Replace $a$ by $a'=a\oplus s$ . Since $s$ has leading bit $t$ and $a$ has that bit equal to $1$ , flipping it makes $a'<a$ , so removing $a-a'$ stones is legal, and the new XOR is $s\oplus a\oplus a'=0$ .

Conclusion. The terminal position is balanced. A player facing a balanced position can only move to unbalanced positions; so the player facing a balanced position loses. ∎

Example. $3\oplus4\oplus5=2\ne0$ . The pile $3$ has the bit of value $2$ : replace it by $3\oplus2=1$ , i.e. remove $2$ stones. The position $(1,4,5)$ has XOR $0$ ✓.

Lesson. For impartial games, find the invariant set of losing positions and prove the two closure properties.

Nim and the XOR rule

Statement

Solution

More problems in Counting principles