Metraipolis › archive › dc_ee23454f2e1a

Sprague–Grundy theorem — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T17:52:38.418Z
SHA-256 of the archived text
e41a46a94eb5c2ed0a52a0ba2bfbb05bd615cdf2d63cc95a5a8ef2fca31a7919
Stable URL of this page
https://metraipolis.com/documento/dc_ee23454f2e1a

How to cite

Sprague–Grundy theorem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ee23454f2e1a (Metraipolis archive dc_ee23454f2e1a, sha256 e41a46a94eb5c2ed0a52a0ba2bfbb05bd615cdf2d63cc95a5a8ef2fca31a7919)
BibTeX
@misc{dcee23454f2e1a,
  title = {Sprague–Grundy theorem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ee23454f2e1a; sha256 e41a46a94eb5c2ed0a52a0ba2bfbb05bd615cdf2d63cc95a5a8ef2fca31a7919},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim. The Grundy value or nim-value of any impartial game is the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the nim-sequence of the game. The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1936) and P. M. Grundy (1939).

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «zero-knowledge proof»).
Fonte: Wikipedia in inglese, voce «Sprague–Grundy theorem» — https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
Wikidata Q1687147 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1687147
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1362556548, consultata il 2026-10-15T17:01:16.757Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3a6d1280b6faa7cf970886d07699ca31bd6ba2232a2e0004c15bef48c7e2f3dd