Sprague–Grundy theorem

E163078

mathematical theorem result in combinatorial game theory

The Sprague–Grundy theorem is a fundamental result in combinatorial game theory that assigns each impartial game position a nonnegative integer (its Grundy value), allowing such games to be analyzed and combined via nim-like addition.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (6)

Label	Occurrences
Grundy numbers	1
Grundy theorem	1
Grundy value	1
Sprague–Grundy function theorem	1
Sprague–Grundy theorem canonical	1
Sprague–Grundy theory	1

How this entity was disambiguated

This entity first appeared as the object of triple T1422430 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Sprague–Grundy theorem
Context triple: [Winning Ways for your Mathematical Plays, coversConcept, Sprague–Grundy theorem]

A. Winning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays is a multi-volume book on combinatorial game theory that popularizes and systematically explores mathematical games and their underlying structures.
B. Conway’s Game of Sprouts
Conway’s Game of Sprouts is a pencil-and-paper topological game in which players alternately connect dots with lines under simple rules, leading to rich combinatorial and mathematical analysis.
C. On Numbers and Games
On Numbers and Games is a mathematical book by John H. Conway that introduces surreal numbers and explores combinatorial game theory in a rigorous yet playful style.
D. Sperner's lemma
Sperner's lemma is a fundamental result in combinatorial topology that guarantees the existence of a fully labeled simplex in certain labeled triangulations, and is widely used to prove fixed-point and equilibrium theorems.
E. Surreal numbers
Surreal numbers are a class of numbers introduced by John H. Conway that form an extensive ordered field encompassing the real numbers, infinite quantities, and infinitesimals within a unified framework.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Sprague–Grundy theorem
Target entity description: The Sprague–Grundy theorem is a fundamental result in combinatorial game theory that assigns each impartial game position a nonnegative integer (its Grundy value), allowing such games to be analyzed and combined via nim-like addition.

A. Winning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays is a multi-volume book on combinatorial game theory that popularizes and systematically explores mathematical games and their underlying structures.
B. Conway’s Game of Sprouts
Conway’s Game of Sprouts is a pencil-and-paper topological game in which players alternately connect dots with lines under simple rules, leading to rich combinatorial and mathematical analysis.
C. On Numbers and Games
On Numbers and Games is a mathematical book by John H. Conway that introduces surreal numbers and explores combinatorial game theory in a rigorous yet playful style.
D. Sperner's lemma
Sperner's lemma is a fundamental result in combinatorial topology that guarantees the existence of a fully labeled simplex in certain labeled triangulations, and is widely used to prove fixed-point and equilibrium theorems.
E. Surreal numbers
Surreal numbers are a class of numbers introduced by John H. Conway that form an extensive ordered field encompassing the real numbers, infinite quantities, and infinitesimals within a unified framework.
F. None of above. chosen

Statements (46)

Predicate	Object
instanceOf	mathematical theorem ⓘ result in combinatorial game theory ⓘ
alsoKnownAs	Grundy theorem ⓘ linked to: Sprague–Grundy theorem Sprague–Grundy function theorem ⓘ linked to: Sprague–Grundy theorem Sprague–Grundy theory ⓘ linked to: Sprague–Grundy theorem
appliesTo	finite impartial games under normal play ⓘ impartial combinatorial games ⓘ
associates	each game position with a nonnegative integer ⓘ
assumes	finite game positions ⓘ no chance moves ⓘ normal play rule where last move wins ⓘ perfect information ⓘ two-player play ⓘ
characterizes	positions of impartial games by nonnegative integers ⓘ
classification	P-positions and N-positions via Grundy values ⓘ
defines	Grundy value ⓘ linked to: Sprague–Grundy theorem nim-value ⓘ
determines	a position is losing iff its Grundy value is 0 ⓘ a position is winning iff its Grundy value is nonzero ⓘ
field	combinatorial game theory ⓘ combinatorics ⓘ
formalizes	equivalence of impartial games to Nim heaps ⓘ
foundationFor	nim-heap decomposition of games ⓘ systematic analysis of impartial games ⓘ
historicalPublication	Patrick Michael Grundy's work in the 1930s ⓘ Roland Sprague's work in the 1930s ⓘ
implies	every impartial game under normal play is equivalent to a Nim heap ⓘ outcome of a sum of impartial games can be determined by xor of Grundy values ⓘ
namedAfter	Patrick Michael Grundy ⓘ Roland Sprague ⓘ
relatedTo	Grundy numbers ⓘ linked to: Sprague–Grundy theorem Hackenbush (impartial variants) ⓘ Kayles ⓘ Nim ⓘ Wythoff Nim ⓘ impartial game theory ⓘ octal games ⓘ
statesThat	each impartial game position has a unique nonnegative integer Grundy value ⓘ every position in a finite impartial game under normal play is equivalent to a heap of Nim of some size ⓘ the Grundy value of a disjunctive sum of impartial games is the bitwise xor of the Grundy values of the components ⓘ
usedFor	analyzing impartial games ⓘ combining impartial games via nim-sum ⓘ deciding winning and losing positions ⓘ
usesConcept	disjunctive sum of games ⓘ minimum excluded value (mex) ⓘ normal play convention ⓘ

How these facts were elicited