Novinka: popis nemusíš odovzdávať len na konci kola, ale môžeš už priebežne. My sa ti ho pokúsime čo najskôr opraviť a ak nebudeš mať všetko alebo niečo nebude správne, tak tvoj popis môžeš doplniť/opraviť a znovu ho odovzdať.

V krajine za siedmimi horami a za siedmimi dolinami, kde sa voda sypala a piesok lial, žila raz Červená Čiapočka. Jedného dňa ochorela Červenej Čiapočke babka. Čiapočka dostala teda za úlohu jej zaniesť obed. Mama jej nabalila do košíka koláče, víno, a z nejakého dôvodu aj kriedy, a dievča sa vydalo na cestu lesom.

Červená Čiapočka si spokojne išla po lesnom chodníčku, keď tu zrazu ide okolo skalnej steny a vidí, že v nej sú dvere. “Fúha, čo tam môže byť, to musím preskúmať,” pomyslí si. Nakukne do dverí a vidí, že za nimi je chodba. Ide po chodbe, ale tá sa o chvíľu rozvetví na dve chodby. “To vyzerá ako bludisko,” hovorí si Čiapočka. “Zaujímalo by ma, čo je v ňom. Ale ako ho ho môžem preskúmať a nestratiť sa pri tom?”

Úloha

Bludisko si môžeme predstaviť ako štvorcovú mriežku, kde každé políčko je buď stena alebo voľné. Na všetky voľné políčka sa dá dostať od vchodu po voľných políčkach. Môže vyzerať napríklad takto:

Červená Čiapočka by chcela preskúmať bludisko. To znamená, že by chcela prejsť postupne všetkými políčkami a potom sa vrátiť späť von. Nemôže teda napríklad len vojsť a pri prvej križovatke sa otočiť a vyjsť naspäť von, lebo tak nepreskúma celé bludisko.

a. Nakresli v obrázku vyššie, ako ho môže Červená Čiapočka preskúmať, teda akou cestou ho môže prejsť.

Môže sa stať, že v bludisku je cyklus. To je taká postupnosť (aspoň troch) susedných políčok, že sú všetky rôzne a prvé susedí s posledným. Napríklad tieto políčka tvoria cyklus:

b. Predpokladajme, že v bludisku nie sú žiadne cykly. Daj Červenej Čiapočke návod, ako má bludisko preskúmať. Pozor, Červená Čiapočka nemá neobmedzenú pamäť, vie si pamätať iba zopár vecí. Vie si napríklad zapamätať posledné políčko, na ktorom bola, ale nevie si zapamätať celú jej cestu bludiskom.

c. Červená Čiapočka neverí tvojmu návodu, bojí sa dvoch vecí: (1) či takto naozaj prejde celé bludisko a žiadnu časť z neho nevynechá, a (2) či trafí naspäť z bludiska von, či sa jej nestane, že by v ňom takto blúdila donekonečna. Skús ju presvedčiť, že tvoj návod takto naozaj funguje.

Červená Čiapočka sa teda odhodlane vydala skúmať bludisko podľa tvojho návodu. Po chvíli vyšla zase von, ale niečo sa jej nezdalo. Určite predsa neprešla úplne všetkými chodbami.

d. Vymysli také bludisko (už v ňom môžu byť aj cykly), že keby ho Červená Čiapočka skúmala podľa tvojho návodu z minulej úlohy, tak ho buď nepreskúma celé, alebo v ňom bude blúdiť donekonečna.

“Aha, už vidím v čom je problém,” pomyslí si Čiapočka. “Ale ako to potom spravím, aby som sa v bludisku nestratila… počkať, veď ja tu niečo mám!” Spomenie si, že v košíku má okrem jedla aj kriedy, tak jednu z nich vytiahne.

e. Červená Čiapočka si teraz môže na každé políčko, ktorým prechádza, nakresliť kriedou nejakú značku (vie kresliť len zopár jednoduchých značiek, teda môže tam napríklad spraviť čiarku, ale nemôže tam nakresliť celú mapu bludiska). Uprav tvoj predchádzajúci návod tak, aby Čiapočka preskúmala celé bludisko a nestratila sa, aj keď v ňom sú cykly.

Červená Čiapočka sa teda vydala do bludiska aj s kriedou a poctivo preskúmala každé zákutie, keď zrazu pred sebou vidí - Vlka. “Ale ale, kto to tu chodí po mojom bludisku?” pýta sa Vlk. “Ja… ja som Červená Čiapočka,” bojazlivo povie Červená Čiapočka. “Idem babke zaniesť koláče, a po ceste som uvidela vchod, tak som sa len chcela pozrieť, čo tu je. Nechcela som vôbec rušiť…”

“No dobre teda”, povie Vlk. “Neboj, ja ti nič nespravím. Len mi povedz, kde to tá tvoja babka vlastne býva?” Červenej Čiapočke odľahlo, že ju Vlk nezožerie, a tak mu povedala, kde býva jej babka. Vlk potom odbehol a Červená Čiapočka sa vrátila späť von z bludiska a pokračovala v ceste.