Zadanie
Milý denníček,
dnes som bol za tými kozliatkami, ale nedopadlo to bohvieako. Samozrejme, kozliatka mi otvorili vrátka, tak som ich všetky zhltol. Taký som bol plný, že som sa nevládal pohnúť. Preto ma načapala mama koza vo svojom vlastnom dome a ľahko si domyslela, čo sa stalo. Chcel som sa vyhnúť bitke, nuž som povedal: „Prepáčte mi, mama koza, nevedel som, že sú vaše. Viete, ja som vegetarián, ja papám iba sirôtky.“ Uverila mi a všetko bolo odpustené, len som musel ísť na operáciu, aby mi kozliatka z brucha vytiahli.
V čakárni pred operáciou sme hrali s mamou kozou karty. Na nich boli celé čísla od \(1\) po \(2k\) vrátane, pričom každá kartička mala práve jedno číslo a žiadne dve kartičky nemali rovnaké. S mamou kozou sme si ich náhodne rozdelili na polovicu a hrali sme nasledovne:
Ja a mama koza sme sa striedali v ťahoch, pričom som začínal ja.
Hráč na ťahu musí vyložiť jednu kartičku s číslom \(m\) takú, že je \(m\) menšie ako všetky alebo väčšie ako všetky ostatné už vyložené kartičky. (Ak nie je na stole žiadna karta, tak hráč môže vyložiť ľubovoľnú.)
Ak hráč nemôže vyložiť na ťahu žiadnu kartičku, prehral. (Aj ak minul všetky svoje kartičky.)
Určte víťaznú stratégiu pre jedného z hráčov na základe začiatočného rozdelenia kariet.
Aby sa nám podarilo nájsť nejakú myšlienku pre riešenie, skúsime si vymyslieť jednoduchý príklad. Nech vlk má obidve kartičky \(1\) a \(2k\). On teda môže zahrať v prvom ťahu \(1\), potom mama koza zahrá čokoľvek, a vlk zahrá \(2k\) v druhom ťahu. Je očividné, že mama koza nevie zahrať kartičku menšiu ako \(1\) alebo väčšiu ako \(2k\) – čiže prehrala. Analogicky, keď by mama koza mala túto dvojicu, tiež by vyhrala – vždy vie zahrať aj \(1\), aj \(2k\), a vlk po jej ťahu nemôže vyložiť žiadnu kartičku.
Čiže aj intuitívne, aj s týmto príkladom nám môže prísť úvaha o tom, že okrajové kartičky sú „lepšie“, a pritom dôležitou je nie kartička sama o sebe, ale pár kariet.
Poďme sa pozrieť ďalej. Čo keď ale každý hráč má len jednu kartičku z dvojice \(1\), \(2k\)? Skúsime si tiež vymyslieť príklad. Nech vlk má kartičky \(1\), \(2\), \(5\), a mama koza má zvyšné \(3\), \(4\), \(6\). Keď vlk v prvom ťahu zahrá \(1\), tak mama koza vie hneď zahrať \(6\) a vyhrá. Nech teda vlk vyloží \(2\). Potom máme \(2\) možnosti:
Mama koza zahrá \(3\) alebo \(4\). Ďalej vlk zahrá \(5\), a mama koza už nebude môcť vyložiť zvyšnú kartičku z dvojice \((3,4)\), lebo sa obe nachádzajú medzi \(2\) a \(5\). Mama koza preto môže vyložiť len \(6\). Vlk vyloží \(1\) a mama koza už nemôže nič dokladať.
Mama koza hneď zahrá \(6\), teda vlk zahrá \(1\) a mama koza prehrá.
Čiže vlk vie vyhrať v tomto prípade bez ohľadu na to, čo zahrá mama koza. Analogicky, keď by kartičky boli vymenené, tak by aj mama koza mohla vyhrať skoro takisto (premyslite si to).
Takže, už máme niekoľko dôležitých myšlienok: symetrické dvojice kartičiek sú dôležité pre hráčov, pričom „lepšie“ sú viac vzdialené od stredu. Okrem toho, ten, kto má nejakú takú dvojicu, vyhrá bez ohľadu na to, kto začína. Skúsime teraz tieto myšlienky zovšeobecniť, upresniť a dokázať.
Urobme dvojice kartičiek \((1, 2k), (2, 2k-1), ..., (k, k+1)\), ktoré ďalej budeme volať „pár“. Skúsime vymyslieť a dokázať stratégiu pre toho hráča, ktorý má „najviac vzdialený pár“ kartičiek, alebo, presne povedané, takú dvojicu \((i, 2k+1-i)\), že \(1\leq i\leq k\), a pre všetky \(1\leq j < i\) žiaden hráč nevlastni dvojicu kartičiek \((j, 2k+1-j)\). Budeme hovoriť, že pár \((j, 2k+1-j)\) je „viac vzdialený od stredu“, keď \(j<i\).
Začneme vlkom. Nech on má najviac vzdialený pár. Pomenujeme ho \((i, 2k+1-i)\), pričom nech \(1\leq i\leq k\). Teda vlk, aby vyhral, môže postupovať nasledovne: začne hru tým, že vyloží jednu kartičku zo svojho páru, nech to bude \(i\). Ďalej sú \(2\) možnosti:
Mama koza vyloží kartičku \(j\) takú, že \(i < j < (2k+1-i)\), čiže vnútri vlkovho páru. Vlk potom môže vyložiť \((2k+1-i)\), lebo \((2k+1-i) > j > i\), čiže je väčšia ako všetky ostatné už vyložené kartičky.
Mama koza vyloží kartičku \(m_1\) takú, že \(m_1 < i\) alebo kartičku \(m_2\) takú, že \((2k+1-i) < m_2\). V oboch prípadoch, keďže vieme, že vlk má najviac vzdialený pár, a všetky páry, čo sú viac vzdialené, sú rozdelené medzi hráčmi, tak vlk musí mať kartičku, ktorá dopĺňa \(m_1\) alebo \(m_2\) do páru, ktorú môže vyložiť.
V oboch prípadoch, po \(2\) ťahoch oboch hráčov vedia zahrať len tie kartičky, ktoré sú viac vzdialené od stredu ako \((i, 2k+1-i)\) (v prvom prípade sú to práve všetky také kartičky, a v druhom sú to kartičky, ktoré sú viac vzdialené od stredu ako \((m_1, 2k+1-m_1)\) alebo \((2k+1-m_2, m_2)\)). Je to dôležité preto, lebo všetky také kartičky sú po pároch rozdelené, čiže práve jednu kartičku z každej takej dvojice má práve jeden hráč. To nám hovorí o tom, že na každý ťah mamy kozy vlk vie zahrať kartičku z toho istého páru, lebo keď mama koza zahrá kartičku \(n\), ktorá je menšia ako všetky, tak \(2k+1-n\) je väčšia, ako všetky. Naozaj, keď by to bolo inak, tak by existovala kartička \(2k+1-n' > 2k+1-n\), teda \(n'<n\), a z konštrukcie stratégie pre vlka by muselo vyplývať, že keď bola zahraná nejaká kartička, tak aj jej doplnok by musel byť zahraný. Teda mama koza by nemohla vyložiť \(n\), lebo už by bola zahraná kartička \(n'<n\). Analogický dôkaz vieme spraviť aj pre prípad, keď \(n\) je väčšie, ako všetky ostatné kartičky.
Takže, vlk vždy vie „symetricky“ dokladať kartičky z toho istého páru, z ktorého zahrala kartičku mama koza. Vlk teda nikdy neprehrá, čiže vyhrá.
Analogicky vieme sformulovať postup pre mamu kozu, keď má najviac vzdialený pár \((i, 2k+1-i)\):
Pokúsi sa vyložiť obidve kartičky zo svojho páru.
Keď vlk vyloží kartičku \(j\), že \(j<i\) alebo \((2k+1-i)<j\), tak mama koza vyloží doplnok tej kartičky do páru.
Potom, ak mama koza vyložila svoj pár, alebo jej v tom vlk zabránil a ona vyložila doplnok do ho kartičky, vedia už hrať len tie kartičky, ktoré sú viac vzdialené od stredu a sú rozdelené medzi hráčmi. Mama koza preto vždy vie vyložiť kartičku, ktorá je doplnkom do páru kartičky vlka. Vidíme preto, že mama koza vyhrá.
Zostalo nám prebrať ten prípad, keď nikto nemá najviac vzdialený pár. V tomto prípade platí skoro tá istá logika. Každý pár kartičiek je rozdelený medzi hráčmi, a teda na každý ťah vlka mama koza vie vyložiť kartičku, ktorá je z toho istého páru. V tomto prípade vyhrá mama koza.
Takže, keď niekto má najviac vzdialený pár, tak vyhrá bez ohľadu na to, kto začína. Ak nikto nemá najviac vzdialený pár, tak vyhrá mama koza.
Iné riešenie
Ak má mama koza obe z kariet \(1\), \(2k\), očividne môže každú z nich položiť v ktoromkoľvek ťahu. Zároveň, po tom, ako budú položené obe, zrejme už nie je možné uložiť žiadnu ďalšiu kartu. Znamená to, že mama koza ich vie uložiť v prvých dvoch svojich ťahoch bez ohľadu na to, či začína a následne vlk nevie ťahať, čím mama koza vyhrala. Analogickou argumentáciou v rovnakej situácii vyhrá aj vlk.
Zostáva teda prešetriť, čo sa deje vo zvyšnom prípade – a teda, keď každý z hráčov má práve jednu z kariet \(1\), \(2k\). Nech bez ujmy na všeobecnosti mama koza má kartu \(1\) a vlk kartu \(2k\). Pozrime sa teraz, koľko po sebe idúcich kariet od okraja majú u seba naši hráči. Povedzme, že mama koza má \(a\) kariet \(1\), \(2\), \(\dots\), \(a\), avšak kartu \(a+1\) už nemá a vlk má \(b\) kariet \(2k\), \(2k-1\), \(\dots\), \(2k-b+1\), avšak kartu \(2k-b\) už nemá. Je zrejmé, že obaja sú schopní tieto svoje okrajové karty zahrať bez ohľadu na to, čo bude robiť ich súper. Ostáva nám preskúmať, aké šance majú hrať karty zo stredu.
Každý z hráčov vie vo svojom prvom ťahu uložiť ktorúkoľvek kartu, lebo na to, aby niektoré karty nebolo možné vykladať, musia už byť vyložené aspoň dve karty. Znamená to, že vlk vie v prvom svojom ťahu uložiť kartu \(2k-b\), v druhom kartu \(a\) a následne už obaja môžu ukladať iba svoje okrajové karty. Tým vie vlk dosiahnuť, že mama koza bude schopná vyložiť najviac jednu kartu, ktorá nie je jej okrajová. Keďže vlk vyložil tiež jednu neokrajovú kartu, tak takouto stratégiou je schopný vyhrať za predpokladu, že vie vyložiť viac kariet ako mama koza, a teda \(b+1>a+1\), čo je ekvivalentné s \(b>a\).
Podobná stratégia funguje aj pre mamu kozu. Vtedy môže vlk teoreticky vyložiť dve svoje neokrajové karty, kým mu to mama koza znemožní. Mama koza zároveň touto stratégiou dokáže vyložiť okrem okrajových kariet jednu neokrajovú. Uvedomme si však, že keďže nezačína, na výhru jej stačí vedieť vyložiť aspoň toľko kariet ako vlk, čo dáva podmienku \(a+1\geq b+2\), čo je v celých číslach opäť to isté ako \(a>b\).
Mama koza teda vie vyhrať vždy, keď \(a>b\). Naopak, vlk vie vyhrať vždy, keď \(b>a\). Ostáva nám teda prešetriť prípad \(a=b\).
Uvedomme si, že akonáhle niektorý z nich zahrá niektorú svoju okrajovú kartu, jeho súper môže zahrať tú svoju najbližšie k stredu (ak tak doteraz neurobil). Odteraz už teda vedia hrať len svoje okrajové karty. A nakoľko \(a=b\), skôr sa ich zbaví ten, kto položil svoju okrajovú kartu ako prvý, a teda prehrá. Znamená to, že cieľom oboch hráčov je vyložiť svoju prvú okrajovú kartu neskôr ako súper. Vieme to interpretovať aj tak, že keďže ani jeden z nich nechce zahrať okrajovú kartu, tak akoby sme hrali bez nich. Potom totiž ten, kto nemôže vyložiť kartu, tak by síce mohol vyložiť niektorú svoju okrajovú kartu, no to vedie k tomu, že prehral. Vlk a mama koza teda hrajú s kartami \(a+1, a+2, \dots, 2k-a\). Keďže nezáleží na absolútnych hodnotách na kartičkách, iba na ich relatívnych veľkostiach, môžeme všetky hodnoty znížiť o \(a\). Tým dostaneme, že hrajú s kartami \(1, 2, \dots, 2(k-a)\), čo je rovnaká úloha ako predtým, len s menším počtom kariet.
Túto úlohu teda vieme vyriešiť rekurzívnou myšlienkou. Je zrejmé, že postupným zjednodušovaním otázky niekedy dosiahneme prípad, kedy buď \(a>b\) (a teda vyhrá mama koza), \(a<b\) (a teda vyhrá vlk) alebo \(a=b=k\). V opačnom prípade totiž stále môžeme úlohu postupom uvedeným vyššie zredukovať na jednoduchší prípad. Je zrejmé, že v prípade \(a=b=k\) vyhrá ten hráč, ktorý nezačína, pretože obaja sú schopní vyložiť všetky svoje karty bez ohľadu na súpera.
Suma sumárum teda dostávame, že vyhrá ten, kto má väčší počet okrajových kariet, pričom v prípade rovnosti tieto odstránime a otázku sa opýtame znova v menšom prípade, kým nedostaneme odpoveď. Ak sa takto zbavíme všetkých kariet, vyhrá ten, čo nezačínal.
Poznámky
Ako to, že sme sa dostali k dvom rôznym výsledkom? Ide totiž o to, že obe interpretácie sú ekvivalentné. Skúste si premyslieť, prečo.
Viacerým z vás v riešeniach chýbal poriadny popis, ako má hráč s víťaznou stratégiou hrať, aby zaručene vyhral. Toto je skoro vždy nevyhnutná súčasť riešenia a je to dobré napísať, aj keď táto stratégia z vašich ostatných úvah implicitne vyplýva.
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ť.