Solution
Nim 3-4-5
Show the problem again
Two players play Nim with piles of 3, 4, and 5 stones. Players alternately remove any positive number of stones from a single pile; whoever takes the last stone wins. The first player wins with optimal play, and the winning first move is unique. How many stones does it remove?
Worked solution
The answer is 2: remove 2 stones from the pile of 3, leaving piles of 1, 4, 5. By the Sprague–Grundy theorem, a Nim position is losing for the player to move iff the XOR of pile sizes is 0. Here 3 ⊕ 4 ⊕ 5 = 2 ≠ 0, so the first player wins. The only pile that can be reduced to make the XOR zero is the 3-pile: 3 → 1 gives 1 ⊕ 4 ⊕ 5 = 0, handing the opponent a losing position; thereafter, always restore XOR = 0.
Source: Nim, solved by Charles Bouton (1901). Statement written for AxiomIQ.