Nim and Winning Positions

Nim is the puzzle most likely to appear in an interview precisely because its full solution is one formula, and interviewers can watch whether you find the invariant or just guess. Once you see the rule, every question about who wins and what to play becomes arithmetic.

The game

There are several piles of stones. Two players alternate turns; on a turn, a player removes any positive number of stones from any single pile (but only one pile per turn). The player who removes the last stone wins. Given the starting pile sizes, who wins with perfect play, and what should they do?

The claim. Write each pile size in binary and XOR them all together (bitwise addition without carrying: a bit is 1 in the result exactly when an odd number of the piles have a 1 in that bit position). If the XOR of all pile sizes is 0, the position is losing for the player about to move; if it's nonzero, the position is winning, and there is always a move to a XOR-zero position.

Why zero-XOR positions lose. This is an invariant argument. If the XOR is already 0, any single move (which changes exactly one pile) must change that pile's contribution to the XOR, so the total XOR after the move becomes nonzero — you cannot move from a zero-XOR position to another zero-XOR position. Conversely, if the XOR is nonzero, there's always a way to shrink exactly one pile to make the XOR zero again (found by looking at the highest bit where the XOR is 1, and reducing whichever pile has a 1 there). So from a nonzero position you can always hand your opponent a zero position, and from a zero position you're always forced to hand them a nonzero one. The all-zero pile position (0,0,...,0), the actual end of the game, has XOR 0 — a loss for whoever is stuck facing it, meaning the player who just moved (took the last stone) wins. Zero-XOR is a losing position for the mover, all the way down.

Worked example

Piles are 5, 7, and 3. Who wins, and what's the winning move?

In binary: $5 = 101$, $7=111$, $3=011$. XOR bitwise: $101 \oplus 111 = 010$, then $010 \oplus 011 = 001$. The total XOR is $1$, nonzero — the player to move wins.

Finding the move. The XOR is 1, so look at pile sizes XORed with the total: pile 5 gives $5 \oplus 1 = 4$ (a valid reduction, since $4<5$) — reduce the 5-pile to 4. Check: new XOR is $100 \oplus 111 \oplus 011 = 011 \oplus 011 = 0$. That's the winning move.

The XOR-invariant idea generalises to the Sprague-Grundy theorem, which assigns every impartial combinatorial game a single number (its "Nim-value") so that any sum of independent games can be analysed by XORing their individual values — the same reduction from a huge game tree to simple arithmetic.