2. Pestovanie ovocia v Absurdistane

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Samkovi Gurskému na

Genetickí inžinieri v Absurdistane urobili nedávno prevratné pokroky v genetickej modifikácii rastlín. Ich metóda je taká presná, že vedia určiť, koľko a dokonca aj akých plodov na vyšľachtenej rastline vyrastie. Napríklad vytvorili jahodu, na ktorej v lete dozrie jedna jahoda a jedna malina.

Naviac, aj nová jahoda, ktorá na rastline vyrástie, má tú istú vlastnosť. Preto ak z nej zoberú semiačko (nachádza sa tam iba jedno) a zasadia ho, v lete ďalšieho roka vyrastie rastlina s jednou jahodou a jednou malinou. Malinu zase vyšľachtili tak, aby z jej semiačka vyrástla vždy iba jedna malina (a žiadne jahody).

Označme si jahodu písmenom J a malinu písmenom M. Ak v prvom roku zasadíme jednu jahodu a následne budeme každý rok sadiť semienka zo všetkých plodov, ktoré nám dozrejú, budeme mať v nadchádzajúcich rokoch tieto plody:

• 1-vý rok – J – na začiatku máme jednu jahodu, ktorú zasadíme.
• 2-hý rok – JM – na zasadenej jahode vyrástla jedna jahoda a jedna malina. Táto rastlina následne uhynula, takže do ďalšieho roka budeme sadiť iba to, čo sme dopestovali.
• 3-tí rok – JMM – zo zasadenej jahody vyrástla opäť jedna jahoda a jedna malina, a zo zasadenej maliny vyrástla tiež jedna malina. Dokopy máme jednu jahodu a dve maliny, ktoré budeme sadiť ďalší rok.
• 4-tý rok – JMMM

Vidíme, že vďaka takto vyšľachteným rastlinám vieme dokonale predpokladať úrodu v ľubovoľnom ďalšom roku. V \(n\)-tom roku totiž budeme mať jednu jahodu a \(n-1\) malín, teda dokopy presne \(n\) plodov.

To, samozrejme, zaujalo vládu Absurdistanu. Vďaka štatistikám a vešteckej guli totiž presne vie, ako sa bude rok po roku vyvíjať spotreba ovocia v ich krajine. Ak by teda dokázali vyšľachtiť rastliny, ktoré túto spotrebu dokonale pokrývajú, bol by to veľký úspech pre ich ekonomiku. A práve na tomto mieste vstupujete do príbehu vy.

Úloha

Rastliny budeme v tejto úlohe označovať veľkými písmenami anglickej abecedy. Každá rastlina bude mať naviac určené, aké plody na nej dozrievajú. Toto zapíšeme tak, že za písmeno, ktoré zodpovedá rastline, napíšeme šípku a za tú písmená tých rastlín, ktorých plody na nej dozrejú. V našom prípade by sme teda mali rastliny J \(\rightarrow\) JM (na poradí písmen na pravej strane nezáleží, rastlina J \(\rightarrow\) MJ je úplne rovnaká) a M \(\rightarrow\) M. Dajte si pozor, že každá rastlina musí mať priradené práve jedno takéto pravidlo. Naviac, ak by sme chceli aby na nejakej rastline nič nevyrástlo (a takáto rastlina proste umrie), zapíšeme to pomocou \(\rightarrow\) 0.

Na začiatok si potom určíme, ktoré rastliny máme v roku 1. Počet týchto rastlín môže byť buď určený vládou alebo si ho v niektorých prípadoch môžeme určiť sami. V tom prípade však nemôžeme začínať s viac ako 5 rastlinami. To, akých typov sú tieto rastliny, je jedno a môžeme si to určiť ako chceme.

Následne v každom roku zasadíme všetky rastliny, ktoré máme. Na nich nám vyrastú nejaké plody, ktoré zozbierame, a pôvodné rastliny zahynú. Ďalší rok potom zasadíme všetky zozbierané plody¹, z nich nám opäť niečo vyrastie a toto opakujeme rok čo rok.

Vláda Absurdistanu vám zadá nejaké nekonečné postupnosti, ktoré hovoria o tom, koľko plodov treba vypestovať v ktorom roku. Vašou úlohou bude navrhnúť také rastliny, aby počet plodov, ktoré tieto rastliny vyprodukujú, bol rok po roku rovnaký ako v zadanej postupnosti.

Príklady

Skôr ako sa pustíme do súťažných úloh, ukážme si niekoľko užitočných príkladov.

Príklad 1: v \(n\)-tý rok chceme vypestovať \(n\) plodov. Takúto úlohu môžeme zapísať ako postupnosť \(1, 2, 3, 4, \dots\)

Toto je vlastne príklad zo zadania, preto sú riešením rastliny J \(\rightarrow\) JM a M \(\rightarrow\) M. A začínať chceme s jednou rastlinou J.

Príklad 2: v \(n\)-tom roku chceme vypestovať \(2n+1\) plodov. Takúto úlohu môžeme zapísať ako \(3, 5, 7, 9 \dots\)

Riešenie bude používať tie isté rastliny, ako sme použili v prvom príklade. Akurát v roku 1 musíme mať 3 rastliny. Zvolíme si rastliny JJM. Ešte potrebujeme dokázať, že takéto riešenie je správne. Z predchádzajúceho príkladu vieme, že za \(n\) rokov vyrastie z jednej J dokopy \(n\) plodov. No a M sa za celú dobu nezmení. V \(n\)-tý rok teda budeme mať \(n+n+1 = 2n+1\) plodov.

Príklad 3: je nám jedno, koľko plodov vypestujeme v prvom roku, potom však budeme chcieť, aby sa počet plodov každým rokom zdvojnásobil. Takéto zadanie zapíšeme ako \(x, *2, *2, \dots\) – \(x\) na začiatku hovorí o tom, že vládu nezaujíma počet plodov v prvom roku a môžeme si tento počet určiť sami (akurát musí byť najviac 5).

Toto môžeme dosiahnuť napríklad pomocou rastliny X \(\rightarrow\) XX, pričom na začiatku budeme začínať s jednou takotou rastlinou. Vidíme, že jediné rastliny, ktoré môžeme vypestovať, sú rastliny X. No a každý rok nám z každého zasadeného X vyrastú dva plody X, preto sa bude ich počet zdvojnásobovať.

Úloha

Pre každú z nasledovných podúloh navrhnite sadu rastlín a typy rastlín v prvom roku tak, aby bol počet plodov v roku \(n\) taký, ako určila vláda Absurdistanu vo svojej predpovedi. Je jasné, že vaše riešenie nemôže obsahovať viac ako 26 rôznych rastlín pre jednu podúlohu (lebo ako by sme ich pomenovali?). Vzorové riešenie však nepotrebuje na žiadnu podúlohu viac ako 10 rastlín.

Vo svojom riešení tiež zdôvodnite, prečo daný návrh funguje a v \(n\)-tom roku vyprodukuje požadovaný počet plodov. Snažte sa argumentovať všeobecne, pokúste sa vyhnúť argumentom "Pre prvé štyri roky to funguje...".

1. (1 bod) \(1, 2, 3, 1, 2, 3, 1, \dots\)

2. (2 body) \(x, +2, -1, +2, -1, +2, \dots\)

3. (2 body) \(x, *4, /2, *4, /2, \dots\)

4. (3 body) \(x,*2, +1, *2, +1, *2, \dots\)

5. (3 body) \(n\)-té fibonacciho číslo: \(1, 2, 3, 5, 8, 13, \dots\). \(n\)-té fibonacciho číslo vypočítate ako súčet dvoch predchádzajúcich čísel. Nasledujúce číslo je teda číslo \(8+13 = 21\).

6. (4 bodov) \(n^2\): \(1, 4, 9, 16, 25, \dots\)