Zadanie
Keď Danteho nebavilo riešiť problémy iných, tak si vyrazil do lokálneho kasína ošklbať niekoho o peniaze. Dnes bola v ponuke takáto hra:
Dvaja hráči – jeden naľavo a jeden napravo – hrajú hru. Pre potreby hry je na stole vyložených \(2020\) červených, \(2020\) zelených a \(2020\) modrých žetónov. Začína hráč napravo od žetónov, ktoré sú uprostred stola. Potom sa hráči striedajú v ťahoch. V jednom svojom ťahu si hráč zoberie zo stola aspoň jeden žetón, avšak nesmie si zobrať viac ako jeden žetón rovnakej farby. Vyhráva ten hráč, ktorý zoberie úplne posledný žetón zo stredu stola. Kam si má Dante sadnúť, aby mal proti svojmu súperovi víťaznú stratégiu? Svoje tvrdenie zdôvodnite.
Poznámka: Víťazná stratégia znamená, že hráč vie voliť také ťahy, aby vyhral bez ohľadu na to, aké ťahy vykonáva jeho súper.
Stav hry budeme označovať trojicou prirodzených čísel \((C,Z,M)\), kde čísla \(C\), \(Z\), \(M\) označujú počet červených, zelených a modrých žetónov na stole. Hra začína v stave \((2020,2020,2020)\) a končí, keď niektorý z hráčov dosiahne stav \((0,0,0)\).
Úlohy, v ktorých je potrebné nájsť víťaznú stratégiu sa obyčajne riešia od konca. Budeme hovoriť, že stav hry je vyhrávajúci, ak hráč na ťahu vie z tohto stavu zaručiť svoju výhru. Inak je stav prehrávajúci.
Zrejme stavy \((1,0,0)\), \((1,1,0)\), \((1,1,1)\) a ich permutácie sú vyhrávajúce, pretože hráč na ťahu môže zobrať všetky žetóny a ihneď vyhrať. Ďalej vieme zistiť, že \((2,0,0)\) je prehrávajúci stav, pretože jediný dovolený ťah nás dostane do stavu \((1,0,0)\). Avšak to je zle, pretože z tohto stavu vie náš súper vyhrať. Analogicky pre permutácie, t.j. stavy \((0,2,0)\) a \((0,0,2)\). Následne stavy \((2,1,0)\), \((2,1,1)\), \((3,1,0)\) a \((3,1,1)\) sú vyhrávajúce. Môžeme totiž zobrať žetóny tak, aby sme skončili v stave \((2,0,0)\). Z tohto stavu totiž nemôže súper vyhrať, a preto vyhráme my.
Takto môžeme postupovať až do nekonečna. Trvalo by nám však dlho, kým by sme sa dostali do stavu \((2020,2020,2020)\). Namiesto toho je užitočné všimnúť si vo vyhrávajúcich pozíciach nejaký vzor. Tu to vôbec nie je ťažké. Ak si vypíšeme dostatočne veľa pozícii, môžeme ľahko odhadnúť, že prehrávajúce sú práve tie pozície \((M,Z,C)\), kde všetky tri \(M,\ Z,\ C\) sú párne. Z toho vyplýva, že víťazná stratégia spočíva v tom, že budeme hrať tak, aby vždy po našom ťahu boli \(M,\ Z\) aj \(C\) párne. Toto musíme aj dokázať.
Ak je súper na ťahu a \(M,\ Z,\ C\) sú párne, tak musí zobrať aspoň jeden žetón, a preto po jeho ťahu bude určite aspoň z jednej farby na stole nepárny počet žetónov. Následne my môžeme zobrať žetóny tých farieb, z ktorých je na stole nepárny počet. Tým sa znova dostaneme do situácie, kde \(M,\ Z,\ C\) sú párne. Navyše súper nemôže vyhrať, lebo po jeho ťahu bude vždy aspoň z jednej farby nepárny počet žetónov. Preto nikdy nemôže dosiahnuť stav \((0,0,0)\). Keďže hra určite skončí, tak musíme vyhrať my.
Hra začína v stave \((2020,2020,2020)\), ktorý je prehrávajúci, preto Dante musí ísť druhý a postupovať vyššie opísanou stratégiou.
Poznámka: Opísať stratégiu v tejto konkrétnej úlohe bolo o dosť jednoduchšie. Funguje napríklad stratégia zopakovať ťah predchádzajúceho hráča. V skutočnosti je to tá istá stratégia, ktorú sme opísali v našom riešení. My sme chceli ukázať postup, ako sa na stratégiu dá prísť, v komplikovanejších úlohách.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.