6. Koniec Mamutieho Šamana vzorové riešenie

Označme si prvú šachovnicu \(M\) a druhú \(R\). Akékoľvek prípustné rozmiestnenie figúrok na šachovniciach budeme volať stav hry.

Prvým typom ťahu môžeme vymeniť ľubovoľné dva riadky. To ale znamená, že na poradí riadkov nezáleží. Druhým typom ťahu môžeme povymieňať figúrky v prvých dvoch riadkoch, ak dodržíme zadané kritéria. Keďže na poradí riadkov nezáleží, tak kombináciou oboch typov ťahov môžeme vymeniť figúrky v ľubovoľných dvoch riadkoch. Preto si môžeme šachovnice rozbiť na jednotlivé riadky. Naším cieľom je teraz ukázať, že vieme dostať na \(M\) také isté riadky ako sú na \(R\).

Teraz dokážeme, že môžeme ťahať aj na \(R\). Presnejšie, dokážeme, že ak vieme vyhrať s ťahaním na \(R\), tak vieme vyhrať aj bez neho. Ak spravíme nejaký ťah na \(M\), vieme ho isto vrátiť späť, lebo je to opäť povolený ťah. Ak budeme ťahať na oboch šachovniciach a dostaneme sa do stavu, keď sú obe rovnaké, stačí nám potom ťahať na oboch šachovniciach spätne (keďže sú už obe rovnaké, tak robíme na oboch rovnaké ťahy) tak, aby sme dostali pôvodnú \(R\). Tým pádom sme ale na \(R\) nemuseli ťahať vôbec a vieme vyhrať aj bez ťahania na nej. Odteraz budeme preto ťahať na oboch šachovniciach. Mimochodom, trik s ťahaním späť často zjednoduší úlohu, preto je fajn si ho zapamätať.

Teraz sa pustime do samotného riešenia. Predpokladajme, sporom, že existuje stav hry, z ktorého nevieme vyhrať. Potom iste existuje aj takýto stav, v ktorom majú šachovnice najmenší počet riadkov. Navyše medzi nimi existuje aj stav, v ktorom existuje na \(M\) riadok, ktorý sa líši s nejakým riadkom \(R\) na najmenšom počte pozícií. Zoberme si tento stav hry. Keďže na poradí riadkov nezáleží, môžeme bez ujmy na všeobecnosti predpokladať, že prvý riadok \(M\) a prvý riadok \(R\) sú tie, ktoré sa líšia na najmenšom počte pozícií.

Pozrime sa na prípad, že prvý riadok \(M\) je rovnaký ako prvý riadok \(R\). Ak prvý riadok odstránime zo šachovníc, dostávame stav hry, v ktorom majú šachovnice menší počet riadkov a stále ho nevieme vyhrať, čo je spor. Ak totiž vieme vyhrať po odstránení riadku, potom vieme vyhrať aj keď pridáme rovnaký riadok, lebo s ním po celý čas nič neurobíme. Preto prvé riadky \(M\) a \(R\) musia byť rôzne.

Dva riadky, v ktorých je v oboch párny počet figúrok sa líšia na párnom počte pozícií. Keďže prvé riadky \(M\) a \(R\) sú rôzne, tak sa líšia aspoň na dvoch pozíciach. Bez ujmy na všeobecnosti, nech sa líšia v prvých dvoch stĺpcoch. Nech je to tak, že v prvom riadku \(M\) sú v prvých dvoch stĺpcoch dve figúrky a v prvom riadku \(R\) dve prázdne políčka.

Predpokladajme, že nejaký riadok \(M\) má v prvých dvoch stĺpcoch prázdne políčka. Potom môžeme dve figúrky z prvých dvoch stĺpcov prvého riadku presunúť do tohto riadku. Tým sme počet pozícií, v ktorých sa prvý riadok \(M\) a \(R\) líšia, zmenšili o dva. To je spor s voľbou nášho stavu hry.

Z toho vyplýva, že vo všetkých zvyšných riadkoch \(M\) máme aspoň v jednom z prvých dvoch stĺpcoch figúrku. Potom je v týchto stĺpcoch spolu aspoň \(m+1\) figúrok. Rovnako na \(R\) nemôžu byť v prvých dvoch stĺpcoch dve figúrky v jednom riadku, inak by sme ich vedeli presunúť do prvého riadku (teraz využívame, že môžeme ťahať aj na \(R\)). Preto je na \(R\) v prvých dvoch stĺpcoch aspoň \(m+1\) prázdnych políčok, čo je najviac \(m-1\) figúrok. To je v spore s tým, že v každom stĺpci na \(M\) a \(R\) je rovnaký počet figúrok.

Môžete si rozmyslieť, že ak prvé dva stĺpce prvého riadku \(M\) vyzerajú inak, tak opäť podobnými úvahami dospejeme k sporu. Napríklad, ak by bola v prvom stĺpci figúrka a druhý by bol prázdny, tak by sme sčítali počet figúrok v prvom a počet prázdnych miest v druhom stĺpci. Tým sme ukázali, že náš „najmenší“ stav hry, v ktorom nevieme vyhrať neexistuje, a preto vieme vyhrať vždy.