5. Kúpim Majstrovskú Stratégiu $\left(\kappa \le 8\right)$ vzorové riešenie

Návod, ako prísť na dôležité fakty

Najprv si vyskúšame, čo sa stane, keď hráme hru na šachovnici \(2\times 2\). Očividne prehrá ten hráč, ktorý začína, pretože nemá miesto, kam posunúť svoju vežu. Tí, čo teraz očakávajú šachovnicu \(3\times 3\), si budú musieť trochu počkať.

Hrajme na šachovnici \(n\times n\) a predpokladajme, že sa hra dostala v nejakom momente do bodu, že biela veža a čierna veža sú obe na podšachovnici¹ \(2\times 2\), samozrejme diagonálne oproti sebe. Táto pozícia je tiež prehrávajúca pre začínajúceho hráča (pokračujúceho – pretože sa pozeráme na situáciu uprostred hry). Prečo? Nech je začínajúci (pokračujúci) hráč na políčku \((a,b)\) a svoju pôvodnú štartovaciu pozíciu mal na \((1,1)\). Potom začínajúci (pokračujúci) hráč má možné ťahy: ísť o \(x \in \{1,\dots, a-1\}\) jedným smerom alebo o \(y \in \{1,\dots, b-1\}\) druhým smerom. Dokopy teda má na výber z \(a+b-2\) ťahov. Teraz však protihráč spraví rovnaký ťah o \(x\) resp. \(y\) v tom istom smere a dosiahne situáciu, kde sú opäť na podšachovnici \(2\times 2\), a pôvodne začínajúci, teraz už pokračujúci, hráč je opäť na ťahu. Miesta, kam sa môže veža pohnúť, bude v každom ďalšom ťahu menej, keďže každým ťahom sa k okrajom šachovnice posunie bližšie. Takto to však nemôže pokračovať do nekonečna, pretože počet možností \(a+b-2\) sa bude stále zmenšovať, až začínajúci (pokračujúci) hráč skončí na \((1,1)\) a prehrá. Podobne sa dá argumentovať aj prípad, kedy hráčova štartovacia pozícia je \((n,n)\).

Dobre teda, takže ak niekto vie dosiahnuť vo svojom ťahu podšachovnicu \(2\times 2\) a nechať na ťahu súpera, tak vyhral. Ako to môže niektorý hráč docieliť? Podšachovnicu \(2\times 2\) vieme jedným ťahom vytvoriť z ľubovoľnej podšachovnice \(2 \times k\) alebo \(k \times 2\) pre ľubovoľné \(k \in \{3, 4, \dots n\}\). Takže všetky tieto pozície sú vyhrávajúce pre hráča, ktorý bude na ťahu na podšachovnici \(2 \times k\) alebo \(k \times 2\).

Dobre, takže čo s tou šachovnicou \(3\times 3\)? Hráč, ktorý začne, musí z tejto šachovnice nutne vytvoriť buď pozíciu \(2\times 3\) alebo \(3\times 2\). Preto šachovnica \(3\times 3\) je prehrávajúca pre začínajúceho hráča. Tak, ako sme v druhom odstavci dokázali, že „ustupovanie“ pre podšachovnicu \(2\times 2\) nezmení prehrávajúcosť pozície, tak aj pre podšachovnicu \(3\times 3\) to bude rovnaké. Všeobecný dôkaz príde neskôr. Ako sa dostaneme do podšachovnice \(3\times 3\)? Z ľubovoľnej podšachovnice \(3\times k\), kde \(4\leq k \leq n\). Ako sa dostaneme do \(3\times k\)? Z \(k\times k\). A tak ďalej.

Dôkaz

Nech začína D. V. Označme si políčka šachovnice od jeho rohu \((1,1)\) po môj roh \((n,n)\). Dokážem, že pre mňa budú vyhrávajúce pozície tie, keď moja vzdialenosť na prvej a druhej súradnici od D. V. je rovnaká a D. V. je na ťahu, v preklade naše veže sú v rohu štvorca.

Nech je v nejakom momente hry dosiahnutá taká pozícia, nech D. V. je ťahu na políčku \((a,b)\) a ja som na \((a+k, b+k)\). D. V. sa môže pohnúť na ľubovoľné políčko z množiny \[\begin{align} \{(a', b), a'\in \{1,2,\dots, a-1, a+1, \dots, a+k-1\}\} \cap \\ \cap \{(a, b'), b'\in \{1,2,\dots, b-1, b+1, \dots b+k-1\}\}.\end{align}\]

Ak D. V. ťahal tak, že \(a'>a\), resp. \(b'>b\), tak moja odpoveď bude ťah na \((a+k,b+k+a-a')\), resp. \((a+k+b-b',b+k)\). Tým vznikne štvorec menšej veľkosti. Síce bližší roh, teda roh veže D.V., bude ďalej od súradníc \((1,1)\), avšak moja veža bude bližšie k rohu \((1,1)\) ako bola v predošlom ťahu.

Ak D. V. ťahal tak, že \(a'<a\), resp. \(b'<b\) pre príslušné ťahy, tak moja odpoveď bude ťah na \((a'+k,b+k)\) resp. \((a+k,b'+k)\). Tým vznikne opäť štvorec rovnakej veľkosti a obe veže budú bližšie k súradniciam \((1,1)\).

Lenže ťahy oboch typov vie robiť D. V. iba obmedzený počet krát, a preto vyhrám. Inými slovami, ja sa svojim ťahom vždy priblížim k rohu \((1,1)\) a vždy viem spraviť ďalší ťah, teda raz musí nastať situácia, že D. V. už nemá ako ťahať.