5. Koľko máme stromov?

Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Toto je pokračovanie úlohy z minulého kola. Ak si úlohu v minulom kole nevidel(a), môžeš si pozrieť jej zadanie aj vzorové riešenie, aj keď to na pochopenie tejto úlohy nie je nutné.

Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected].

Zebra sa prechádza po savane, keď zrazu uvidí svoju kamarátku, žirafu Amandu, ako stojí pri strome, odtrháva si z neho ovocie a popri tom si niečo zapisuje do zošitu.

Zebra podíde k Amande a spýta sa: “Čo to robíš?”

Amanda dožuje kus ovocia, ktorý práve odtrhla, a začne vysvetľovať Zebre, ako vymyslela, že si bude zapisovať postupnosti čísel podľa toho, ktoré ovocia oberie.

“Najprv si treba uvedomiť, ako tie stromy vyzerajú. Tam, kde sa kmeň prvýkrát rozvetvuje, vždy rastie jeden kus ovocia. Tomuto ovociu môžeme hovoriť aj koreň, lebo je najbližšie ku koreňom stromu. Z miesta, kde rastie ovocie, sa kmeň rozdelí na niekoľko ďalších vetiev. Na konci každej vetvy rastie ovocie. Miesta, kde rastie ovocie, môžeme volať aj vrcholy. Z každého vrcholu ešte môže rásť aj niekoľko ďalších vetiev, na nich môžu byť ďalšie vrcholy, a tak ďalej.”

“Ovocia si navyše môžeme zoradiť podľa veľkosti a očíslovať ich od \(1\) po \(n\) (každé číslo použijeme práve raz). Okrem toho hovoríme, že nejaký vrchol susedí s nejakým iným, pokiaľ sú priamo spojené vetvou. Navyše povieme, že nejaký vrchol \(A\) je dieťa nejakého iného vrcholu \(B\), ak susedia a ak je \(B\) bližšie ku koreňu ako \(A\) – ako v rodokmeni. Podobne môžeme používať slová ako rodič alebo súrodenec. Nakoniec vrcholy, ktoré nemajú žiadne deti, voláme listy, lebo sú na konci vetiev, tak ako listy.”

“Dobre, to všetko dáva zmysel,” odpovedá Zebra, “ale čo to má spoločné s tými tvojimi zápiskami?”

“Tak teraz ti vysvetlím, ako oberám ovocie zo stromu. Začnem tým, že si nájdem list s najmenším číslom. Ten potom odtrhnem aj s vetvou, ktorou bol pripojený k rodičovi. A potom si zapíšem číslo, ale nie toho dieťaťa, ale toho rodiča. No a toto opakujem, až kým neoberiem celý strom.”

“Asi rozumiem,” hovorí Zebra, “ale rada by som k tomu videla aj nejaký príklad.”

“Dobre, tak predstav si takýto strom:”

“List s najmenším číslom je teraz \(1\), tak ho odtrhnem. Jeho rodič je \(4\), takže to si zapíšem. Teraz je najmenší list \(2\), tak odtrhnem ten a zapíšem si \(6\). Ďalší na rade je list \(5\), ktorého rodič je \(3\). Teraz už aj \(6\) je list, takže oberiem ten…”

“Áno, už vidím, takže keď budem takto pokračovať, dostanem nakoniec \(4, 6, 3, 3, 4, 3\),” dopovie Zebra.

“Presne tak,” prikývne Amanda. “A teraz čo myslíš, vedela by si zistiť, z akého stromu vznikla táto postupnosť?” spýta sa a ukáže na jej posledný zápis.

Úlohy

“Hmm, ako by som mohla začať…” zamyslí sa Zebra, “tak viem, že začneš oberať listy, tak by sa asi zišlo vedieť, aké čísla majú ony.”

1. (10 bodov) Máme postupnosť, ktorá vznikla z nejakého stromu. Ako z nej zistíme, aké čísla mali pôvodné listy toho stromu?

“Výborne, a čo ďalej?” pýta sa Amanda.

2. (30 bodov) Ako sa dá z postupnosti zistiť, z akého stromu vznikla? Vymysli taký postup, pomocou ktorého sa to bude dať zistiť pre hocijakú danú postupnosť.

Okrem toho by postup nemal byť až príliš pomalý, teda napríklad neprichádza do úvahy skúsiť každý možný strom, nájsť preňho tú postupnosť a zistiť, ktorá sedí.

“Mám to, napríklad z tohto!” poteší sa Zebra, keď sa jej konečne podarí nájsť správny strom.

“Napríklad?” čuduje sa Amanda. “A myslíš, že by mohol byť aj iný?”

3. (20 bodov) Môže sa stať, že rovnakú postupnosť dostaneme aj z viacerých rôznych stromov?

Stromy považujeme za rôzne, ak dva vrcholy s nejakými číslami v jednom susedia a v druhom nie. Nezáleží napríklad na poradí detí, alebo ako presne je strom nakreslený – strom sa dá väčšinou nakresliť viacerými rôznymi spôsobmi.

“Tak, a teraz ti ja dám príklad,” zasmeje sa Zebra. “Z akého stromu dostaneš…” a povie asi dvadsať náhodných čísel.

“Veď ale to je hlúposť, to nie je zo žiadneho stromu, to si si práve vymyslela,” namieta Amanda.

“No áno, vymyslela,” prizná Zebra, “ale aj tak existuje nejaký strom, z ktorého by si dostala akurát túto postupnosť.”

4. (20 bodov) Máme nejakú postupnosť \(n - 1\) čísel v rozsahu od \(1\) do \(n\). Existuje pre každú takú postupnosť nejaký strom, z ktorého dostaneme akurát tú postupnosť? Alebo existuje taká postupnosť, ktorú nedostaneme zo žiadneho stromu?

“No je to zaujímavé, tieto tvoje postupnosti,” povie Zebra, “ale pozri, už zapadá slnko, mala by som ísť domov.”

“Hej, pravda,” uznáva Amanda, “inak ale pozri, aký je tu pekný výhľad, keď zapadá slnko, a tam v diaľke, koľko tam je stromov, a predsa každý z nich je iný…”

“Hej, naozaj, koľko?” vytrhne Zebra Amandu zo zasnených úvah.

5. (20 bodov) Koľko existuje rôznych stromov, ktoré majú presne \(n\) vrcholov?

Obe žirafy sa na chvíľu zamyslia. “Ale veď to je jasné!” zakričí po chvíli Zebra a vysvetlí Amande, prečo to tak je.

A tak sa obe žirafy, spokojné, že sa im podarilo vyriešiť všetky úlohy, poberú domov.