Nim and Sprague-Grundy Values

XOR the pile sizes to win Nim; mex turns any impartial game into one.

The idea

Nim is played with several piles of tokens; a move removes any positive number of tokens from a single pile, and the player who cannot move loses. It is the model impartial game — both players always have the same moves available, so the position alone, not whose turn it is, decides who wins under best play.

The winning rule uses the nim-sum, written $\oplus$: write the pile sizes in binary and add column by column without carrying, so a column is $1$ exactly when an odd number of piles have a $1$ there. A Nim position is a loss for the player to move if and only if its nim-sum is $0$.

Two facts justify the rule. From a position of nim-sum $0$, every move changes exactly one pile and therefore makes the nim-sum nonzero. From a position of nonzero nim-sum, some pile can be shrunk to make the nim-sum $0$. So the winning player can return the nim-sum to $0$ on every turn, and the opponent can never do the same.

Reach for the nim-sum whenever a puzzle is a two-player removal game, especially one that splits into independent piles or components with each move touching only one of them.

Ways to work on it

• Walkthrough. Find the winning move in Nim using the nim-sum rule.
• Practice. Compute a nim-sum and decide who wins.
• Hardest. Compute Grundy values for a composite game and decide who wins.

Not sure where to start? Take the ten-question placement test.