Grundyho hra je strategická matematická hra pro dva hráče. Nejprve je tu jedna hromada položek. Dva hráči se střídají v rozdělování kterékoli z hromádek na dvě hromádky různých velikostí. Hra končí, když zbydou pouze hromádky dvou nebo jednoho předmětu žádné nelze rozdělit na hromady různých velikostí. Vyhrává hráč, který provedl poslední tah.
Hra, která začíná s jednou hromádkou 8 předmětů, vyhrává pro prvního hráče, pokud rozdělí původní hromádku na dvě ze 7 a 1 položky:
hráč 1: 8 → 7+1Hráč 2 nyní může provést jeden ze tří tahů: rozbít 7 na 6 + 1, 5 + 2 nebo 4 + 3. V každém z těchto případů může hráč 1 vrátit hromádky 4 předmětů a hromádky o velikosti 2 nebo méně soupeři. :
hráč 2: 7+1 → 6+1+1 hráč 2: 7+1 → 5+2+1 hráč 2: 7+1 → 4+3+1 hráč 1: 6+1+1 → 4+2+1+1 hráč 1: 5+2+1 → 4+1+2+1 hráč 1: 4+3+1 → 4+2+1+1Nyní musí hráč 2 rozdělit hromádku čtyř předmětů na 3 + 1, hráč 1 v budoucnu rozdělí 3 na 2 + 1:
hráč 2: 4+2+1+1 → 3+1+2+1+1 hráč 1: 3+1+2+1+1 → 2+1+1+2+1+1 Hráč 2 nemůže provést tah a prohrává.Hru lze analyzovat pomocí teorie Sprague-Grundy . Chcete-li to provést, musíte porovnat velikosti hromad ve hře Grundy s ekvivalentními velikostmi hromad ve hře Nim . Tato korespondence je popsána posloupností:
Velikosti hromádek: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Ekvivalentní velikosti hromad Neem: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ... (sekvence A002188 v OEIS )Pomocí této korespondence lze strategii pro hraní Nim použít také pro hru Grundy. Otázka, zda se posloupnost hodnot Nim pro Grundyho hru stává periodickou, je nevyřešeným problémem. Alvin Berlekamp , John Horton Conway a Richard Guy navrhli [1] , že je to periodické, ačkoli prvních 235 hodnot nalezených Achimem Flammenkampem to nepotvrzuje.