Na stole je hromádka n sirek a dva hráči s nimi hrají hru. Hráč na tahu musí odebrat jednu nebo dvě sirky. Kdo nemůže táhnout, prohrál. Určete, který z hráčů (začinající či ten druhý) má vyhrávající strategii (tj. umí si zajistit výhru bez ohledu na tahy soupeře). Řešte pro
Výsledek: Vyhrávající strategii má (a) ten druhý; (b) začínající; (c) začínající; (d) začínající hráč.
Dva hráči hrají hru na plánu s n soustřednými kružnicemi (jako na obrázcích). Střídavě vybarvují po jednom políčku. V prvním tahu se vybarví jedno z nejvíce vnějších políček. V každém dalším tahu se musí vybarvit políčko, které sousedí s posledně vybarveným ve směru jedné z šipek. Každé políčko lze vybarvit pouze jednou. Kdo nemůže táhnout, prohrál.
Pro hodnoty
odpovězte na následující otázky:
Výsledek: 1. Vyhrávající strategii má vždy druhý hráč. 2. (a) 12 (b) 18 (c) 30 (d) 6\cdot2014=12084. 3. (a) 6^2=36 (b) 6^3=216 (c) 6^5=7776 (d) 6^{2014}.
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.
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é.
Dva hráči opět hrají hru se sirkami. Tentokrát je na stole 15 sirek a hráč, který je na tahu si může vybrat, zda odebere 2, 3, nebo 4 sirky. Kdo nemá jak táhnout, prohrál. Rozhodněte, kdo má vyhrávající strategii.
Vyhrávající strategii má začínající hráč.
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.
Shrnutí: (V a P pozice) a naopak pozice, v nichž si umí zajistit bez ohledu na tahy protihráče výhru, nazveme V pozice.
Jak určíme, zda je počáteční pozice V nebo P? Jednoduše! V a P pozice lze vždy určovat „odspodu“ jako v následujícím obrázku pro první úlohu. V pozice jsou znázorněny zeleně (plnou barvou), P pozice červeně (šrafovaně).
Pro zajímavost uveďme, že v principu lze tímto způsobem určit, zda je počáteční pozice v šachu vyhrávající čí prohrávající. Větvení možností v šachu je ale natolik široké, že i pro nejrychlejší superpočítače je výpočet časově neúnosný. V roce 2012 se nicméně podařilo dokončit výpočet, který u každé šachové pozice se sedmi a méně figurami rozhodl, zda je V či P.