9. príklad - Vzorové riešenie

V zadaní bolo napísané Dokážte pre ľubovoľné kladné celé k. Najprv si teda povedzme, čo takéto zadanie znamená a ako sa takéto úlohy riešia.

Ak máme nejaké tvrdenie dokázať pre ľubovoľné číslo (alebo čokoľvek iné, napríklad ľubovoľné usporiadanie tabuľky, ľubovoľné rozloženie figúrok...), nestačí si vybrať jedno číslo, napríklad k = 2 a ukázať, že pre tento prípad tvrdenie platí. Treba prejsť všetky prípady, od k = 1, k = 2, ..., k = \frac{n}{2}​. Ak je týchto prípadov nejaký konkrétny počet, tak to naozaj môžeme dokazovať tak, že prejdeme každú možnosť a ukážeme, že tvrdenie vždy platí (napríklad ak by sme mali zadané, že n \le 10​, tak nám zostane iba päť možností na k a môžeme prejsť všetky). Ako ale prejsť všetky prípady, keď nevieme, koľko ich je, alebo je ich dokonca nekonečno?

Najčastejší spôsob, ktorým sa takéto úlohy riešia je, že sa pozrieme na to, čo majú všetky možnosti spoločné a ukážeme z toho, že tvrdenie platí. Keďže pri tom vychádzame z toho, čo majú všetky možnosti spoločné, mohli by sme prejsť všetky možnosti a toto zdôvodnenie použiť pri každej. Teda síce nevieme prejsť všetky možnosti posupne, ale môžeme sa takto "pozrieť na všetky naraz".

Na začiatku máme jednu živú baktériu. Môžeme si ju nakreslit takto:

​

Teraz povedzme, že by sa tá baktéria rozmnožila. Tým ona umrie, ale vzniknú dve nové. Môžeme si to nakresliť:

Živé baktérie kreslím zelenou a mŕtve červenou. Povedzme, že by sa teraz jedna z tých dvoch živých baktérií rozmnožila.

Takto môžeme kresliť ďalej, až sa dostaneme ku konečnému obrázku, ktorý môže vyzerať napríklad takto:

Na konkrétnom umiestnení baktérií nezáleží, dôležité je, že každá baktéria je spojená nahor s baktériou, z ktorej vznikla. Môžeme si všimnúť, že každá červená baktéria má dve "deti". Počet potomkov nejakej baktérie môžeme zistiť tak, že sa pozrieme na to, koľko je zelených baktérií, ktoré sú niekde pod ňou (nie nutne priamo spojené s ňou, môžu byť spojené cez niektoré ďalšie, ale iba smerom dole).

Preto keď máme jednu baktériu, ktorá sa rozdelila na dve, tak počet jej potomkov je súčet počtov potomkov tých dvoch baktérií, ktoré vznikli jej rozmnožením (napríklad ak sa jedna baktéria rozmnožila na dve, z ktorých jedna má troch potomkov a druhá štyroch, tak táto má sedem).

Máme teda takýto obrázok, kde je n​ zelených baktérií. Chceli by sme teda nájsť nejakú takú, ktorá má aspoň k​ a najviac 2k​ potomkov. Ako by sme ju mohli nájsť?

Je ľahké nájsť baktériu, ktorá má aspoň k potomkov - môžeme napríklad zobrať tú prvú, ktorá je na vrchu nášho obrázka. Ak by mala zároveň najviac 2k​ potomkov, tak výborne - našli sme ju. Ak má viac, ako 2k potomkov, musíme hľadať ďalej - nájsť nejakú baktériu, ktorá má menej potomkov, ako ona. Vieme, že jej dve "deti" majú dokopy toľko potomkov, ako ona, teda viac, ako 2k. Preto aspoň jeden z nich musí mať viac, ako k​ potomkov (ak by obaja mali najviac k​, tak ich súčet je najviac 2k). Takže ak sa pozrieme na to jej "dieťa", ktoré má viac potomkov, tak sme našli baktériu, ktorá má menej potomkov, ako tá, ktorú sme našli predtým, ale stále aspoň k​.

Ak má táto baktéria najviac 2k potomkov, tak sme ju našli. Ak má viac, tak sa môžeme pozrieť na jej deti, ak ani medzi nimi nenájdeme, tak na deti ich detí a tak ďalej. Takto nájdeme baktérie, ktoré majú stále menej a menej potomkov, ale stále aspoň k​. Keďže čísel medzi k​ a n je iba nejaký obmedzený počet, nemôžeme zmenšovať donekonečna a určite raz nájdeme takú baktériu, akú hľadáme. Taktiež sa nám nestane, že by baktéria už nemala deti, lebo ak má viac, ako 2k potomkov (najmenej troch, keďže k \ge 1​), tak sa musela ešte niekedy rozmnožovať.

Tento dôkaz funguje vždy rovnako bez ohľadu na výber n​ a k​ a bez ohľadu na poradie delenia baktérií. Preto sme ukázali, že pre každé n​ a k​ spĺňajúce podmienky zo zadania existuje baktéria s aspoň k​ a najviac 2k​ potomkami.