7. Konceptov Míňame Spústu vzorové riešenie

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čí.