1. Preblšený cirkus

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Maji Vajdovej na

V jednom malom neznámom cirkuse na okraji jedného malého bezvýznamneho mesta sa jedného nudného dňa premnožili blchy. Celý cirkus sa obrátil hore nohami. Namiesto toho, aby sa nacvičovali nové čísla, zvieratá aj ľuďia začali splašene pobehovať po okolí a pomaly cirkus opúšťať. Keď to už vyzeralo tak, že malý neznámy cirkus bude treba zavrieť, blchy zmutovali do obrovských rozmerov.

To, čo sa na prvý pohľad javilo ako ešte väčšia katastrofa, sa nakoniec ukázalo ako výhoda, ktorá náš malý cirkus preslávila po celom svete. Také veľké blchy sa totiž dajú trénovať, preto sa náš cirkus premenoval na blší a funguje dodnes.

Pred blším vystúpením sa vždy na podlahu nakreslí niekoľko kruhov a očíslujú sa začínajúc od \(1\). Do každého sa potom položí jedna blcha. Vždy, keď počas vystúpenia cvičiteľ zapíska na píšťaľku, všetky blchy skočia zo svojho kruhu do nejakého (nie nutne iného) určeného kruhu. Kruh, do ktorého má blcha skočiť je určený číslom kruhu, v ktorom blcha stojí. Napríklad môže byť povedané, že z kruhu \(3\) sa skáče do kruhu \(1\) a z kruhu \(2\) sa skáče späť do kruhu \(2\). Toto určenie sa počas celého vystúpenia nemení.

Cvičitelia by však potrebovali pomôcť s plánovaním nových choreografií a s prosbou o pomoc sa obrátili na vás.

Úloha

Máme choreografiu pozostávajúcu z \(n\) kruhov pre blchy a z \(n\) bĺch. Pre každý kruh je určené, do ktorého kruhu sa z neho blcha musí pri zapískaní pohnúť. Na obrázku je vidno rozostavenie pre 5 bĺch. Šípka vedúca z kruhu určuje, do ktorého kruhu má z neho blcha skočiť.

Na ďalšom obrázku je vidno inú choreografiu pre \(5\) bĺch. Môžete si na nej všimnúť, že po dvoch zapískaniach sa všetky blchy ocitnú v kruhu \(2\). Takéto blšie choreografie voláme stretávacie. Aj blšia choreografia na predchádzajúcom obrázku má zaujímavú vlastnosť: po presne šiestich zapískaniach bude každá blška naspäť v krúžku, v ktorom bola na začiatku vystúpenia. Takéto blšie choreografie voláme opakovacie.

Vašou úlohou je vymyslieť niekoľko choreografií tak, aby spĺňali nasledovné požiadavky. Vo vašom riešení však nestačí nakresliť žiadanú choreografiu, ale aj vysvetliť, prečo má daná choreografia požadované vlastnosti. Choreografie bez popisu budú hodnotené najviac polovicou bodov.

1. (1 bod) Nakreslite opakovaciu choreografiu, pre ktorú sa blšky na pôvodné miesta vrátia nie po \(6\), ale po \(7\) skokoch. Môžete použiť ľubovoľný počet krúžkov, nemusí ich byť len \(5\).

2. (1 bod) Nakreslite opakovaciu choreografiu, v ktorej sa blšky na pôvodné miesta vrátia prvýkrát až po \(10\) skokoch. Tentokrát ale musíte použiť menej ako \(10\) krúžkov.

3. (2 body) Choreograf by od vás chcel blšiu choreografiu s \(10\) krúžkami. Zaujímalo by ho, aké je najväčšie číslo \(k\), pre ktoré platí, že sa blšky prvýkrát ocitnú všetky naraz vo svojich počiatočných pozíciach po práve \(k\) zapískaniach. Ako taká choreografia vyzerá? Prečo ja vami nájdené \(k\) najväčšie možné?

4. (2 body) Nájdite choroegrafiu s čo najmenej krúžkami, ktorá sa prvýkrát opakuje po \(3960\) zapískaniach.

5. (4 body) Nájdite najmenší počet krúžkov pre choreografiu, ktorá sa má prvýkrát opakovať po \(n\) zapískaniach. Vo vašom riešení popíšte postup ako takúto choreografiu nakresliť a vysvetlite, prečo sa neoplatí kresliť túto choreografiu inak. Dbajte na správnosť vašich tvrdení a argumentov.

6. (1 bod) Skúste vymyslieť choreografiu, ktorá nebude ani stretávacia, ani opakovacia.

7. (1 bod) Janko si nakreslil choreografiu so \(47\) krúžkami. Neukázal ju Marienke, len jej povedal, že jeho choreografia je stretávacia. Na to Marienka povedala: “Nemusíš mi ju ukazovať. Napriek tomu som si istá, že keď \(b\)-krát zapískam, budú už všetky blšky v tom istom krúžku.” Pre aké najmenšie \(b\) má Marienka pravdu bez ohľadu na to, ako vyzerá Jankova choreografia? Prečo?

8. (3 body) V stretávacej choreografii z príkladu si môžeme všimnúť šipku vedúcu z krúžku 2 naspäť do krúžku 2. Takúto šipku voláme slučka. Existuje stretávacia choreografia, v ktorej nie sú žiadne slučky? Svoju odpoveď zdôvodnite.