Úvod do teorie kombinatorických her

Marienbad poznámky

Hrami typu NIM se budeme ještě zabývat na jiné místě. Ve hře Marienbad existuje vyhrávající strategie pro druhého hráče, jedná se tedy o nulovou hru:

Zadání: Máme několik přirozených čísel, jejich bitový Å je nenulový. Dokažte, že lze jedno z nich zmenšit (a ostatní nechat) tak, aby bitový Å získaných čísel byl nulový.

Většinu jedniček v součtu Å můžeme spárovat. Všimneme si nyní nejvýznamnější jedničky ve dvojkovém zápisu Å zadaných čísel (první jednička zleva v součtu modulo 2). Taková existuje alespoň jedna (dk. sporem). Přičteme-li (nebo lépe odečíst) k počtu k zadaným přirozeným číslům ve dvojkové soustavě součet Å všech zadaných přirozených čísel ve dvojkové soustavě, dostaneme číslo menší, než bylo toto přirozené číslo. Rozdíl tohoto čísla v desítkové soustavě nám současně říká, o kolik máme zmenšit toto přirozené číslo.

Odtud plyne i řešení pro hry NIM: Hru hrají dva hráči s několika hromádkami zápalek. Tah spočívá v odebrání libovolného počtu zápalek z jedné z hromádek. Kdo nemůže táhnout, prohrál; nebo-li, kdo hrál jako poslední, vyhrál.

Tvrzení: Ve hře NIM existuje vyhrávající strategie pro prvního hráče právě tehdy, když Å počtu kamenů na jednotlivých hromádkách je nenulový.

Pokud součet Å je nenulový, stačí vybrat hromádku, ve které se vyskytuje nejvýznačnější jednička. Z této největší hromádky vezmeme kameny, které prozatím ještě nejsou spárované. Dostaneme se tak do nulové hry, ve které ex. vyhrávající strategie pro druhého hráče, ve hře, ve které je na tahu druhý hráč, a jsou všechny kameny spárované. Tím se nám celý problém zjednoduší... A tak dále postupujeme, až dostaneme hru, ve které nejsou již žádné kameny. (Dk. indukcí). Je-li naopak hra NIM nulová, potom hráč, který je na tahu, musí si zvolit hromádku (pokud existuje) a vzít libovolný nenulový počet kamenů. Tím ale poruší symetrii (spárování) kamenů, součet Å bude nenulový.

Ve hře Mariendbad máme tedy na hromádkách 1, 3, 5, a 7 kamenů. Označme tuto pozici (1,3,5,7)10, ve dvojkové soustavě dostaneme (1,11,101,111)2. Provedeme-li Å(1,11,101,111)2, dostaneme 0. Tedy, ať zahraje první hráč jakkoliv, druhý hráč odebere tak, aby součet Å byl nulový. Bere kameny, kde je významná jednička, a případně všechny ještě nespárované kameny..., z této hromádky.

Uvažujme ještě pozici (1,5,7)10, tedy (1,101,111)2, která je subhrou Marienbad. Provedeme-li Å součet, dostaneme nenulový rozdíl 3 = (11)2. Přičteme-li postupně Å(1, 112), Å(1012, 112) a Å(1112, 112), dostaneme 102, 1102 a 1002, v desítkové soustavě to je 2, 6 a 4. Odtud je vidět, že jediným správným tahem je snížit počet kamenů v poslední hromádce na 4 kameny.

Ve hře (3,3,2) existuje vyhrávající strategie pro prvního hráče (Å(11,11,10)2Å s číslem (10)2 dostaneme (1,1,0). Tedy vyhrávající strategie spočívá v tom, že odebereme z první nebo druhé jeden kámen (zápalku), popř. z poslední hromádky jeden předmět. Ve hře (3,3,1) existuje vyhrávající strategie pro prvního hráče (Å(11,11,1)2 je nenulové), součtem Å s číslem (01)2 dostaneme (1,1,0). Tedy vyhrávající strategie spočívá v tom, že odebereme z první nebo druhé jeden kámen (zápalku), popř. z poslední hromádky jeden předmět.

Naopak, představme si n-hromádkový NIM, který již umíme vyřešit a postupně přisypávejme kameny na hromádky a pozorujme, jak se hodnota hry změní - z vyhrávající pozice na prohrávající pozici a naopak, popř. je možné vytvořit i stromeček všech logických možnosti. Na začátku budeme mít třeba pozici (....,0,1,0,....) tedy hru, kde existuje vyhrávající strategie pro prvního hráče. Přisypáme jedničku, to mužeme udělat i díky přemístění pořadí hromádek buď do nenulové hromádky, nebo nulové, dostaneme tak dvě možnosti: (....,0,10,0,...)2, nebo (....,0,1,1,0,...). Zatímco druhá hra je nulová, první hra je nenulová (zde ex. vyhrávající strategie pro prvního hráče)...

Jak to bude vypadat, budou-li na dvou hromádkách stejný počet kamenů? Pokud na dvou hromádkách bude po jednom kameni, první hráč odebere jeden kámen a druhý odebere poslední - první prohrál. Pokud bude na dvou hromádkách stejný počet kamenů, druhý hráč může kopírovat tahy prvního hráče (odebírá stejný počet kamenů z druhé hromádky), a tedy vyhrál.

Na závěr si ještě zahrajme NIM (3,5,1,8,7)10:

zpět