Opravovatelia

Mišo M. [email protected]

Pre jednoduchosť vyjadrovania si zavedieme súradnice pre našu tabuľku. Riadok a stĺpec, v ktorých kôň začína, označíme ako nulté. Smerom nahor budú postupne prvý, druhý, až $(m+1)$-vý riadok, smerom doprava budú prvý až $(n+1)$-vý stĺpec. Kôň teda začína na políčku $[0,0]$ a chce sa dostať na políčko $[m+1,n+1]$. Zároveň na ostatné políčka v nultom a $(m+1)$-vom riadku, nultom a $(n+1)$-vom stĺpci stúpiť nevie.

Zároveň si uvedomme, že výmena hodnôt $m, n$ len preklopí celú tabuľku, čo nemení nič na tom, či cesta pre koňa existuje alebo nie. Bez ujmy na všeobecnosti tak môžeme predpokladať, že $m \leq n$. Rozlíšime teda jednotlivé prípady pre počet riadkov.

Prípad $m = 1$

Jazdec v šachu skáče v tvare $L$-ka, keď sa jedným zo štyroch smerov posunie o $2$ políčka a súčasne niektorým kolmým o $1$. To znamená, že pri každom jeho skoku sa jedna jeho súradnica zmení o $1$, kým zvyšná sa zmení o $2$. Keďže $n \geq m = 1$, vzdialenosť koňa od paše je aspoň $2$ políčka v každom smere, na jeden skok sa teda do cieľa nedostane. Musí teda spraviť skoky aspoň dva. Po jeho prvom sa posunie na políčko $[1, 2]$. Keďže $m = 1$, je iba jeden riadok, do ktorého môže skočiť. Keďže sa musí posunúť o $1$ riadok, musí sa posunúť o $2$ stĺpce, takže určite bude na tomto políčku. To zároveň znamená, že $n \geq 2$, inak by nevedel spraviť ani tento jeden skok.

Jeho druhý skok musí opäť zmeniť číslo jeho riadku. Mimo jeho riadok sú však len dve políčka, na ktoré vie stúpiť: $[0, 0]$ a paša. Vrátením sa na štart sa do cieľa nedostane, takže po druhom skoku musí byť na paši. Tá je v riadku $2$, takže opäť musíme stĺpec zmeniť o $2$, čím dostaneme políčko $[2, 4]$. Keďže na tomto políčku musí byť paša, nutne $m = 1$ a $n = 3$. To je zároveň jediná možnosť, ako sa do cieľa dostane pre jednoriadkovú tabuľku.

Obrázok 1: Riešenie pre $1$ riadok.

Prípad $m=2$

Tentoraz môže kôň spraviť prvý skok na dve políčka – $[1, 2]$ a $[2, 1]$. Zároveň si môžeme všimnúť, že pokiaľ neskáče na pašu, môže svoj riadok zmeniť jedine z $1$ na $2$ alebo z $2$ na $1$. V oboch prípadoch sa riadok mení o $1$, takže stĺpec sa zmení o $2$. Kým riadky sa musia pri každom skoku striedať, pri stĺpcoch sa môžeme rozhodnúť, či skočí smerom doprava k paši, alebo smerom doľava naspäť k počiatočnému políčku. Keďže vracať sa naspäť nijak nezmení, kam sa kôň môže dostať, po zvolení úvodného políčka je jeho cesta daná jednoznačne. Otázka znie, kedy sa dokáže dostať do cieľa.

Paša má súradnice $[3, n+1]$. Dostať sa na ňu tak vieme len z políčok $[2, n-1]$ a $[1, n]$, ktoré sú v posledných dvoch stĺpcoch. Kôň sa do týchto dvoch stĺpcov určite vie dostať z oboch počiatočných políčok. V každom skoku totiž vynechá („preskočí“) len jeden stĺpec, takže ak nie je v poslednom alebo predposlednom stĺpci, tak sa vie isto posunúť ďalej doprava. Označme $s$ počet skokov, ktoré spravil kôň, kým sa dostal do posledných dvoch stĺpcov. Rozlíšime dva prípady.

Ak je $s$ nepárne, teda $s = 2k+1$ pre kladné celé $k$, tak kôň skončí v rovnakom riadku, do ktorého ho dostal prvý skok. Po prvom skoku totiž zmenil riadok párne veľa ráz. V každom zo zvyšných $2k$ skokov sa zároveň posunie o $2$ políčka doprava. Pri voľbe $[1, 2]$ tak skončí na políčku $[1, 2+4k]$, pri voľbe $[2, 1]$ skončí na políčku $[2, 1+4k]$.

Ak je $s$ párne, teda $s = 2k$ pre kladné celé $k$, tak kôň skončí v opačnom riadku, než do ktorého ho dostal prvý skok. Opäť ho každý zo zvyšných $2k-1$ skokov posunie o $2$ políčka doprava. Z políčka $[1, 2]$ sa tak dostane na políčko $[2, 2 + 4k-2] = [2, 4k]$. Z políčka $[2, 1]$ na políčko $[1, 1+4k-2] = [1, 4k-1]$.

Kedy sa teda náš kôň dostane na pašu? Posledný skok z druhého riadku musí byť z políčka $[2, n-1]$, pričom sa jedná o políčko $[2, 1+4k]$ alebo $[2, 4k]$. Číslo $n$ tak má zvyšok $1$ alebo $2$ po delení $4$. Na to, aby bol posledný skok z prvého riadku, sa musí jednať o políčko $[1, n]$. Tam sa vie dostať buď na $[1, 2+4k]$ alebo $[1, 4k-1]$. Číslo $n$ má teda zvyšok $2$ alebo $4-1=3$. Kôň sa tak na pašu dostane, len ak $n$ nie je násobok $4$. V opačnom prípade vieme z $n$ dorátať vhodné $k$ a zvoliť postup, aby skončil na správnom políčku. Riešenia pre $m = 2$ sú teda $n \geq 2$, ktoré nie sú násobkom $4$.

Prípad $m \geq 3$.

Všimnime si, že z predchádzajúcej časti vieme, že koňovi stačia dva riadky na to, aby sa dokázal dostať do jedného z posledných dvoch stĺpcov. Odtiaľto vieme potom postupovať „preklopene“: koňa skákaním v posledných dvoch stĺpcoch dostaneme do jedného z posledných dvoch riadkov. Nech sa teda deje čokoľvek, kôň sa dostane do jedného zo štyroch políčok pred cieľom: $[m-1, n-1], [m-1,n], [m,n-1], [m,n]$. Ak sa vie dostať na pašu odtiaľ, isto sa tam dostane aj zo štartového políčka.

Obrázok 2: Možné pozície koňa v rohu.

Keďže predpokladáme, že $n \geq m$, tak nutne $n \geq 3$. Náš kôň má určite na manévrovanie aspoň $3$ políčka v každom smere. Všimnime si, že pre $3$ zo štyroch políčok to stačí. Ľavé horné a pravé dolné sú na jeden skok od cieľa, z úplného rohu sa na pašu dá doskákať napríklad takto:

Obrázok 5: Riešenie pravého horného rohu.

Čo však so štvrtým políčkom? Aby sa na toto políčko vôbec vedel dostať, musel tam skočiť z iného riadku/stĺpca ako sú posledné $3$. Zároveň je toto políčko príliš ďaleko od štartu, aby skočil priamo odtiaľ, takže nutne je niektoré číslo z $m, n$ viac ako $3$. Keďže sme $n$ zvolili ako „to väčšie“, tak $n \geq 4$. Potom má kôň o stĺpec viac na manévrovanie a na pašu sa dostane napríklad takto:

Obrázok 6: Riešenie pre poslednú pozíciu koňa.

Odpoveď: Kôň sa na pašu vie dostať pre dvojice $(m, n)$, kde $m$ aj $n$ sú aspoň $3$, $m = 2$ a $n \geq 2$ nie je násobok $4$, $n = 2$ a $m \geq 2$ nie je násobok $4$, a dvojice $(1, 3)$, $(3, 1)$.