Uvažme na (nekonečné) tabuli zapsaný konečně dlouhý řetězec složený pouze ze znaků 0 a 1. Vyvolaný student nyní přistoupí k tabuli a pokud řetězec začíná znakem 0, tak na konec řetězce připíše dva znaky 00. Pokud však aktuální řetězec začíná znakem 1, tak na jeho konec student dopíše čtyři znaky 1101. Poté student první tři znaky řetězce smaže a jde si sednou do lavice. Následně je k tabuli vyvolán další student a vše se opakuje, pak další a další studenti...

Kdy popsaný proces skončí? Buď jsou postupně umazány znaky řetězce, až jich na tabuli zbude méně než tři a proces se zastaví. Nebo je některý řetězec zopakován a proces se pak zacyklí do nekonečna. Nebo ještě se může stát, že délka řetězce obecně (v dlouhodobém horizontu) neustále roste a nikdy nedojde ani k zacyklení, ani k zastavení. (Studentů a tabule ke hraní je pořád dost.)

Zamyslete se nad následujícími úkoly a aspoň část z nich vyřešte pro získání bonusu.

a) V zahřívacím kole každý dokažte, že pokud dojde k zacyklení procesu (jak je definováno výše), tak délka cyklu musí být sudá.
Každé odevzdané řešení musí tento bod obsahovat, avšak jen tato lehká otázka na bonus nestačí - pokračujte dále.

b) Sestrojte počáteční řetězec pro nějž se proces zacyklí s co nejkratší délkou cyklu.
(Opět se jedná o lehkou otázku, a proto řešte i z dalších bodů.)

c) Pokuste se (ručně nebo s pomocí počítače) sestrojit počáteční řetězec, pro který se proces ani nezastaví, ani nezacyklí, tedy kdy bude délka řetězce narůstat nade všechny meze. Případně můžete uvést důkaz, že tato situace nemůže nastat.

d) Najděte (ručně nebo s pomocí počítače), pro všechny malé délky n, počáteční řetězec délky n pro nějž se proces zastaví po co nejdelším počtu kroků. Ještě hodnotnější by byla obecná konstrukce počátečních řetězců libovolných délek, pro které se proces zastaví po co nejdelším počtu kroků (doprovázená důkazy správnosti a maximality).

e) Najděte (ručně nebo s pomocí počítače), pro všechny malé délky n, počáteční řetězec délky n pro nějž se proces zacyklí s co největší délkou cyklu obsahujícího i počáteční řetězec. Ještě hodnotnější by byla obecná konstrukce počátečních řetězců libovolných délek, pro které vznikají největší délky cyklů (doprovázená důkazy správnosti a maximality).

f) Co dalšího zajímavého a netriviálního dokážete o popsaném procesu zjistit?