6. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Ulice v meste sú usporiadané do nekonečnej štvorcovej mriežky, z ktorej časť vidíme na obrázku (mriežka rovnako pokračuje aj ďalej do všetkých smerov). Šošo a jeho čata si naplánovali trasu, ktorá sa skladala z 9 presunov. Pri každom presune si vybrali nejakú svetovú stranu a v tom smere sa posunuli na najbližšiu križovatku. Keď však túto trasu prešli, stále nezvolali dosť ľudí, takže takých istých 9 presunov zopakovali ešte niekoľkokrát. Výprava začínala v bode A (súradnice [0; 0]). Po 15 presunoch sa nachádzali v bode B (= [3; 2]), po ďalších 7 presunoch sa nachádzali v bode C (= [5; 3]) a po ďalších 8 presunoch v bode D (= [6; 6]). Počas celej výpravy nikdy neprešli po tom istom úseku (medzi dvomi susednými križovatkami) dvakrát.
  1. Zistite, kde sa nachádzali po 27 presunoch.
  2. Zistite z akých deviatich presunov sa skladala ich pôvodná trasa.

Vzorové riešenie

Opravovali: Danko, MartinŠ

Šošo a jeho čata prešli za celý čas svoju trasu trikrát, a potom ešte prvé tri presuny zo štvrtého opakovania, kým sa dostali do bodu D (15+7+8=3 \cdot 9+3). Po troch prejdeniach trasy, čiže 27 presunoch sa nachádzajú na trikrát väčších súradniciach ako po jej prvom prejdení, keďže prejdením trasy sa vždy posunuli rovnako, a začínali na [0;0]. Teda obe súradnice, vodorovná aj zvislá, vtedy budú deliteľné 3. Keďže o 3 presuny neskôr už boli v D, zaujímajú nás iba tie z nich, ktoré sú od D vzdialené maximálne 3. Týmto dostávame len 5 možností kde sa mohli po 27 presunoch nachádzať, no priamo v D to byť nemohlo, pretože nevieme spraviť 3 presuny tak, aby sme sa vrátili do D (musí ich byť párny počet, za každý presun nejakým smerom sa potom musíme vrátiť opačným). Na obrázku sú zaznačené modrou:

Z každej z týchto pozícií je len jedna cesta ako sa na tri presuny vieme dostať do bodu D, a to rovno, 3 presuny priamo do smeru ktorým je D. To nám už určí prvé tri z deviatich presunov na trase. Skúsme si preto pre každú možnosť rozobrať, čo nám to o zvyšku trasy hovorí, a ktoré trasy by mohli sedieť.

Ak sú po 27 ťahoch v E=[6;9] alebo F=[9;6].

V oboch prípadoch sa zameriame na pohyb tým smerom, v ktorom sa musíme dostať až na súradnicu 9. Ukážeme si argument pre prípad s E, a rovnako vieme argumentovať aj v prípade s F. Vieme, že z bodu E, kde začíname nové opakovanie trasy, idú tri kroky do D, teda prvé tri presuny trasy sú smerom dole. Táto trasa sa pred príchodom do E zopakovala trikrát, vždy začínajúc troma presunmi dole, teda dokopy sa pohnú dole aspoň 9-krát. E však leží od bodu A 9 posunov opačným smerom, preto by zo zvyšných 18 pohybov v prvých troch cykloch všetky museli smerovať hore, aby mali šancu skončiť aspoň na výške bodu E. Potom by však neostali už žiadne presuny na to, aby sme sa dostali o 6 miest doprava, kde E leží, lebo všetkých 27 presunov robíme iba vertikálne.

Podobne pri bode F, aby sme sa vzhľadom na nutných 9 presunov doľava vedeli dostať dostatočne doprava, museli by všetky ostatné presuny smerovať tam, a nemali by sme sa ako dostať o 6 presunov hore.

Ak sú po 27 ťahoch v G=[6;3].

Vieme, že na to, aby sa dostali z G do D, musia byť prvé 3 posuny trasy hore. Okrem toho, ak sa po 3 trasách nachádzajú na súradniciach [6; 3], tak každá trasa ich posunula o tretinu z celkovej zmeny, teda celkovo o 2 presuny doprava a o 1 hore. Vieme teda, že po 21 presunoch, teda dvoch prejdeniach trasy a troch krokoch sa budú nachádzať na [2 \cdot 2, 2 \cdot 1] a ešte o prvé tri kroky vyššie, teda na [4;5]. Bod C sa však nachádza na [5;3], a musia sa tam dostať už po 15+7=22 presunoch, čo je hneď po najbližšom, aj keď spolu tieto body nesusedia. V tomto prípade teda tiež nevieme splniť podmienku zo zadania.

Ak sú po 27 ťahoch v H=[3;6].

Podobne ako v predošlom prípade, aj tu vieme zistiť, že prvé tri presuny trasy smerujú doprava, a každá trasa ich musela dokopy posunúť o [+1; +2]. Ďalej sa pozrieme, ako sa mohli dostať do bodu C. Pozíciu po 18 presunoch poznáme, je to [2 \cdot 1; 2 \cdot 2]=[2;4], a potom znova opakujú trasu od začiatku, teda začínajú tromi presunmi doprava na [5; 4]. Hneď v nasledujúcom ťahu musia byť na C=[5; 3], teda sa v štvrtom presune trasy pohnú dole.

So znalosťou prvých štyroch presunov trasy sa pozrieme čo sa stane po jej prvom prejdení. Dostávame sa z [1,2] tromi presunmi doprava a jedným dole na [4;1]. To je zatiaľ 13 presunov z pätnástich, po ktorých majú byť v B. Za zvyšné dva presuny sa na [3; 2] vedia dostať len kombináciou presunu doľava a hore, no nemôžu sa vrátiť hore po ceste ktorou prišli, a preto začnú presunom doľava. Teraz im už chýba prejsť iba posledné tri presuny, aby dokončili druhé opakovanie trasy, ktorého konečný bod vieme vypočítať ako 2*[1;2]=[2;4]. Pôjdu tam teda dvoma presunmi hore a jedným doľava. Ten presun vľavo nemôžu spraviť hneď, lebo tadiaľ už raz išli, a ani ako posledný, lebo hneď na začiatku ďalšej trasy pôjdu doprava, čo by bolo po rovnakom úseku. Teda tam pôjdu v poradí hore, doľava hore.

Odpoveď: Výsledná trasa po ktorej išli je teda doprava, doprava, doprava, dole, doľava, hore, hore, doľava, hore.

Komentár

V tomto príklade sa mohlo zdať náročné vôbec začať, hlavne bez uvedomenia že súradnice po presune 27 musia byť násobkom troch. Viacerí z vás to však zvládli aj bez toho, okrem postupu spomenutého v tomto vzorovom riešení sa dalo ku príkladu postupovať aj na základe iných obmedzujúcich informácií alebo pomocou rovníc. Celkovo však treba povedať, že riešitelia ktorí sa príklad odhodlali odovzdať ho poväčšinou úspešne vyriešili bez väčších problémov.