Zadanie
Cestou na Veľkú Moravu uvažoval Konštantín nad metodológiou edukácie teológie v reáliách slovanských. Ako erudovaný filozof po exorbitantnom elaborovaní prišiel na meritórnu ideu a riekol: „Čuj, Metod, Slovanom sa Božie slovo lepšie učiti bude, pokiaľ mu porozumäti schopní budú. Tož, pre jazyk slovanský, je potrebné písma vytvoriti, aby sme do jazyka ľudu slovo Božie mohli preložiti.“ A Metod odvetil: „OK.“
Postup tvorby slovanského písma využíva rozpisovanie. Pod rozpísaním postupnosti rozumieme nasledovnú operáciu: Danú postupnosť prirodzených čísel \((a_1,\dotsc,a_n)\) nahradíme postupnosťou \((1,2,\dotsc,a_1-1,a_1,1,2,\dotsc,a_2-1,a_2,1,2,\dotsc,a_3-1,a_3,\dotsc,1,2,\dotsc,a_n-1,a_n)\), teda každý prvok \(p\) nahradíme prvkami \(1,2,\dotsc,p\). Konštantín si zobral postupnosť \((1,2,\dotsc,9)\) a rozpísal ju \(n\)-krát. Teraz ho zaujíma vzhľadom na \(n\), koľko čísel bude v postupnosti a koľko z nich sú jednotky. To mu umožní konštantovať, či už ide o písmo finálne.
V riešení tejto úlohy budeme využívať kombinácie a kombinačné čísla. Kombinačné číslo \(\binom{n}{k} = \frac{n!}{(n-k)!k!}\) nám hovorí, koľkými spôsobmi vieme vybrať \(k\) prvkov z \(n\) prvkov (napríklad koľkými spôsobmi si vieme z \(n\) žiakov vybrať \(k\), ktorých pošleme na súťaž). Ak si sa s kombinačnými číslami ešte nestretol/la, odporúčam zhliadnuť nasledovné video1.
Na úvod by som rozhodne odporučil, aby ste si rozmysleli, ako bude daná postupnosť vyzerať po jednom, prípadne dvoch rozpísaniach (čo nám pomôže vybudovať si základnú intuíciu ohľadom úlohy).
Nazvime si postupnosť vzniknuvšiu po \(n\) rozpísaniach ako \(n\)-tú generáciu čísel. Zamyslime sa teraz spoločne nad pôvodom ľubovoľného čísla v \(n\)-tej generácii. Nech pre lepšiu názornosť je to napr. číslo \(5\).
Všimnime si, že číslo \(5\) vzniklo buď rozpísaním iného čísla \(5\) z predošlej generácie, alebo rozpísaním nejakého väčšieho čísla z predošlej generácie. Poďme sa ale lepšie zamyslieť nad celým „rodokmeňom“.
Zoberme si nejaké číslo \(5\) z napr. \(4.\) generácie. Ako mohla táto päťka vzniknúť? Uvedomme si, že táto päťka musí mať jednoznačne daný ,,rodokmeň", napríklad \(8 \xrightarrow{} 6 \xrightarrow{} 6 \xrightarrow{} 5 \xrightarrow{} 5\). Tento zápis znamená, že naša päťka je potomkom osmičky z nultej generácie, ktorej potomkom v prvej generácii sa stala \(6\)-ka, ktorej potomkom sa v druhej generácii stala opäť \(6\)-ka, potomkom ktorej bola \(5\)-ka, z ktorej vznikla v štvrtej generácii naša \(5\)-ka. V štvrtej generácii budeme mať potom toľko pätiek, koľko rôznych rodokmeňov vieme vytvoriť.
Všimnime si, že tento rodokmeň je vždy nerastúci (čiže napríklad potomkom \(3-\)ky už nikdy nebude \(4\), ani žiadne väčšie číslo).
A teraz na rad príde menší trik. Uvedomme si, že ľubovoľný rodokmeň vieme jednoznačne zakódovať pomocou binárneho kódu. Napr. rodokmeň \(8 \xrightarrow{} 6 \xrightarrow{} 6 \xrightarrow{} 5 \xrightarrow{} 5\) vieme zakódovať ako \(10110010\). Cifry \(0\) v tomto kóde fungujú ako oddeľovač generácií. Cifry \(1\) fungujú ako pokles hodnoty v predošlej generácii. Počet jednotiek na začiatku nám teda v podstate iba určí, od akého čísla chceme v nultej generácii začať. Čiže v našom prípade v \(0.\) generácii poklesneme jednotkou z \(9\) na \(8\), prejdeme nulou do \(1.\) generácie, prostredníctvom dvoch jednotiek znížime hodnotu o \(2\) na \(6\), nulou prejdeme do ďalšej generácie, znova nulou prejdeme do ďalšej generácie… Pre lepšiu názornosť uvedieme zopár alternatívnych prípadov: \[\begin{align} 9 \xrightarrow{} 8 \xrightarrow{} 8 \xrightarrow{} 6 \xrightarrow{} 5 &\Rightarrow 01001101,\\ 7 \xrightarrow{} 7 \xrightarrow{} 7 \xrightarrow{} 7 \xrightarrow{} 5 &\Rightarrow 11000011,\\ 9 \xrightarrow{} 8 \xrightarrow{} 7 \xrightarrow{} 6 \xrightarrow{} 5 &\Rightarrow 01010101.\end{align}\]
Ako teda vyzerajú všetky kódy, ktorými vieme v štvrtej generácii získať číslo \(5\)? Keďže z deviny musíme poklesnúť na päťku, v kóde potrebujeme \(4\) jednotky. No a keďže musíme prejsť z \(0.\) generácie do \(4.\), potrebujeme \(4\) jednotky. Každý kód obsahujúci \(4\) jednotky a \(4\) nuly potom jednoznačne určuje práve jednu päťku zo \(4.\) generácie. A naopak, každej päťke v štvrtej generácii vieme priradiť práve jeden takýto kód.
Celkovo bude teda v štvrtej generácii toľko pätiek, koľko vieme takýchto kódov vytvoriť. Tieto kódy majú \(8\) pozícií a z nich si musíme vybrať \(4\) pozície, ktoré určíme ako \(0\) (zvyšné budú \(1\)). To máme spolu \(\binom{8}{4} = 70\) možností (čiže spolu \(70\) pätiek).
No a keď už máme predstavu, ako to celé funguje, stačí nám už iba naše úvahy zovšeobecniť. Druhá podotázka z úlohy sa nás pýta, koľko jednotiek budeme mať v \(n\)-tej generácii. A teraz sa skúste zamyslieť sami! Ako budú vyzerať kódy, ktoré budeme obdobným spôsobom priraďovať jednotkám v \(n\)-tej generácii? No dobre, ja vám to teda poviem…Tieto kódy musia pozostávať z \(8\) jednotiek (musíme poklesnúť z \(9\) na \(1\)) a \(n\) núl (prechádzame medzi \(n\) generáciami).
A koľko takýchto kódov vieme vytvoriť? Každý kód má spolu \(n+8\) pozícií, pričom si potrebujeme vybrať \(8\), ktoré určíme ako jednotky (zvyšné budú nuly). Dohromady teda máme \(\binom{n+8}{8}\) kódov.
Odpoveď: Po \(n\) rozpísaniach budeme mať \(\binom{n+8}{8}\) jednotiek.
Joooj, a teraz musíme ešte pracne spočítať, koľko bude po \(n\) rozpísaniach všetkých čísel…Alebo nemusíme?! Ej veru, všimnime si, že z každého čísla v \(n\)-tej generácii vznikne v \((n+1)\)-vej generácii práve jedna jednotka. Všetkých čísel po \(n\) rozpísaniach je teda presne toľko, koľko je jednotiek po \(n+1\) rozpísaniach, čiže dokopy \(\binom{n+1+8}{8}= \binom{n+9}{8}\) čísel.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.