Sprague-Grundy theorem: every impartial game position has a Grundy value G. G(n) = mex{G(m) : m reachable from n}. G=0 means losing (P-position). Game sum: G(A+B) = G(A) ⊕ G(B). Reduces any impartial game to Nim!
How to Use
Choose game type:
- Subtraction: Remove from {s₁,...,sₖ}
- Grundy values: Computed via mex
- Win/Lose: G=0 or G>0
The Mex Function
mex(S) = minimum excludant = smallest non-negative integer NOT in S. mex({0,1,3})=2. mex({1,2})=0. mex({})=0. This builds Grundy values bottom-up from terminal positions.
The Theorem
Every position in an impartial game is equivalent to a Nim heap of size G(n). Sum of games: Grundy values XOR. So ANY impartial game can be analyzed using Nim theory!
Step-by-Step Instructions
- 1Choose game.
- 2Compute Grundy values.
- 3Find G(n).
- 4XOR for sums.
- 5Determine winner.