Everything Is Nim

The Sprague–Grundy theorem

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Every impartial game is equivalent to a Nim heap of size equal to its Grundy number.
• Grundy number = mex of the Grundy numbers of the positions you can reach.
• For combined games, take the nim-sum of the Grundy numbers.

Steps

1. Grundy numbers
2. Take one or two, again
3. Compute a mex
4. Take one, three or four
5. Patterns in Grundy numbers
6. Playing two games at once