9. príklad - Vzorové riešenie

Rozdelíme si úlohu na dva prípady podľa toho, či je N párne. Ak je totiž N nepárne, výhru si vie Lukáš zaručiť jednoducho:

Lukáš bude začínajúci hráč a pridá jednu kostičku. Tým bude na kôpke nepárny počet kostičiek. Či už pútnik pridá jednu kostičku alebo vynásobí počet kostičiek dvomi, po jeho ťahu bude na kôpke párny počet kostičiek. To platí pre akýkoľvek nepárny počet kostičiek na kôpke. Potom Lukáš zase pridá 1 kostičku, čím vytvorí nepárne číslo. Takto sa budú striedať, až kým Lukáš nepoloží N-tú kostičku. Položí ju on, lebo pútnik nemá ako zabrániť tomu, aby po Lukášovom ťahu bol na kôpke nepárny počet, lebo vždy dostane nepárny počet z neho musí urobiť párny.

Ak je N párne, už nevidíme takú priamočiaru stratégiu, preto sa budeme musieť na hru pozrieť viac systematicky. Budeme sa pozerať na to, ktoré pozície sú vyhrávajúce a ktoré prehrávajúce (pozíciou sa myslí stav hry, teda to, aký počet kostičiek je na kôpke, keď ideme urobiť ťah).

Prvá prehrávajúca pozícia je, keď je na kôpke N kostičiek. Vtedy už nemôžeme urobiť ťah. Pozícia s N-1 kostičkami je zase vyhrávajúca, lebo vieme súpera dostať do prehrávajúcej tým, že pridáme 1 kostičku. Podobne aj pozícia s \frac{N}2 kostičkami, lebo vieme zdvojnásobiť počet kostičiek a súper opäť prehráva. Všeobecne platí, že ak sa vieme z pozície dostať ťahom na prehrávajúcu, je vyhrávajúca. Ak však nevieme súpera dostať do situácie kedy zaručene prehrá, teda sa vieme dostať iba na vyhrávajúce, tak je prehrávajúca. 

Takúto úvahu má zmysel robiť, pretože hra je "priamočiara" - nemôžeme sa vrátiť späť do nejakej minulej pozície. Preto sa dá určiť, či je každá pozícia vyhrávajúca alebo nie tým, že pôjdeme od konca. Ak poznáme stav všetkých pozícií, na ktoré sa vieme dostať, použijeme na určenie vyššie opísané pravidlo.

Pre počty medzi \frac{N}2 a N vieme tiež jasne určiť, či hráč na ťahu vyhrá, teda či sú vyhrávajúce alebo prehrávajúce. Hráči totiž už nemôžu násobiť dvomi, musia iba pridávať 1 kostičku. Hráč, ktorý je v pozícii s hocijakým párnym počtom kostičiek väčším ako \frac{N}2 sa už nevie dostať do pozície s nepárnym počtom kostičiek, pretože pridaním 1 kostičky vytvorí nepárne číslo a jeho súper potom zasa párne. Teda to bude práve jeho súper, ktorý na konci dosiahne N. Všetky párne pozície väčšie ako \frac{N}2 sú teda prehrávajúce (a všetky nepárne vyhrávajúce).

Ale čo ak na ťahu máme menej kostičiek? Kedy vieme dostať súpera do prehrávajúcej pozície? Vieme už, že všetky párne pozície väčšie ako \frac{N}2 sú prehrávajúce. Takže ak dostaneme hocijaké číslo väčšie ako \frac{N}4, ale nanajvýš \frac{N}2, môžeme ho zdvojnásobiť. Tým vytvoríme súperovi jednu z prehrávajúcich pozícií a on nakoniec prehrá.

Máme teda "vyhrávajúce pásmo" ktoré obsahuje všetky pozície nad \frac{N}4 do \frac{N}2. Toto pásmo je zaujímavé tým, že sa nedá preskočiť - vždy aspoň jeden hráč musí vytvoriť takúto pozíciu. Aj keby na ťahu mal najväčšie menšie číslo a zdvojnásobil by ho, nad toto pásmo sa nedostane. Hráč ktorý toto urobí zároveň aj prehrá, lebo dostane súpera do vyhrávajúcej pozície. Tým že hráči nesmú presiahnuť \frac{N}4, môžeme si povedať, že pôvodná hra s N je ekvivalentná tomu, akoby hráči hrali iba s maximom M=\lfloor \frac{N}4 \rfloor (zápis znamená zaokrúhlenie nadol, číslo \frac{N}4 nemusí existovať, ale hľadáme najväčšie, ktoré nie je väčšie). Nemajú síce zakázané robiť ťahy ktoré toto číslo presiahnu, ale zaručia si tým prehru.

Ak je M nepárne, Lukáš dokáže vyhrať stratégiou, ktorá je opísaná v prvej časti riešenia. Ak je číslo párne, musíme zopakovať úvahu o stratégii pre párne N. Zistíme teda, že pozícia \lfloor \frac{M}4 \rfloor je prehrávajúca a pozrieme sa, ako na ňu vie Lukáš dostať pútnika. Teda v prípade potreby zase úvahu opakujeme.

Ak v tomto procese narazíme na nepárne číslo, môžeme poradiť Lukášovi, že má začínať, aby naň vedel dostať súpera neustálym pričítavaním 1. Po dosiahnutí tohto nepárneho čísla (alebo keď ho pútnik presiahne) už pokračuje tak, aby vždy išiel na prehrávajúce pozície tak, ako sme ich opísali. 

Môže sa ale stať, že budú všetky čísla párne? Pri operácii delenia kladného čísla 4 a prípadnom zaokrúhlení sa číslo vždy musí zmenšiť, a teda jediná možnosť, ako by sme mohli mať samé párne čísla je, že sa eventuálne dostaneme na 0. To nám hovorí, že byť na ťahu s 0 kostičkami na kôpke je prehrávajúce, a teda Lukáš by nemal začínať.

Odpoveď: Lukáš by mal začínať, ak je N nepárne alebo ak sa opakovaným delením N štyrmi a zaokrúhľovaním nadol dostaneme na nepárne číslo. Lukáš vie na dané nepárne číslo súpera dostať tak, že vždy bude iba pridávať 1 kostičku. Potom zdvojnásobuje iba vtedy, ak jeho súper v predošlom ťahu práve presiahol jedno z čísel ktoré opakovaným delením vzniklo.