5. príklad - Vzorové riešenie
Zadanie
Pláň je nekonečná štvorcová sieť. Na nej máme medveďa a svišťa, ktorí sa naháňajú, a vždy sú na susedných políčkach. V každom kroku sa pohnú tak, že:
- svišť sa teraz rohom, ale nie stranou, dotýka políčka, na ktorom stál v predchádzajúcom kroku medveď,
- medveď sa nedotýka ani jedného z políčok, na ktorých stáli svišť alebo medveď v predchádzajúcom kroku, stranou ani rohom,
- svišť a medveď stále susedia stranou.
Na ktoré všetky pozície (vzhľadom na tú začiatočnú) sa vedia medveď a svišť dostať po ľubovoľnom počte krokov?
Vzorové riešenie
Na začiatku nevieme, ako sú súradnice otočené. Tak si ich otočme tak, aby svišť a medveď boli takto vedľa seba:
Najskôr sa môžem pozrieť, kam sa dokážu medveď a svišť dostať po jednom kroku:
Svišť sa posunie diagonálne od medveďa a medveď vedľa neho, tak aby sa nedotýkal predchodzej pozície.
Teraz by sme radi našli nejaký pohyb, ktorý by sme vedeli opakovať, aby sme pokryli nejakú časť plochy. Napríklad by nás zaujímalo, či existuje postupnosť ťahov, ktoré dostanú svišťa s medveďom o jedna doprava. Ak áno, vieme tento pohyb opakovať a posunúť ich tak na ľubovľné miesto napravo.
Rovnakú postupnosť môžeme urobiť aj symetricky na druhú stranu. Totiž všetky ťahy, ktoré sme použili fungujú aj doľava aj doprava. Tak sa vedia posunúť doľava. Toto pre nás znamená, že ich vieme posunúť hocikam chceme na čiare prechádzajúcej cez nich.
Vieme ich podobne posunúť aj hore a dole?
Na to, aby boli priamo nad svojou minulou pozíciou, môžeme ich posunúť dva krát doľava. Znovu symetricky ich vieme posunúť aj dole o jedno políčko.
Odpoveď: Pomocou novo vytvorených pohybov hore, dole, doprava, doľava sa dokážu dostať na hocijaké políčko v štvorcovej sieti.