Impartial games and nim-values

An impartial game is a two-player game where both players have the same moves from every position, there is no chance, and (under the normal play convention) the player who cannot move loses. Project Euler returns to these games again and again — stone piles, paper strips, coins on a line, digits on a blackboard — because one theorem turns every one of them into arithmetic. The Sprague–Grundy theorem says each position is equivalent to a single Nim heap of some size, its nim-value (or nimber), and that a sum of independent games is worth the XOR of their values. The problems below then split three ways: those where you compute the Grundy table, those where the table hides a closed form that you have to find, and those where the game is the easy part and the question is a count — of losing positions, of winning moves — that the XOR structure lets you take over values instead of over positions.

The idea

Win/lose first: P- and N-positions

Every position of a finite impartial game is either a P-position (the Previous player wins — the player to move loses) or an N-position (the Next player wins). The classification is a two-line induction: a terminal position is P; a position is N if some move reaches a P-position, and P if every move reaches an N-position. When the question is only "who wins from here?", this boolean is all you need. Problem 961 (remove a digit; whoever takes the last non-zero digit wins) is solved exactly this way: the state compresses to a bitmask of zero/non-zero digit slots, every move produces a strictly smaller mask, so a single forward sweep over the masks fills the win/lose array with no recursion at all.

The boolean is also the right tool when the game is not a sum. In Problem 711 the players write numbers on a board and the winner is decided by the parity of the total count of binary ones, so the state is one budget plus one parity bit — nothing splits, and there is no nim-value to add. The tabulated win/lose pattern is still the key, it just describes the set of winning starts: here two rigid binary families (all-ones numbers, and isolated ones at even bit positions with a short all-ones tail). Once a winning set has that much structure, summing over it is algebra — geometric and arithmetico-geometric series — not a search.

Nim-values: mex over the options

The boolean stops being enough as soon as the game is a sum — several independent heaps or regions, where a move touches exactly one of them. Win/lose does not compose (two losing components do not make a losing sum in any simple way), but nim-values do. The Grundy value of a position is the mex — minimum excludant, the smallest non-negative integer not in a set — of the values of its options:

$$ g(p) = \operatorname{mex}\{\, g(q) : p \to q \,\} $$

A position is P exactly when g(p) = 0. Value k means "behaves like a Nim heap of k": from it you can reach every smaller value, but not k itself. For a one-parameter game (a heap of n stones under some move rule) the table is a direct loop:

def grundy_table(n_max: int, moves) -> list[int]:
    g = [0] * (n_max + 1)
    for n in range(1, n_max + 1):
        seen = {g[m] for m in moves(n)}
        g[n] = next(k for k in range(len(seen) + 1) if k not in seen)
    return g

mex of a set of size s is at most s, so the range(len(seen) + 1) bound is always enough. The same bound allows a push formulation that vectorises well: keep a boolean table reach[n][v] ("heap n has an option of value v"), only max-options + 1 columns wide; when heap n is finalised, its value is the first False in its row, and it then marks reach[n + k][g(n)] for every legal take k. Problem 310 (take a square number of stones) does exactly this, one NumPy row-scan and one fancy-indexed store per heap.

Positions that split into independent parts — painting two adjacent squares in a strip (Problem 306), cutting a rectangle into four (Problem 933) — fit the same mould: an option's value is the XOR of its parts' values, and the mex runs over those XORs.

Finding the sum hidden in the game

The theorem only pays off once you see the game as a sum, and the decomposition is not always the one the statement draws:

  • Products of moves. A coin on a grid that moves either left or up — never both — is the sum of a row game and a column game, so its value is g(x) ⊕ g(y). In Problem 649 each coin decomposes this way and the coins are independent, so the whole board is a sum of 2c one-dimensional subtraction games.
  • Trees. Cutting a node off a rooted tree and dropping its subtree is Green Hackenbush. Its colon principle says a stalk of one edge on top of a subtree of value v is worth v + 1, and the branches at a node are independent, so a node's value is the XOR over its children of (child value + 1). That is what makes Problem 400 (the game on a Fibonacci tree) a two-term recurrence instead of a search over a tree with thousands of digits' worth of nodes.

The nim-sum

The payoff is the nim-sum: for a sum of games, g(A + B) = g(A) ⊕ g(B), bitwise XOR. In plain Nim each heap's value is its size, so (a, b, c) is lost for the mover iff a ⊕ b ⊕ c = 0. Problem 301 is Nim with heaps (n, 2n, 3n) and turns entirely on the XOR: since n + 2n = 3n and a + b = (a ⊕ b) + 2(a & b), the triple is a P-position exactly when n & 2n = 0 — no two adjacent set bits — so the game question becomes a binary-string count.

Variants change the move rule but keep the structure. Problem 310 (take only a square number of stones) and Problem 509 (take only a proper divisor of the pile) are three-heap sums: compute each heap's Grundy value under the new rule, then count the triples whose values XOR to zero.

How to reason about it

Count by value, not by position. Grundy values are usually tiny compared with the positions they label — a few dozen or a few hundred distinct values over a range of 10⁵ or more. Once you have g, build a histogram cnt[v] of how many heaps take value v, and count P-positions of a multi-heap sum as Σ cnt[x]·cnt[y]·cnt[x ⊕ y] over value pairs (with care over ordering if the heaps are sorted). That is the step that turns an O(N³) triple loop into something linear in N plus a small square in the number of values. The sum is an XOR convolution of the histogram with itself, and the rest of the toolkit follows from that one word:

  • Sorted heaps. When the problem counts a ≤ b ≤ c, count ordered triples and divide out the symmetry with Burnside's lemma: a transposition fixes (a, a, c), which is losing iff g(c) = 0 because g(a) ⊕ g(a) = 0; a 3-cycle fixes only (a, a, a). Problem 310 needs nothing more than that — no case split over coinciding heaps.
  • Many components. c independent tokens give the c-fold XOR-convolution power of one token's histogram, so raise it by exponentiation by squaring — Problem 649 does O(log c) products of length-8 vectors, independent of the board size.
  • Diagonalise. The Walsh–Hadamard transform turns XOR convolution into pointwise products, the way the FFT does for ordinary convolution. It is the tool when the value alphabet is large or another axis rides along, but its inverse divides by the alphabet size: under a modulus like 10⁹ that size has no inverse, which is why 649 keeps the direct convolution and 922 (prime modulus) can use the transform.

Count winning moves by target value. A move in component i wins exactly when it takes that component from gᵢ to gᵢ ⊕ G, where G is the total — so "how many winning moves?" is "how many moves reach a given value?". When components nest, the target propagates down: in Problem 400 a move inside a child wins when the child's new value g' satisfies g' + 1 = t ⊕ (sibling term), so the count W(k, t) of moves in the depth-k tree that reach value t obeys a recurrence over levels and target values. Values stay far smaller than the tree, so the table is levels × values, not nodes.

Print the table before you trust it — then look for the closed form. The Grundy table is the honest algorithm, but most of these problems ask about bounds like 10¹⁶ where no table fits. The recurring move is: brute-force g(n) (or the P/N pattern) for small inputs, stare at it, and spot the structure. The shapes that keep turning up:

Pattern in the table Where it comes from Example
Depends on the binary digits of n a move rule tied to doubling or halving divisor-style piles (509), Problem 899: P exactly when the low bits of the larger pile are all ones, at a width set by the smaller pile's bit length
Depends on the Zeckendorf digits a move bound tied to the previous move Fibonacci nim in Problem 692: the minimal winning take is the smallest term of n's Zeckendorf representation
Depends on a generalised Zeckendorf basis a take bound of r × the previous take Problem 870: the losing piles obey H_{j+1} = H_j + H_{l_j}, l_j the first index with r·H_l ≥ H_j — Fibonacci for r = 2, powers of two for r = 1
Eventually periodic finite move sets on a line (octal games, subtraction games) the strip-painting game in 306 is Dawson's Kayles, whose values settle into a period after a short irregular prefix; the subtraction set {2, 3, 5, 7} in 649 has period 9 from the start
Structured winning set a non-additive win condition, e.g. a parity of bit counts Problem 711: two binary families, summed in closed form
A mex recurrence with arithmetic structure the "write the smallest unused number" constructions Problem 832: the mex-and-XOR sequence groups into blocks by powers of four

Once the pattern has a name, the answer usually falls to a digit DP or a sum over bit lengths in O(log n) — the game theory was only the doorway.

Detect a period; don't hard-code it. For a subtraction game whose largest take is s, g(n) depends only on the previous s values, so the first time the opening window g(0..s-1) reappears the sequence is periodic from there on. Checking for that window is a few lines of cycle detection, and it turns "count heaps of each value up to 10⁷" into q copies of one period plus a remainder.

When the rule has a real parameter, sweep its breakpoints. Problem 870 asks how the losing positions change as the ratio r in "take at most r × the last take" grows. The only place r enters is the comparison r·H_l ≥ H_j, so the whole sequence is constant between critical ratios H_j / H_{l_j − 1}; the next change is the smallest critical ratio above the current r. That is an event sweep along the r axis — exact fractions and cross-multiplication for the ties, and only the suffix after the first changed term rebuilt at each event.

Prove the pattern, or at least cross-check it. A pattern read off a table is a conjecture. The cheap insurance is to keep the brute-force Grundy solver and compare it with the closed form over every input it can reach — the solution to 899 does exactly this up to n = 200 before trusting the bit-length formula at the real bound.

Know when Sprague–Grundy does not apply. It needs an impartial game under normal play with independent components. Misère play (last mover loses) breaks the XOR rule outside a few special cases. Partisan games, where the players' moves differ — Problem 939 "Partisan Nim", Problem 949 "Left vs Right II" — need combinatorial game theory proper (surreal values, temperature) rather than nimbers. Nimbers do not vanish there, though: they are the impartial part of a partizan value. In Problem 922 the canonical form of every staircase diagram, computed for small cases, came out as an integer plus a nimber, (b − a) + *(k − 1); a sum of them is N + *X with N an ordinary sum and X an XOR, and the first player (Right) wins iff N > 0, or N = 0 and X ≠ 0. The count is then an ordinary convolution in N crossed with an XOR convolution in X — Walsh–Hadamard on one axis, polynomial powers on the other. And a move whose legality depends on history (Fibonacci nim's "at most twice the last take") makes the state bigger than the heap: fold the history into the state before you look for a value.

Problems10 / 31

  • ○ 0260 — Stone Game
  • ● 0301 — Nim
  • ○ 0306 — Paper-strip Game
  • ● 0310 — Nim Square
  • ○ 0344 — Silver Dollar Game
  • ○ 0366 — Stone Game III
  • ○ 0391 — Hopping Game
  • ● 0400 — Fibonacci Tree Game
  • ○ 0459 — Flipping Game
  • ○ 0488 — Unbalanced Nim
  • ○ 0509 — Divisor Nim
  • ○ 0550 — Divisor Game
  • ○ 0560 — Coprime Nim
  • ○ 0629 — Scatterstone Nim
  • ○ 0644 — Squares on the Line
  • ● 0649 — Low-Prime Chessboard Nim
  • ○ 0665 — Proportionate Nim
  • ● 0692 — Siegbert and Jo
  • ● 0711 — Binary Blackboard
  • ○ 0798 — Card Stacking Game
  • ○ 0806 — Nim on Towers of Hanoi
  • ○ 0832 — Mex Sequence
  • ○ 0859 — Cookie Game
  • ● 0870 — Stone Game IV
  • ○ 0888 — 1249 Nim
  • ● 0899 — DistribuNim I
  • ○ 0900 — DistribuNim II
  • ● 0922 — Young's Game A
  • ○ 0933 — Paper Cutting
  • ○ 0953 — Factorisation Nim
  • ● 0961 — Removing Digits