Hry I

1. (a) Ukážeme, že vyhrávající strategii má druhý hráč. Na soupeřův první tah zareaguje tak, aby po jeho tahu na stole zůstaly tři sirky (to může vždy učinit). Po druhém soupeřově tahu pak může odebrat všechny zbývající sirky (tedy jednu, nebo dvě) a tím odsoudit soupeře k prohře.

2. (b) Zde má vyhrávající strategii první hráč. Klíčové je, aby v prvním tahu odebral dvě sirky. Poté můžeme situaci analyzovat podobně jako v části (a), anebo si můžeme uvědomit, že jsme v předchozí úloze o situaci, v níž na stole leží 6 sirek, ukázali, že je pro táhnoucího hráče bezvýchodná (hraje-li soupeř správně).

3. (c) Zde už se hodí odpozorovat, že klíčovou roli hrají násobky tří. Tvrdíme, že první hráč vyhraje, pokud začne odebráním jedné sirky. Pak bude na stole 9 sirek, tedy násobek tří. Pro prvního hráče pak není problém zařídit (podobně jajko v části (a)), aby po jeho dalším tahu bylo na stole přesně 6 sirek (opět násobek tří). Posléze 3 a nakonec 0 (opět podobně jako v části (a)).

4. (d) Myšlenku z předchozí úlohy dále rozvedeme. Pokud se prvnímu hráči podaří, aby počet sirek na stole po jeho tahu byl násobek tří, má již zajištenu výhru. Na každý tah soupeře, bude odpovídat tahem opačným (na jedničku dvojkou, na dvojku jedničkou). Takto po každé výměně klesne počet sirek přesně o tři tedy na nižší násobek tři. Tím časem dospějeme k devíti, šesti či třem sirkám na stole až nakonec první hráč odebere poslední sirku a vyhraje. Zbývá dopočítat, že 2013 je násobek tří, a vidíme, že první hráč vyhraje, odebere-li na začátku jednu sirku (a posléze hraje podle popsané strategie).

1. (1) Ukážeme, že vítěznou strategii má vždy druhý hráč. Začněme případem $n= 2$. Uvědomíme si, že hráč, který jako první sestoupí do vnitřního kruhu, již zákonitě prohraje. Po dalších pěti tazích, tedy v momentě, kdy dojdou přípustné tahy, bude totiž na tahu opět on. Oba z hráčů se tedy snaží maximálně oddálit sestup do vnitřní úrovně. Ten se pak ale odehraje přesně v sedmém tahu, a zahraje jej tak první hráč, který nutně prohraje.

   Pro vyšší hodnoty $n$ budeme uvažovat obdobně. Druhý hráč se opět bude snažit za každou cenu vyhnout sestupu na nižší úroveň, a jelikož je v každé úrovní šest, tedy sudý počet, polí, bude se mu tato strategie dařit. Nakonec tedy první hráč sestoupí do nejvíce vnitřní úrovně a posléze prohraje.

2. (2) Z výše uvedených úvah plyne, že oba hráči se budou snažit oddálit sestup do každé z nižších úrovní. Tímto způsobem vyplní celý hrací plán, který má přesně $6 n$ polí. Jelikož jedním tahem vyplní přesně jedno pole, je $6n$ i odpovědí na zadanou otázku.

3. (3) Určujícími pro průběh hry jsou políčka, která budou jako první vybarvena v každé úrovni. Ukážeme, že počet průběhů hry je totožný s počtem způsobů, jak v každé úrovni vybrat „začínající“ políčko. Tím úlohu vyřešíme, jelikož druhý počet možností je přesně $6^n$.

   Vyberme v každé úrovni jedno políčko. Podstatné je, že poté lze celý průběh hry jednoznačně zrekonstruovat. V každé úrovni totiž víme, odkud a kam máme vybarvovat, což určuje potřebné tahy jednoznačně. Víme tedy, že každé vybarvení odpovídá nějakému a pokaždé jinému průběhu hry. Zbývá si uvědomit, že není žádný průběh hry, na který by se tímto způsobem nedostalo. Nyní je zřejmé, že oba počty jsou stejné.

Ukážeme, že vítěznou strategii má první hráč.

Inspirování první úlohou, začněme nejprve u menších případů. První zajímavý případ nastává, je-li na stole šest sirek. Tehdy totiž vítězí druhý hráč, a to tak, že ve svém tahu odebere všechny zbylé sirky (těch je 3,4, nebo 5). Tato pozice je pro hráče na tahu tedy prohrávající.

Pokud bychom po prvním tahu mohli druhého hráče do této pozice postavit, měli bychom již víteznou strategii. To ovšem nelze a musíme tak zapátrat o krok dále. Odtušíme, že klíčové v této úloze budou násobky šesti. Je-li na stole například 12 sirek, může netáhnoucí hráč zajistit, aby se počet sirek po následující dvojici tahů snížil přesně o šest (stejně jako v prvním odstavci). Tedy na další nižší násobek šesti, což je v našem případě šest sirek, což je pro táhnoucího hráče jistá prohra. I dvanáct sirek je tak pro hrajícího hráče prohraná pozice.

Strategie prvního hráče je již jasná. Odebere tři sirky a postaví tak druhého hráče do prohrávající pozice.

Podobným uvažováním o vyhrávajících a prohrávajících pozicích lze odzadu rozřešit mnoho podobných úloh. Více ve shrnutí na konci hodiny.