5. Koľko máme stromov?
Zadanie
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.”
a. (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.
b. (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ý?”
c. (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ť.”
d. (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.
e. (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.
a. Čo sú listy?
Ako vieme z minulého kola, každý vrchol sa v postupnosti nachádza toľko krát, koľko má detí. Listy sú tie vrcholy, ktoré nemajú deti, sú to teda tie (z rozsahu $1$ až $n$), ktoré v postupnosti nie sú.
b. Ako zrekonštruovať strom?
Na začiatku odtrhneme list s najmenším číslom. To, aké máme listy, vieme z úlohy A. Okrem toho z postupnosti vieme, ktorý vrchol je rodič odtrhutého listu.
Budeme si teda takto postupne stavať strom. Začneme od listov, ale z tohto prvého kroku vieme k najmenšiemu listu pridať rodiča.
Čo ďalej? Predstavme si, čo sa stane ďalej. Z pôvodného stromu sme odtrhli najmenší list, čím sme dostali nový, menší strom. Zároveň sme si zapísali prvé číslo do postupnosti.
Z tohto nového stromu budeme ďalej trhať podľa rovnakých pravidiel a dostaneme tak zvyšok postupnosti. Keď sa nám teda podarilo takto spätne zistiť prvý krok, podobne vieme spätne zistiť aj všetky ďalšie kroky, až kým nepostavíme celý strom.
Ako to teda celé spravíme? Budeme postupne čítať postupnosť, popritom stavať strom a pamätať si, ktoré vrcholy sú aktuálne (na tom mieste v postupnosti) listy.
V každom kroku nám aktuálne číslo postupnosti hovorí, čo je rodič aktuálne najmenšieho listu. Teda si zoberieme najmenší z aktuálnych listov a “zavesíme” ho pod vrchol, ktorý má byť jeho rodič. Tento list bol potom odtrhnutý, takže už nebude list. Jeho rodič sa možno stane listom, to vieme podľa toho, či sme mu odtrhli všetky deti (z minulého kola vieme ich počet).
Tieto kroky teda budeme opakovať dovtedy, kým nepostavíme celý strom.
Príklad rekonštrukcie stromu
Chcelo by to ešte nejaký príklad, tak sa pozrime na ten, čo bol v zadaní: $4, 6, 3, 3, 4, 3$.
Vieme, že listy sú $1, 2, 7$, najmenší je $1$. Jeho rodič je $4$, takže pripojíme $1$ pod $4$. Potom bude jednotka odtrhnutá, ale štvorka má dve deti, takže sa ešte nestane listom.
V ďalšom kroku je najmenší list $2$, jeho rodič je $6$, takže pripojíme dvojku pod šestku. Je to jediné dieťa šestky, takže šestka sa stane listom.
Ďalej je najmenší list $5$, jeho rodič je $3$, nestáva sa listom. Ďalšia na rade je $6$, pripojíme ju (aj s dvojkou pod ňou) pod $3$, trojka sa stále nestáva listom. Potom sedmička, čím sa štvorka stane list a nakoniec štvorka, čím sa listom stane aj trojka. To už je posledný vrchol, takže sme skončili a máme celý strom.
c. Je to jednoznačné?
Takto vieme z každej postupnosti jednoznačne spätne dostať strom, z ktorého vznikla. Teda nielenže dostaneme nejaký taký strom, ale dokonca vieme, že to je jediný možný (vždy keď staviame strom, tak vieme, že to musí byť práve tak).
Nemôžu teda z dvoch rôznych stromov vzniknúť rovnaké postupnosti, lebo potom by sme ich nevedeli takto spätne postaviť, ale by to vieme.
d. Existuje ku každej postupnosti strom?
S každou možnou postupnosťou vieme skúsiť spraviť postup, ktorý sme popísali v úlohe B. Ak sa nám ho podarí spraviť, tak dostaneme nejaký strom. Jediné, čo by sa mohlo pokaziť, je že sa minú listy skôr, ako to dokončíme, alebo sa nám práveže neminú ani na konci, a teda to nebude strom, ale niekoľko stromov.
Poďme teda sledovať, koľko máme kedy listov. Dajme tomu, že na začiatku ich je $k$, potom v postupnosti musí byť $n - k$ (rôznych) nelistov. V každom kroku odtrhneme jeden list, ale ak sme tým odtrhli posledné dieťa, tak sa namiesto toho stane listom rodič.
Vždy najneskôr vtedy, keď odtrhneme všetky aktuálne listy, sa nám uvoľní nový list (lebo už nemá čo byť pod ním). Listy sa nám teda určite neminú príliš skoro.
Počas celého postupu odtrhneme $n - 1$-krát nejaký list, na začiatku ich máme $k$, a medzičasom ich ešte pribudne $n - k$ (za každé rôzne číslo v postupnosti jeden, keď mu odtrhneme posledné dieťa). Počet listov bude teda na konci $k + (n - k) - (n - 1) = 1$, teda naozaj dostaneme jeden strom.
e. Koľko máme stromov?
Keby sme túto úlohu chceli vyriešiť samostatne bez toho, že by sme vedeli o týchto postupnostiach, zistili by sme, že je to ťažšie, ako sa na prvý pohľad zdá.
Lenže my už vieme, že z každého stromu dostaneme práve jednu postupnosť a z každej postupnosti spätne dostaneme práve jeden strom. Stromov teda musí byť toľko čo postupností.
No a počet postupností, na rozdiel od počtu stromov, vieme zistiť pomerne ľahko. Postupnosti sú tvorené $n - 1$ číslami od $1$ po $n$, teda ich je spolu $n^{n - 1}$, a toľko teda bude aj stromov.
Načo sú tie postupnosti?
Zaujímavosť na záver: to, že to končilo úlohou zistiť počet stromov, vôbec nie je náhoda. Matematici sa o to snažili už dlho, zdalo sa, že má vyjsť $n^{n - 1}$, čo vyzerá ako jednoduchý vzorec, ale nikto to nevedel dokázať.
Toto oberanie bolo vymyslené na to, aby dokázali, že to tak naozaj je. Pomocou toho previedli ťažkú úlohu (zistiť počet stromov) na ľahkú úlohu (zistiť počet postupností). Dnes je už známych niekoľko rôznych dôkazov toho, koľko je stromov, ale žiadny nie je úplne priamočiary.
Zaujímavé je ešte to, že je nutné, aby vrcholy boli očíslované. Ak rátame počet stromov bez očíslovaných vrcholov (a teda vrcholy považujeme za nerozlíšiteľné), tak na to nie je známy žiadny vzorec, xa dokonca zrejme taký vzorec ani neexistuje.