Operace XOR
Počty kamenů převedeme do dvojkové soustavy. Počty kamenů dále napíšeme pod sebe a sečteme binární operací XOR (exlusive or), kterou označujeme také Å.
XOR | 0 | 1 ------+-----+----- 0 | 0 | 1 ------+-----+----- 1 | 1 | 0
Tato operace odpovídá logické spojce 'vylučovací nebo'. Vidíme, že tato operace je komutativní, asociativní a komutativní, má navíc nulový prvek 0, a je tedy grupovou operací množiny { 0, 1 }. Sčítání XOR je modulo 2. Každý prvek je sám k sobě inverzní (opačný).
Odtud získáme jednoduché pravidlo pro naše hromádky:
Pokud ve sloupcích bude lichý počet jedniček, píšeme 1, v ostatních případech píšeme 0. Pár příkladů:
101 5 1 1 100 4 XOR 110 6 10 2 111 7 ---- 11 3 11 3 011 100 4 XOR 100 4 XOR 101 5 --------- -------- 100 001
Pokud výsledek je nenulový, v prvním tahu se snažíme dostat 0, tj. odebereme tolik kamenů, abychom se dostali do 0. V nulové hře existuje vyhrávající strategie pro druhého hráče. Bude-li na hrací ploše 0 kamenů, není výhodné začínat, druhý hráč vyhrává (Kdo nemá tah, prohrál.) Je-li hráč na tahu v netriviální nulové hře, potom, ať zahraje jakkoliv, dostane se do nenulové pozice (bere nenulový počet předmětů). Tedy:
Příklad:
--> počty kamenů | binárně 1 | 1 2 | 10 3 | 11 4 | 100 5 | 101 6 |XOR 110 ----------------------- 111
Protože součet Å je nenulový, hráč, který je na tahu, má vyhrávající strategii - odebrat takový počet kamenů, aby se dostal do nulové hry. Takovým dobrým tahem je z poslední hromádky odebrat 5 kamenů. Pokud součet Å je nulový, odebráním kamenů se dostane do nenulové pozice.
Zbývá ještě algoritmizovat, ze které hromádky a kolik kamenů vezmeme. Vraťme se ještě k našemu předcházejícímu příkladu. V každém řádku přičteme (tj. odečteme) (111)2 (Proč?), a dostaneme:
--> počty kamenů | binárně Å(111) dekadicky 1 | 1 110 = 6 2 | 10 101 = 5 3 | 11 100 = 4 4 | 100 11 = 3 5 | 101 010 = 2 6 |XOR 110 001 = 1
Tedy, budeme-li chtít snížit počet kamenů na některé hromádce, musíme získat číslo menší, než bylo původní (tj. původní počet kamenů)! To můžeme udělat ve čtvrté, páté nebo šesté hromádce.
Speciální konfigurace je ta, když nějaké dvě hromádky mají stejný počet kamenů. V takové hře existuje vyhrávající strategie pro druhého hráče - stačí kopírovat tahy soupeře. Této strategii se také někdy říká kradení strategie. Tato strategie umožnuje brát kámen jako poslední a tedy vyhrát (normální varianta). V betlové variantě lze postupovat analogicky - zde kritické pozice je jedna hromádky s jedním předmětem.
Hry NIM patří k absolutně nestranným hrám a reprezentují všechny absolutně nestranné hry.