1. Poskladané náušnice
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ť.
Ak máš hocijaké otázky k tejto úlohe, napíš Miškovi na [email protected]
Krtko skúša novú módu: povedal si, že bude nosiť náušnice. Ale je trápne mať rovnaké náušnice ako všetci ostatní, tak si vyrobí vlastné. Vyrábať si ich bude z korálok.
Najzákladnejšia náušnica je jednoducho korálka. To ale nie je veľmi zaujímavé, takže to môže Krtko vylepšiť tým, že zavesí jednu korálku pod druhú a tak dostane novú náušnicu.
Takáto náušnica stále nie je veľmi zaujímavá. Krtko vie ale vyrobiť z dvoch takýchto náušníc ďalšiu. Zoberie každú z náušníc za tú korálku, za ktorú bola zavesená, a zavesí jednu pod druhú.
Náušnica, ktorá mu vznikne, potom bude vyzerať takto:
Toto potom môže opakovať: zoberie dve rovnaké náušnice a zavesí jednu pod druhú, čím dostane novú náušnicu.
Aby sa nám ľahšie hovorilo, ktoré náušnice sú ktoré, tak každej náušnici priradíme nejaký level. Samotné korálky sú level $0$, jedna korálka pod druhou je level $1$, náušnica na obrázku sú level $2$, a tak ďalej. Teda keď zavesím pod seba dve náušnice rovnakého levelu, tak dostanem o $1$ väčší level.
Úlohy
a. Nakresli, ako vyzerajú náušnice levelu $4$.
Krtko si takto skladal náušnice, až sa dostal k nejakému konkrétnemu levelu, označme ho $x$. Teraz by chcel vedieť nejaké vlastnosti tých svojich náušníc. V ďalších úlohách teda vymysli, ako vieš tú vlastnosť spočítať, keby ti Krtko povedal ten level, teda číslo $x$.
b. Koľko korálok má celá náušnica dokopy?
c. Koľko korálok je zavesených priamo za hlavnú korálku? Hlavná korálka je tá, za ktorú je zavesená celá náušnica.
Na obrázku je hlavná korálka tá modrá a priamo za ňu je zavesená červená a žltá. Zelená je až pod červenou, takže tá sa neráta.
Krtka toto skladanie náušníc veľmi zaujalo, a tak v tom pokračoval celkom dlho a dostal sa po náušnice s fakt vysokými levelmi. Tieto náušnice ale potom mali fakt veľa korálok, takže boli ťažké a Krtka z toho potom boleli uši.
Tak si Krtko povedal, že ich trochu odľahčí. Náušnice sa mu ale stále páčia a nechce z nich dať preč príliš veľa korálok, lebo to by potom už nevyzeralo pekne.
Rozhodol sa teda, že to spraví takto. Zoberie si tú svoju náušnicu (s levelom $x$) a odstrihne niektoré nite. Korálky, ktoré boli za tieto nite zavesené, spadnú dole a už v náušnici nebudú. Aby toho ale neodstrihol príliš veľa, tak spod každej korálky prestrihne najviac jednu niť, ktorá z nej priamo visí.
Na obrázku môže Krtko prestrihnúť napríklad niť medzi modrou a červenou, čím červená aj zelená korálka spadnú. Ostane iba modrá a žltá a niť medzi nimi Krtko nemôže odstrihnúť, lebo už odstrihol jednu niť, ktorá visela z modrej korálky.
Alebo by mohol odstrihnúť žltú a zelenú korálku. Potom ostane len modrá a červená, a červenú zase odstrihnúť už nemôže, lebo spod modrej už jednu odstrihol.
d. Keď bude Krtko strihať podľa týchto pravidiel, koľko najmenej korálok mu môže ostať na jeho novej náušnici?
Vzoráky z tohto kola si môžeš pozrieť aj ako video
A
Ružová je hlavná korálka.
B
Pri každom zvýšení levelu zoberieme celú náušnicu, skopírujeme ju a zavesíme pod hlavnú korálku, takže sa počet korálok zdvojnásobí.
C
Pri každom zvýšení levelu zavesíme kópiu tej pôvodnej náušnice pod hlavnú korálku, takže tam toho bude visieť o $1$ viac.
D
Keď máme náušnicu levelu $n$, tak pod hlavnou korálkou visia náušnice levelov postupne $1, 2, \dots, n - 1$. My môžeme jednu z nich odstrihnúť úplne a každú z tých zvyšných ostrihať tak, ako keby to bola samostatná náušnica.
Skúsme odstrihnúť celú tú najväčšiu náušnicu (takto sa zbavíme najviac korálok hneď v prvom kroku, takže vyzerá, že sa to oplatí). Potom nám ostane taký počet korálok, ako je súčet ostrihaných prvých $n - 2$ levelov. Keď teraz zvýšime level, tak si môžeme dovoliť odstrihnúť tú novú najväčšiu náušnicu, ale potom už nemôžeme odstrihnút tú druhú najväčšiu, ktorá bola odstrihnutá predtým celá. Pribudne nám teda toľko korálok, koľko bolo v ostrihanej náušnici levelu $n - 2$. Odpoveď pre ďalší level je teda súčet odpovedí pre posledné dva levely (a začíname $1, 1$).
Čo sa stane, ak odstrihneme celú nejakú inú náušnicu než tú najväčšiu? Potom sa nám tam namiesto nejakej menšej ostrihanej náušnice objaví tá najväčšia ostrihaná náušnica. Asi sa dá čakať, že tá najváčšia (aj keď bude ostrihaná), bude mať aspoň toľko korálok ako nejaká menšia (tiež ostrihaná). Je to naozaj tak? Pre prvých pár levelov to platí, a v tom prípade už vieme, že počet korálok v ďalšom leveli bude súčet posledných dvoch, čo je viac ako v predošlom leveli. To znamená, že aj pre ten nový level platí, že ostrihaná náušnica toho levelu má viac korálok ako ostrihané náušnice menších levelov. Takže to platí pre všetky levely, a tým pádom sa nám naozaj najviac oplatí odstrihávať tú najväčšiu.