Úvod do teorie kombinatorických her

Laskerův NIM

Laskerův NIM je zobecněním obecného NIMu. Hráč, který je na tahu, může buď odebrat libovolný počet předmětů z libovolné hromádky, nebo hromádku rozdělit na dvě.

Poměrně jednoduše se dojde ke Sprague-Grundyho funkci (výtvarný zákon posloupnosti):

Na jedné hromádce g(0) = 0, g(1) = 1. Při dvou předmětech dostáváme tyto tři pozice (0), (1), (1,1). Protože 1 Å 1 = 0, je g(2) = 2. Při třech předmětech po prvním tahu se můžeme dostat do pozic (0), (1), (2), (1,2). Protože 1 Å 2 = 3, proto g(3) = mex{0,1,2,3} = 4 atd.

Postupně dostaneme tyto výsledky:

  n   0  1  2  3  4  5  6  7  8  9  10  11  12 ...
g(n)  0  1  2  4  3  5  6  8  7  9  10  12  11 ...

Obecně Sprague-Grundy funkce pro jednu hromádku je: g(4k+1) = 4k+1, g(4k+2) = 4k+2, g(4k+3) = 4k+4, g(4k+4) = 4k+3, pro každé k ≥ 0, tj. g(n) = g(n-4) + 4, pro n ≥ 4.

Důkaz provedeme indukcí:
(a) je-li na hromádce 4k+1 předmětů, potom svým tahem se můžeme dostat do jedné hromádky s 0, 1, 2, ..., 4k předmětů, resp. (4k,1), (4k-1,2), (4k-2,3),...(2k+1,2k). Protože hodnoty na dvou hromádkách jsou vždy liché, dostáváme g(4k+1) = 4k+1.
(b) na hromádce nyní máme 4k+2 předmětů. Po prvním tahu počty předmětů mohou být 0, 1, ..., 4k+1, resp. (4k+1,1), (4k,2), (4k-1,3),...,(2k+1,2k+1). Hodnoty jsou buď sudé, nebo dělitelné 4. Proto g(4k+2) = 4k+2.
(c) máme-na hromádce 4k+3 předmětů, g(4k+3) bude nejměně 4k+2, protože můžeme odebrat 4k+2, 4k+1, 4k,..., 1. Odpovídající pozice jsou 0, 1, 2, ..., 4k+2. Nyní budeme rozdělovat hromádku s 4k+3 předměty na dvě. Dostaneme se do stavů (4k+2,1), (4k+1,2), ..., (2k+2, 2k+1). Všechny tyto pozice nabývají lichou hodnotu, a navíc g(4k+2,1), podle předchozího výpočtu v bodu (b), je g(4k+2,1) = g(4k+2) + g(1) = 4k+2 + 1 = 4k + 3. Proto hodnota g(4k+3) = mex{0,1,2, ...,4k+3} = 4k + 4.
(d) Poslední případ: na hromádce je právě 4k+4 předmětů, budeme-li odebírat po jednom, dvou atd. předmětech, dostaneme se jistě do stavů, 0, 1, 2, ..., 4k+2 a také do stavu 4k+3, podle předcházejícího výpočtu ale g(4k+3) = 4k + 4, tj. přeskočíme jednu hodnotu. Postupně dále rozebereme hromádku na dvě, dostaneme pozice (4k+3,1), (4k+2,2), ..., (2k+2,2k+2). Tyto hodnoty jsou buď sudé, nebo 1 (mod 4). Odtud: g(4k+4) = 4k+3.

Úloha: Analyzujte hru v postavení (2,5,7).

Rekurzivní definice Sprague-Grundy posloupnosti g(n) je

g(n) = min{N - {g(0),g(1),...,g(n-1),g(1)Åg(n-1), g(2)Åg(n-2),...}}.

Lasker si všiml ještě jedné zákonitosti. Hromádku, která není ekvivalentní s disjunktním součtem hromádek s menším počtem předmětů, nazýváme prvočíselnou hromádkou. Prvočíselné hromádky obsahují 1, 2, 3, 4, 7, 15, 31, ... předmětů. Od čísla dva to je 2k-1. Každá pozice v Laskerově NIMu je buďto prvočíselná hromádka, nebo disjunktní součet prvočíselných hromádek. (Analogie základní věty aritmetiky.) Každá pozice v Laskerově NIMu je ekvivalentní nějaké prvočíselné hromádce. Prohrávající pozice je ta, jejíž rozklad na prvočíselné hromádky můžeme pospárovat, tj. počet každé prvočíselné hromádky je sudý (existuje vyhrávající strategie pro druhého hráče).

Úloha: Proveďte analýzu normální varianty Laskerovy hry: Hráč, který je na tahu, může buď odebrat libovolný počet předmětů z libovolné hromádky, nebo hromádku rozdělit na dvě nestejné hromádky. (viz též hra Grundy a NIM)

Klíčová slova: Hra NIM, Nimbers, Sprague-Grundy funkce, vyrovnaný a nevyrovnaný stav (alespoň jeden hráč má zaručeno, že protihráč nemůže vyhrát ihned v následujícím tahu). Hra bez patu. Nim čísla.