1. Poskakujúci Super Mário

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

Super Mário spokojne prežíval jeden zo svojich troch životov – jedol hríby, poskakoval medzi stromami, a naháňal sa za princeznou. Pri jednom skoku sa ale pošmykol a spadol do veľkej zelenej rúry. Keď precitol, zistil, že sa nachádza v nevedno akom veľkom systéme miestností.

Tento systém je tvorený niekoľkými navzájom nerozoznateľnými miestnosťami usporiadanými do kruhu. Z každej miestnosti vedú dve prechodové komory do susedných miestností. Okrem toho je tam už len jedno stropné svetlo a vypínač, ktoré toto svetlo ovláda. Pomocou neho vie Mário v danej miestnosti vypnúť alebo zhasnúť svetlo.

Na obrázku nižšie je jednoduchý systém so štyrmi miestnosťami. Mário sa nachádza v hornej z nich a v miestnosti je aktuálne zhasnuté.

Mário by rád zistil, v akom rozsiahlom systéme sa nachádza, teda určil počet miestností, ktoré ho tvoria. Má však niekoľko problémov. Síce zapnutie a vypnutie svetiel ovláda iba Mário pomocou vypínačov v miestnosti, netuší ako sú tieto svetlá rozsvietené na začiatku. V niektorých miestnostiach sú zapálené, v iných nie. No najmä, napriek tomu že je Super, si nevie v miestnostiach nechávať žiadne značky ani ich iným spôsobom označovať. Je teda naozaj odkázaný iba na zapínanie a vypínanie svetiel.

Úloha

Mário môže robiť dva typy akcií: prechádzať dverami medzi skrýšami a rozsvecovať alebo zhasínať svetlo v jednotlivých skrýšach. Vašou úlohou je pomôcť mu s nasledujúcimi problémami.

1. (2 body) Vymyslite spôsob, ktorým Mário zistí, či je v systéme práve jedna miestnosť alebo ich je viac. Ak je systém miestností tvorený iba jednou miestnosťou, tak jediná prechodová komora spája jedny jej dvere s druhými. Ak teda Mário opustí miestnosť jedným koncom, vojde druhým koncom do tej istej miestnosti.

2. (3 body) Nájdite ľubovoľný spôsob, ktorým Mário zistí, či sú miestnosti aspoň tri.

3. (6 body) Nájdite ľubovoľný postup, ktorým vie Mário zistiť počet miestností v systéme, bez ohľadu na to, aký je veľký.

4. (4 body) Označme si počet miestností v systéme ako \(n\) (ktoré Mário stále nepozná). Nájdite taký spôsob na určenie tejto hodnoty, pri ktorom Máriovi stačí spraviť nanajvýš \(20n + 47\) akcií (táto hodnota výrazne prevyšuje počet akcií, ktoré potrebuje spraviť vzorové riešenie). Odôvodnite, prečo váš postup nepotrebuje viac akcií.

   Ak si nie ste istý, koľko otázok používa váš postup, aj tak nám ho pošlite, určite získate aspoň čiastkové body :)