10. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Parkovisko má tvar tabuľky n \times n a autobus stojí na ľavom hornom políčku. Chatár je veľký komediant a preto chce donútiť autobusára zastaviť na každom jednom políčku parkoviska tak, aby si autobusár nevšimol, že si z neho robí srandu. Preto vie autobusára navigovať iba tak, že zastaví o 2 políčka diagonálne, od miesta kde stojí, alebo zastaví na ľubovoľnom hranou susediacom políčku, od toho istého miesta. Navyše na žiadnom políčku autobusár nemôže zastaviť viac ako raz, inak by mu to prišlo podozrivé. Nakoniec vieme, že chatár strieda autobusárove pohyby, pričom prvý krát poslal autobusára o 2 políčka diagonálne od jeho pôvodnej polohy. Určte pre ktoré n sa chatárovi podarí, autobusára navigovať cez všetky políčka, bez toho, aby si autobusár všimol, že si z neho strieľa:

  1. pre n = 4,
  2. pre n = 8,
  3. pre n = 9

Vzorové riešenie

Opravovali: JakubK, Johnny

Tabuľka veľkosti 4 \times 4 je pomerne malá a dá sa s ňou pohrať. Navyše väčšinou je vynútený ťah alebo len zopár možností. Jedno z riešení ako sa dá prejsť celá tabuľka je nasledovné:

Tabuľka veľkosti 8 \times 8 už je moc veľká na to, aby sme náhodne dopĺňali poradie pohybov a dúfali, že nám to výjde. Tabuľka 8 \times 8 sa dá rozdeliť na štyri 4 \times 4 tabuľky. Jednu tabuľku 4 \times 4 sme už vytvorili, tak ju poďme aj využiť. Po jej prejdení skončíme na kraji tabuľky, konkrétne v pravom hornom rohu. Ak by sme tieto ťahy však robili postupne osovo súmerne podľa osi z ľahvého horného rohu do pravého dolného rohu, tak by sme skončili v ľavom dolnom rohu. Tabuľku 8 \times 8 vieme prejsť tak, že najskôr prejdeme tabuľku 4 \times 4 v ľavom hornom rohu a potom sa premiestnime o jedno políčko doprava, lebo sme končili diagonálnym pohybom. Znovu začíname v rohu 4 \times 4 tabuľky, avšak teraz ju prejdeme tak, aby sme skončili v jej ľavom dolnom rohu. Končili sme diagonálnym pohybom, takže sa môžeme posunúť o jedno políčko dole. Teraz sa znovu nachádzame v ľavom hornom rohu tabuľky 4 \times 4, takže ju vieme prejsť tak, že skončíme v jej ľavom dolnom rohu. Potom sa vieme posunúť o jedno políčko doľava a skončíme tak v pravom dolnom rohu poslednej tabuľky 4 \times 4. Keďže vieme prejsť celú tabuľku 4 \times 4 z ľavého horného rohu, tak ju vieme celú prejsť aj z pravého dolného rohu. To znamená, že vieme prejsť aj celú tabuľku 8 \times 8.

S tabuľkou 9 \times 9 už nebudeme mať také štastie, tú už celú neprejdeme. Máme 2 rohy tabuľky také, že susedia s rohom, v ktorom začíname. To znamená, že v aspoň jednom z týchto rohov nebudeme končiť, bez újmy na všeobecnosti, nech je to pravý horný roh. Na každom políčku okrem počiatočného a konečného sú oba druhy ťahov, pričom jedným typom sa naňho dostaneme a tým druhým z neho odídeme. Navyše začíname diagonálnym pohybom, takže políčka X, Y budú určite zabrané diagonálnym pohybom.

Môžeme si všimnúť, že na políčko Z sa už nemôžeme dostať, lebo žiaden diagonálny pohyb z neho nevedie na voľné políčko. Jediný prípad kedy by sme nepotrebovali použiť diagonálny pohyb na políčku Z by bol ak by sme končili na ňom. Potom sa však môžeme pozrieť na ľavý dolný roh a rovnakým argumentom by sme sa dostali do sporu, avšak teraz už nemôžeme povedať, že na sporom políčku budeme končiť. Tým sme ukázali, že exituje v tabuľke políčko, na ktoré sa nikdy nevieme dostať, takže ju nemôžeme celú prejsť podľa podmienok zo zadania.

Odpoveď:Pre n = 4 a n = 8 sa to chatárovi podarí, avšak pre n = 9 sa mu to už nepodarí.