1. Poskakujúci kôň

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Romanovi na [email protected]

Emovi sa končila stáž v Zurichu a potreboval pred odchodom upratať byt. Po chvíli upratovania našiel v kope neporiadku niečo zaujímavé – nekonečnú¹ šachovnicu a figúrku jazdca (koňa). Emo si síce uvedomoval, že by mal upratovať, no napriek tomu si sadol k šachovnici a začal sa s jazdcom hrať. Však len chvíľku…

Ale chvíľa sa natiahla a Emo si zrazu uvedomil, že ak v okamihu neodíde, zmešká lietadlo. Čo však s nevyriešenými problémami, ktoré mu pri hraní napadli?

Úloha

Každému políčku Emovej nekonečnej šachovnice vieme priradiť dvojicu čísel, ktoré určujú jeho súradnice. Prvé číslo zodpovedá horizontálnej (stĺpec) a druhé vertikálnej (riadok) pozícii vzhľadom na začiatok \((0,0)\). Zopár príkladov súradníc nájdete na obrázku nižšie.

Na začiatku stojí na políčku \((0,0)\) jazdec, ktorý sa môže pohybovať podľa štandardných šachových pravidiel. Pohyb jazdca pripomína písmeno L – najskôr sa posunie o dve políčka v zvislom alebo vodorovnom smere a potom ešte o jedno políčko kolmo na pôvodný smer. Na nekonečnej šachovnici má teda pri každom skoku na výber osem políčok, na ktoré sa môže presunúť (viď obrázok).

1. (2 body) Políčko \((0,0)\) má bielu farbu a zvyšené políčka sú ofarbené šachovnicovo. Akú farbu bude mať políčko, na ktoré sa jazdec dostane po \(X\) skokoch? Prečo?

2. (2 body) Jazdec zo svojho začiatočného políčka urobil presne dva skoky. Na koľkých rôznych políčkach môže teraz stáť? Aké súradnice majú tieto políčka?

3. (2 body) Koľko najmenej skokov potrebuje jazdec na to, aby sa dostal zo svojho začiatočného políčka na ľubovoľné zo 4 políčok, ktoré so začiatočným susedia stranou (políčka so súradnicami \((0,1)\), \((1,0)\), \((0,-1)\) a \((-1,0)\))? Prečo to nejde na menej skokov?

4. (2 body) Jazdec zo svojho začiatočného políčka urobil presne tri skoky. Na koľkých rôznych políčkach môže teraz stáť? Popíšte postup, ktorým ste sa dopracovali k svojmu riešeniu. Na rozdiel od podúlohy b) nemusíte do popisu písať súradnice týchto políčok.

5. (3 body) Koľko najmenej skokov potrebuje jazdec na cestu z políčka \((0,0)\) na políčko \((9,9)\)? Prečo to nejde na menej? Popíšte postup, ktorým ste sa dopracovali k svojmu riešeniu.

6. (4 body) Popíšte všeobecný postup, ako by ste zisťovali, na koľko najmenej skokov sa vie jazdec dostať z políčka \((0,0)\) na políčko \((X,Y)\). Skúste popísať, prečo je váš postup správny.