Every position in an impartial game under the normal play convention is equivalent to a Nim heap of some size, its Grundy number. Proved independently by Roland Sprague and Patrick Michael Grundy, it reduces the analysis of a huge class of combinatorial games to the single well-understood game of Nim.
Facts
StatementEvery impartial game played under the normal play convention, where the last player able to move wins, is equivalent either to a single heap of the game of Nim or to an infinite generalization of Nim. The equivalent heap size, its Grundy value, is computed from the game's own position and lets any two impartial games be compared or combined as if they were heaps of Nim. 1 Proof YearSprague published the result in 1936; Grundy reached it independently in 1939, the joint naming this theorem carries. Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Sprague-Grundy Theorem (Wikipedia)
Wikimedia FoundationLead section
In combinatorial game theory, the Sprague-Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim.
Theory section
a theory discovered independently by R. P. Sprague (1936) and P. M. Grundy (1939)
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.