Opravovatelia

Mišo M. [email protected]

Mati [email protected]

Odbime si na začiatok víťazné pozície. Ak bude pred Davidovym ťahom na kôpke len $1$ šmirák, David ho vezme a vyhrá. To napríklad znamená, že pre $n = 1$ vyhráva on. Naopak, ak po jeho ťahu budú na kôpke $1$ alebo $2$ šmiráky, Lukáš si šmirák vezme, a ak na kôpke nejaký ostal, vezme si ho Teri. Vyhrá teda niekto z nich. Pre jednoduchosť budeme hovoriť, že v takejto situácií David prehral.

Predchádzajúci odsek nám dáva ešte jedno pozorovanie. Ak pred Davidovým ťahom sú na kôpke $2$ alebo $3$ šmiráky, David musí šmirák na kôpku pridať. Inak by na kôpke ostali menej ako tri šmiráky a prehral by.

Čo ďalej? Zatiaľ sme úlohu vyriešili len pre $n = 1$. Po chvíli rozmýšľania prídeme na to, že pre $n = 2$ David prehrá. Na začiatku musí šmirák pridať na kôpku a keď Lukáš $1$ šmirák pridá a Teri $1$ odoberie, budú pred Davidom $3$ šmiráky. Podľa postupu vyššie by mal šmirák na kôpku pridať, no v ruke žiaden nedrží. Šmirák teda z kôpky odoberie a prehrá.

Situácia pre $n = 2$ nám čo-to napovedá o situácii pre vyššie počty šmirákov. Vidíme, že Lukášovi s Teri sa oplatí znížiť počet šmirákov na kôpke na $2$ alebo $3$ a následne sa pokúsiť Davida obrať o šmiráky na ruke. Tým by si mohli zaistiť, že vyhrá niekto z nich.

Časť so znižovaním počtu šmirákov na kope je jednoduchá. Ak sú po Davidovom ťahu na kôpke aspoň $4$ šmiráky, Lukáš aj Teri si po jednom vezmú. Bez ohľadu na to, čo spravil David, bude pred jeho ďalším ťahom na kôpke aspoň o $1$ šmirák menej než minule. Keďže na kôpke boli po Davidovom ťahu aspoň $4$ šmiráky, pred jeho najbližším ťahom budú aspoň $2$. Najviac po $n - 3$ kolách teda Lukáš s Teri dosiahnu $2$ alebo $3$ šmiráky na kôpke. Ak to bude pred ich ťahom, tak pre $2$ šmiráky rovno vyhrá jeden z nich. Pre $3$ šmiráky zas vie jeden z nich šmirák pridať a druhý odobrať, čím dostanú $3$ šmiráky pred Davidovým ťahom. Tu sa oplatí ešte spomenúť, že to naozaj vedia spraviť. Keďže doteraz šmiráky len brali, určite má niekto z nich¹ na ruke šmirák, ktorý na kôpku môže položiť. Ten druhý šmirák vezme.

Takže vieme, že Lukáš s Teri určite vedia po konečnom počte ťahov zabezpečiť, že pred Davidovým ťahom sú na kôpke $2$ alebo $3$ šmiráky. Ľahko si všimneme, že Davida vedia v tomto stave udržiavať ľubovoľne dlho. Aby David neprehral, musí šmirák na kôpku pridať, čím pred Lukášom s Teri budú $3$ alebo $4$ šmiráky. V druhom prípade si každý vezme $1$ šmirák a pred Davidom budú $2$. V prvom prípade vie jeden z nich šmirák na kopu dať a druhý odtiaľ vziať (nie nutne v tomto poradí). Pred Davidovým ťahom tak budú $3$ šmiráky.

Takže pred Davidovym ťahom budú na kôpke striedavo $2$ a $3$ šmiráky. V každom ťahu teda musí jeden šmirák z ruky dať na kopu. Keď sa prvýkrát ocitol v tomto cykle, mal obmedzený počet šmirákov na ruke. Označme tento počet $d$. Po $d$ ťahoch, v ktorých bol prinútený dať šmirák na kôpku, mu v ruke žiaden nezostane. Bude si teda musieť jeden z $2$, resp. $3$, šmirákov zobrať a prehrá. Jedinou jeho nádejou by bolo, ak by sa mu podarilo prinútiť Lukáša s Teri prerušiť cyklus. Zo $4$ šmirákov si vedia zobrať dva vždy. Na to, aby si nemohli jeden šmirák zobrať a druhý šmirák na kôpku priložiť, museli by byť obaja bez šmirákov. To však nastať nemôže. V každom ťahu doteraz si totiž aspoň jeden z nich šmirák vzal. Ten, kto si šmirák vzal v minulom kole, ho isto môže v tomto položiť na kôpku. David teda s prehrou nič nenarobí.

Odpoveď

Pre $n = 1$ vyhráva David tým, že hneď na začiatku zoberie jediný šmirák z kopy. Pre $n > 1$ vyhrávajú Lukáš s Teri. Ich stratégia sa odvíja od počtu šmirákov na kope po Davidovom ťahu. Ak sú tam $3$, jeden z nich si šmirák vezme a druhý šmirák na kôpku dá. Ak sú na kôpke $2$ alebo aspoň $4$, obaja si šmirák zoberú. Ak je na kôpke $1$ šmirák, vezme si ho Lukáš a hra skončí.