Grundys spel är ett strategiskt matematikspel för två spelare. Först finns det en hög med föremål. De två spelarna turas om att dela upp någon av högarna i två högar av olika storlekar. Spelet slutar när bara högar med två eller ett föremål återstår, som ingen kan delas upp i högar av olika storlekar. Spelaren som gjorde det sista draget vinner.
Ett spel som börjar med en enda hög med 8 föremål vinner för den första spelaren om han delar upp den ursprungliga högen i två av 7 och 1 föremål:
spelare 1: 8 → 7+1Spelare 2 kan nu göra ett av tre drag: bryta 7 till 6 + 1, 5 + 2 eller 4 + 3. I vart och ett av dessa fall kan spelare 1 lämna tillbaka högar med 4 föremål och högar av storlek 2 eller mindre till motståndaren :
spelare 2: 7+1 → 6+1+1 spelare 2: 7+1 → 5+2+1 spelare 2: 7+1 → 4+3+1 spelare 1: 6+1+1 → 4+2+1+1 spelare 1: 5+2+1 → 4+1+2+1 spelare 1: 4+3+1 → 4+2+1+1Nu måste spelare 2 dela upp en hög med fyra objekt i 3 + 1, spelare 1 kommer i framtiden att dela 3 i 2 + 1:
spelare 2: 4+2+1+1 → 3+1+2+1+1 spelare 1: 3+1+2+1+1 → 2+1+1+2+1+1 Spelare 2 kan inte göra ett drag och förlorar.Spelet kan analyseras med hjälp av Sprague-Grundy teorin . För att göra detta måste du matcha storlekarna på högarna i Grundy-spelet med motsvarande storlekar på högarna i spelet Nim . Denna korrespondens beskrivs av sekvensen:
Pålstorlekar: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Ekvivalenta storlekar av Neem-högar: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ... (sekvens A002188 i OEIS )Genom att använda denna korrespondens kan strategin för att spela Nim också användas för att spela Grundy. Frågan om sekvensen av Nim-värden för Grundys spel blir periodisk är ett olöst problem. Alvin Berlekamp , John Horton Conway och Richard Guy har föreslagit [1] att det är periodiskt, även om de första 235 värdena som hittats av Achim Flammenkamp inte bekräftar detta.