*Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na *

Kika s Andrejom išli spolu na výlet do Tatier. Prenajali si malú chatku uprostred hôr, z ktorej sa každý deň chystali chodiť na rôzne horské túry. Avšak hneď v prvý deň ráno začalo strašne pršať a nikam ísť nemohli. Ostali teda uväznení na chate, a keďže tam nebol žiaden signál, začali sa strašne nudiť.

Snažili sa teda nájsť čokoľvek, čím by sa mohli zabaviť. Ale jediná vec, ktorú našli, bola stará šachovnica s figúrkami. Ani jeden z nich však nevie hrať šach, akurát vedia ako sa hýbu jednotlivé figúrky, preto si vymysleli nasledovnú hru.

Na niektoré políčko šachovnice položia figúrku koňa. Následne sa striedajú v ťahoch – ťah spočíva v tom, že hráč presunie koňa podľa šachových pravidiel na iné políčko šachovnice. Naviac musí platiť, že v každom ťahu sa kôň posunie bližšie k ľavému dolnému rohu šachovnice. Formálne, očíslujme si riadky šachovnice odspodu po vrch číslami 1 až 8 a stĺpce šachovnice zľava doprava číslami 1 až 8. Potom musí platiť, že každým ťahom sa súčet súradníc, na ktorých stojí kôň zmenší. Na nasledujúcom obrázku si môžete pozrieť všetky možné ťahy, ktoré môže šachový kôň spraviť – kôň sa pohybuje v L-ku, ktorého ramená sú dĺžky 3 a 1. Štyri z týchto ťahov sú prípustné (označené zelenou fajkou), lebo zmenšujú súčet súradníc a štyri z nich sú nepovolené (označené červeným krížikom). Samozrejme, ak sa kôň nachádza na kraji šachovnice, niektoré z ťahov hráč nemôže spraviť, lebo by dostal koňa mimo šachovnicu.

Hráč, ktorý už koňom nemôže pohnúť (lebo sa nachádza v niektorom zo 4 políčok v ľavom dolnom rohu) prehráva. No a keďže Andrej je gentleman, Kika začína ako prvá.

Úloha

1. (3 body) Na obrázkoch nižšie sú zobrazené dve možné začiatočné pozície. Pre každú z nich rozhodnite, ktorý hráč vie zvíťaziť, ak budú hrať obaja optimálne. Pýtame sa teda, ktorý z hráčov vie vyhrať bez ohľadu na to, aké ťahy spraví jeho protivník. Pre obe situácie popíšte aj spôsob, akým vie daný hráč vyhrať.

1. (7 bodov) Pre každú pozíciu šachovnice $8\times 8$ zistite, či sa podarí Kike zvíťaziť, ak bude kôň na začiatku na tejto pozície. Výsledok zapíšte do tabuľky $8\times 8$, kde na pozíciu, z ktorej Kika vie vyhrať zapíšete číslo 1 a na pozíciu, z ktorej Kika prehrá zapíšete 0. Teda štyri políčka v ľavom dolnom rohu budú obsahovať 0, pretože ak sa na ne položí kôň, Kika nebude môcť spraviť žiaden ťah a prehrá.

Popíšte, akým spôsobom ste túto tabuľku vypĺňali a zdôvodnite, prečo je váš postup naozaj dobrý. Potom sa pokúste zovšeobecniť váš postup aj pre šachovnice ľubovoľných rozmerov – teda veľkosti $r\times s$. Skúste preto popísať sadu pravidiel, podľa ktorých by ste vedeli vyplniť ľubovoľne veľkú tabuľku.

2. (5 bodov) Keď ich táto verzia prestala baviť, hru si ozvláštnili tým, že na šachovnicu položili viacero koní (kľudne aj viac ako štyroch). V jednom ťahu si mohol hráč vybrať ľubovoľne veľa koní (ale aspoň jedného) a každého z nich posunúť podľa predošlých pravidiel. Nevadilo dokonca ani to, ak sa viacero koní ocitlo na tom istom políčku.

Pomôžte Kike nájsť spôsob akým môže vyhrať, poprípade zistite, že vyhrať nevie. Napíšte teda postup, ktorým sa má v každom kroku riadiť. Tento postup musí byť dosť všeobecný, aby sa dal použiť pri ľubovoľnej situácii, ktorá na šachovnici nastane. Pri riešení môžete použiť tabuľku z podúlohy b).