Nim

Several heaps of stones. A move removes any positive number of stones from one heap. The player who cannot move loses (normal play).

Bouton’s theorem

The first player wins iff the nim-sum $a_1\oplus a_2\oplus \cdots \oplus a_n\ne 0$.

bool firstPlayerWins(const vector<int>& heaps) {
    int x = 0;
    for (int h : heaps) x ^= h;
    return x != 0;
}

Finding a winning move

Let $S=⨁a_i\ne 0$. Find any heap with $a_i\oplus S<a_i$ (at least one exists — the heap whose bit at $S$‘s highest set bit is 1) and reduce it to $a_i\oplus S$. The new nim-sum is 0.

pair<int,int> winningMove(const vector<int>& a) {
    int S = 0;
    for (int h : a) S ^= h;
    if (!S) return {-1, -1};
    for (int i = 0; i < (int)a.size(); i++)
        if ((a[i] ^ S) < a[i]) return {i, a[i] ^ S};      // heap i, new size
    return {-1, -1};
}

Why XOR

Two facts prove the theorem:

1. From $S=0$, every move gives $S\ne 0$. Changing one heap changes the XOR, since $a\oplus a^{\prime }\ne 0$ when $a\ne a^{\prime }$.
2. From $S\ne 0$, some move gives $S=0$. Take the highest set bit $b$ of $S$; some heap has that bit set, and $a_i\oplus S<a_i$ for it (the bit turns off), so reducing it to $a_i\oplus S$ is legal.

Terminal position (all heaps empty) has $S=0$ and is losing — which anchors the induction. ∎

Misère Nim

The player who takes the last stone loses.

Play exactly as in normal Nim, unless every heap has size 1. In that case the first player wins iff the number of heaps is even.

bool misereWins(const vector<int>& a) {
    int S = 0, big = 0;
    for (int h : a) { S ^= h; if (h > 1) big++; }
    if (big == 0) return a.size() % 2 == 0;              // all heaps are 1
    return S != 0;
}

The intuition: with a heap of size $\ge 2$, the winner can always steer the endgame to leave an odd or even number of 1-heaps as needed, so the normal-play strategy carries over until only 1-heaps remain.

Why Nim is the universal game

Sprague-Grundy: every position in every finite impartial game under normal play is equivalent to a single Nim heap, whose size is that position’s Grundy number. A sum of games is equivalent to a Nim position with those heap sizes.

So solving Nim solves all impartial games — you only have to compute the Grundy values.

The variants

Variant	Rule	Solution
Nim	remove any number from one heap	XOR $\ne 0$
Misère Nim	last stone loses	as above
Moore’s Nim${}_k$	remove from up to $k$ heaps	write heaps in binary; losing iff every bit column sums to $0\mathrm{mod}(k+1)$
Staircase Nim	move coins one step down a staircase	XOR of the odd-indexed positions
Wythoff’s game	two heaps; remove from one, or equally from both	losing iff $(\lfloor k\varphi \rfloor ,\lfloor k{\varphi }^2\rfloor )$
Subtraction game	remove $s\in S$ stones	Grundy values, often periodic
Turning games / Mock Turtles	flip coins	Grundy theory
Nim with a move limit	at most $m$ per move	$g(a)=a\mathrm{mod}(m+1)$
Lasker’s Nim	remove, or split a heap in two	$g$ has a period-4 pattern

See Nim Variants for the details.

Nim with a bounded move

If each move removes between 1 and $m$ stones, then $g(a)=a\mathrm{mod}(m+1)$, so the position is losing iff $⨁(a_i\mathrm{mod}(m+1))=0$. This is the “subtraction game” $S=\{\mathrm{1..}m\}$ and is the most common Nim variation in contests.

Staircase Nim — the reduction worth knowing

Coins on stairs $\mathrm{0..}n$; a move slides any number of coins from step $i$ to step $i-1$; coins on step 0 are dead. This is equivalent to Nim on the odd-indexed steps: moves from odd to even steps are real Nim moves, and moves from even to odd steps can always be mirrored by the opponent.

Many “move tokens toward the end” games reduce to staircase Nim.

See also: Grundy Numbers · Nim Variants · Sprague-Grundy