Zadanie
Po úmornom rmútení za bratom sa Metod pobral späť na Veľkú Moravu. Jeho útrapám však nebolo konca. Cestou ho totiž zajali sily pekelné konajúce prostredníctvom tých najhorších z najhorších – Frankov. Tí priviazali Metoda k betónovému pražcu a išli sa zo svojho činu vyspovedať. Keď sa však vrátili, po Metodovi nebolo ani chýru, ani slychu. Ako ho tak hľadali, narazili na studňu, pri ktorej stáli dvaja mládenci. Jeden z Frankov sa ich pýta: „Hallo Jungen, nevideli ste tu takého alte pána Metoda?“ Mládenci odvetili: „No, pred chvíľou tu taký starší pán prebehol a skočil do studne.“ „Aber, to nemohol byť náš Metod, on bol priviazaný o betónový pražec.“
Metodovi na dne studne neostávalo nič iné ako čakať na záchranu. Každý deň vyryl do kameňa inú postupnosť núl a jednotiek dĺžky \(2023\). Po \(n\) dňoch bol zachránený. Keď si zoberieme všetky podpostupnosti1 dĺžky \(1012\) všetkých postupností, ktoré Metod stihol za ten čas napísať, tak nedostaneme všetkých \(2^{1012}\) binárnych postupností dĺžky \(1012\). Aké je najväčšie možné \(n\)?
Podpostupnosť vznikne poškrtaním niektorých prvkov pôvodnej postupnosti. Napríklad \(\{2, 3, 5, 7\}\) je podpostupnosť postupnosti \(\{1, 2, 3, 4, 5, 6, 7\}\)↩
Ako prvé môžeme pri takejto úlohe skúsiť hľadať konštrukciu. Teda si vyberme nejakú podpostupnosť dĺžky \(1012\) a skonštruujme čo najviac postupností, ktoré neobsahujú túto postupnosť. No a ktorú podpostupnosť skúsime ako prvú? Najprirodzenejšie je zobrať podpostupnosť zo samých jednotiek (resp. núl). Môžeme si všimnúť, že presne polovica postupností dĺžky \(2023\) obsahuje viac núl ako jednotiek, napríklad preto, že keď popárujeme binárnu postupnosť s jej inverzom, práve jedna z dvojice bude obsahovať aspoň \(1012\) jednotiek. Teda \(n = 2^{2022}\) vyhovuje (uvažujeme všetky postupnosti s najviac \(1011\) jednotkami). Je to ale to najväčšie vyhovujúce \(n\)? Môžeme si to skúsiť na malých číslach a vidíme, že asi áno. Dokážeme, že to tak naozaj je.
Trikové riešenie (pravdepodobnostná metóda)
Sporom, ak by to tak nebolo, musela by existovať podpostupnosť \(S\) zapísaná ako \(a_1a_2\ldots a_{1012}\), ktorá by nebola obsiahnutá vo viac ako polovici postupností. Poďme sa teraz zahrať takú hru. Hoďme si férovou mincou. Ak padne hlava, zapíšme jednotku, ak padne znak zapíšme nulu. Toto spravme postupne \(2023\)-krát. Ak padne v prvom hode cifra \(a_1\), dostaneme bod. V opačnom prípade nedostaneme bod. Vždy, keď dostaneme bod po padnutí cifry \(a_i\), kde \(i<1012\), budeme chcieť v ďalších hodoch hodiť cifru \(a_{i+1}\) (za ňu dostaneme bod), až kým nedostaneme ďalší bod. Príklad: nech naša podpostupnosť je \(1000\ldots\). Pokiaľ na minci hodíme postupne \(01110\ldots\), body, ktoré postupne dostaneme, sú \(0, 1, 0, 0, 1, \dots\). Pokiaľ aj nazbierame všetkých \(1012\) bodov, pokračujme v hre ďalej (až do \(2023\) hodov), pričom dostaneme bod napríklad vždy práve vtedy, keď hodíme hlavu. Môžeme si všimnúť, že naša postupnosť obsahuje podpostupnosť \(S\) práve vtedy, keď sme nazbierali aspoň \(1012\) bodov. Aká je pravdepodobnosť, že sme nazbierali aspoň \(1012\) bodov? V každom hode sme mali na získanie bodu polovičnú pravdepodobnosť. Pravdepodobnosť, že sme viackrát získali bod ako nezískali je preto rovnaká ako pravdepodobnosť, že sme viackrát nezískali bod ako získali. Teda je to presne polovica. Pre náhodnú postupnosť máme teda polovičnú šancu, že obsahuje \(S\). Preto presne polovica postupností obsahuje \(S\). Z toho už vyplýva, že ak by bolo \(n>2^{2022}\), každá podpostupnosť \(S\) dĺžky \(1012\) by v nich bola obsiahnutá. Preto \(n = 2^{2022}\).
Poznámka: Podobný postup sa dá spraviť aj bez pravdepodobnostnej metódy, a to nájdením bijekcie medzi postupnosťami, ktoré obsahujú viac jednotiek ako núl a postupnosťami obsahujúcimi \(S\) (použitím rovnakého princípu ako pri hádzaní mince).
Klasické riešenie (indukcia)
Indukujme. Uvažujme ľubovoľnú podpostupnosť \(S\) dĺžky \(k\). Nech \(S'\) je \(S\) bez prvého bitu. Označme \(P(S, n)\) počet postupností dĺžky \(n\) obsahujúcich podpostupnosť \(S\). Pre \(n \geq 2\) si môžeme rozmyslieť rekurentný vzťah \(P(S, n) = P(S', n-1) + P(S, n-1)\). Pokiaľ je totiž prvý bit postupnosti zhodný s prvým bitom \(S\), už nám stačí, aby postupnosť z ďalších \(n-1\) cifier obsahovala \(S'\). Ak sa prvý bit nezhoduje, potrebujeme, aby zvyšok obsahoval \(S\). Teraz by sme z rekurencie mohli zrátať výraz všeobecne alebo odsledovať správanie, tipnúť a dokázať indukciou. Vyšlo by nám, že pre podpostupnosť \(S\) dlžky \(k\) platí \(P(S, n) = \binom{n}{n} + \binom{n}{n-1} + \ldots + \binom{n}{k}\), z čoho by sme potom dorátali, že pri \((n, k) = (2023, 1012)\) je to polovica súčtu 2023-tieho riadku Pascalovho trojuholníka, teda \(2^{2022}\). To ale nemusíme robiť. Stačí indukciou dokázať, že \(P(S, n) = P(T, n)\) pre všetky dvojice \(S, T\) dĺžky \(k\). To zrejme platí pre \(n = 1\). A z rekurencie \(P(S, n) = P(S', n-1) + P(S, n-1)\) dostávame indukčný krok, keďže \(P(S, n) = P(S', n-1) + P(S, n-1) = P(T', n-1) + P(T, n-1) = P(T, n)\). Preto pre každú podpostupnosť dĺžky \(1012\) je počet postupností dĺžky \(2023\) obsahujúcich danú podpostupnosť rovnaký. Pre podpostupnosť samých jednotiek sme už počet postupností zrátali, a je ich \(2^{2022}\). Preto \(n>2^{2022}\) nevyhovuje.
Každopádne, najväčšie \(n\) vyhovujúce zadaniu je \(n = 2^{2022}\).
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ť.