5. Ktovieaký Macauský Stopár $\left(\kappa \le 6\right)$
Zadanie
Po mori sa odboj preplavil až do Macaa. Po ceste zjedli všetky zásoby vrátane kožušín a snehu, no i tak boli vyhladovaní. V Macau teda predali loď, aby sa mali za čo najesť. Matúšovi Móricovi Michalovi Františkovi Serafínovi Augustovi sa už cnelo za domovom, tak sa rozhodol, že si stopne nejakú loď do Európy. Po dvoch dňoch státia s vystrčeným prstom v prístave sa nad ním zľutovala posádka jednej francúzskej lode a vzala ho na cestu do Lorientu.
Matúš Móric Michal František Serafín August už bol z toho všetkého cestovania znudený. Našťastie boli na lodi námorníci, nanešťastie sa chceli hrať iba kocky a na tie mu už nezostali peniaze. On si však vystačí aj sám.
Hracia plocha je $n$-uholník. Matúš a Móric sa striedajú v ťahoch, pričom začína Matúš. Vo svojom ťahu zafarbí hráč jeden dosiaľ nezafarbený vrchol namodro alebo nazeleno tak, aby žiadne dva vrcholy rovnakej farby nesusedili. Ak niekto nemá ako spraviť ťah, prehráva. V závislosti na $n \geq 3$ určte, či má víťaznú stratégiu Matúš, alebo Móric, a vysvetlite aká je.
Opravovatelia
Kopy [email protected]
Adri [email protected]
Spôsobov, ako sa dala riešiť táto úloha je viacero. Ukážeme si dva najčastejšie.
Rozdeľme si úlohu na dve možnosti podľa toho, či $n$ je párne, alebo nepárne.
Ak je $n$ párne, tak si Móric môže nakresliť pomyselnú os symetrie podľa ktorej bude hrať (ako na obrázku).
****
Ak teraz zahrá niekde Matúš nejaký ťah, tak ho on podľa tejto osi symetrie môže skopírovať s opačnou farbou na druhú stranu.
Nech sme teda v situácií, ktorá je symetrická podľa tejto osi symetrie, len s vymenenými farbami. Potom Matúš zahrá nejaký ťah. Keďže tento ťah bol legálny, tak legálny ťah bude aj zahranie opačnej farby na opačnú stranu. Tým získame opäť symetrickú situáciu. Toto sa stane aj v prípade, že je to vrchné alebo spodné políčko nášho plánika, lebo síce políčku, ktoré chceme ofarbovať, pribudol ofarbený sused, ale keďže chceme ofarbovať opačnou farbou, môžeme to spraviť.
Týmto spôsobom môže Móric vždy zahrať ďalší ťah a teda Matúš musí nutne prehrať.
Nech $n$ je nepárne. Matúš niekde zafarbí prvé políčko. Následne si Móric môže otočiť hrací plán tak, aby toto políčko bolo políčkom $A$ na hracej ploche a spraviť si pomyselnú os symetrie cez políčko $B$ a uplatniť cez túto os symetrie rovnakú stratégiu ako v prvej časti. Začne teda tým, že políčko $C$ zafarbí opačnou farbou, ako Matúš zafarbil políčko $A$.
****
Keďže políčko $B$ sa už nedá ofarbiť, tak z rovnakého princípu stačí Móricovi „kopírovať“ Matúšove ťahy a má zaručené, že vždy bude môcť zahrať ďalší ťah a vyhrá.
V oboch prípadoch má teda Móric víťaznú stratégiu.
Iné riešenie.
Pozrime sa, ako bude vyzerať hracia plocha po skončení hry. Špecificky sa pozrime na to, ako budú vyzerať políčka okolo voľných políčok. Na to, aby sa na takéto voľné políčko už nedal zahrať ťah, potrebujeme, aby okolo neho bolo z jednej strany modré políčko a z druhej zelené, inak by sa naň ešte dal zahrať nejaký ťah.
Vedľa zelených políčok môžu byť len prázdne alebo modré políčka, prípadne ich kombinácia. Podobne pre modré políčka.
Takže keď si odmyslíme všetky prázdne políčka, tak zvyšné políčka, ktoré budú po novom vedľa seba, sa budú striedať: „modrá, zelená, modrá, zelená…“.
Keďže tieto políčka idú do kruhu, tak tam musí byť rovnaký počet zelených a modrých políčok, a teda musí byť odohraný párny počet ťahov. Z toho vyplýva, že posledný ťah spravil Móric, lebo Móric robil párne ťahy, a teda už Matúš nemohol ďalší ťah pridať.
Z toho vyplýva, že Móric ani nemusel mať nijakú stratégiu, aby vyhral. Stačilo mu len hrať validné ťahy.
