Opravovatelia

Mišo M. [email protected]

Na začiatok sa zamyslime nad tým, kde sa môžu jednotlivé perníčky nachádzať. Perníček číslo $8$ už je v batôžku. Pred tým, ako ho tam Ďuro vložil sa musel nachádzať na kôpke. Predtým, ako mama vyložila na kôpku perník číslo $8$, musela na kôpku uložiť perníčky $1$ až $7$. Vieme teda, že tieto perníčky sú buď na kôpke, alebo v batôžku. O perníčku číslo $9$ nevieme nič. Môže byť už zbalený, môže byť na kôpke, ale nemusel sa zatiaľ dostať ani tam.

Zabudnime teda na chvíľu na číslo $9$ a pozrime sa na to, ktoré perníčky z $1$ až $7$ môžu byť na kôpke. Ďuro určite mohol zobrať perníček hneď po tom, ako ho mama dala na kôpku. Takže ktorýkoľvek perníček môže byť v batôžku. Rovnako tak mohol Ďuro s balením počkať, kým mama nepridala ďalší, čiže ktorýkoľvek perníček môže byť stále na kôpke, bez ohľadu na to, ktoré perníčky zbalil. Pre každý z týchto sedem perníčkov tak máme dve nezávislé možnosti – buď je na kôpke alebo v batôžku – čiže máme dokopy $2^7 = 128$ možností. Zároveň si uvedomme, že pre každú z týchto možností je aj poradie na kôpke dané jednoznačne. Ani Ďuro, ani mama uberaním či pridávaním nemenia poradie perníčkov, takže sú zoradené zdola nahor od najmenšieho čísla po najväčšie.

Tým pádom je aj vzájomné poradie balenia perníčkov $1$ až $7$ dané jednoznačne pre každú možnosť. Otázkou zostáva, kedy zabalíme perníček číslo $9$. Ak už je zabalený, tak máme $128$ možností, ako zabaliť zvyšné. Ak už je na kôpke, tak je určite navrchu, takže najprv zabalíme jeho a potom pre zvyšné perníčky máme ďalších $128$ možností. Ak však na kôpke nie je, tak výsledné poradie záleží od toho, kedy ho tam mama položí.

Dopočítanie pomocou

kombinačných čísel

Označme $k$ počet perníčkov, ktoré sú na kôpke. Ďuro zabalí niekoľko z nich predtým, ako mama na kôpku položí perník číslo $9$. Potom musí Ďuro zbaliť ten, a už mu zostane len dobaliť zvyšok. Ak mama položí perník číslo $9$ predtým, ako Ďuro zabalí aspoň jeden perník z kôpky, výsledné poradie bude rovnaké, ako by tam perník už ležal od začiatku. Zaujímajú nás teda možnosti, kedy mama uloží perník po prvom, po druhom, …, po $k$-tom zbalenom perníku. Takže máme $k$ nových možností.

Pre konkrétne $k$ máme ${7 \choose k}$ možností, ktoré perníčky sú na kôpke. Pre každú možnú kôpku zas máme $k$ možností, kedy sa na nej objaví perníček číslo $9$. Dokopy je to $k \cdot {7 \choose k}$ možných poradí. Počítajme teda:

• Ak $k = 1$, dostaneme $1 \cdot {7 \choose 1} = 7$ poradí.

• Ak $k = 2$, dostaneme $2 \cdot {7 \choose 2} = 42$ poradí.

• Ak $k = 3$, dostaneme $3 \cdot {7 \choose 3} = 105$ poradí.

• Ak $k = 4$, dostaneme $4 \cdot {7 \choose 4} = 140$ poradí.

• Ak $k = 5$, dostaneme $5 \cdot {7 \choose 5} = 105$ poradí.

• Ak $k = 6$, dostaneme $6 \cdot {7 \choose 6} = 42$ poradí.

• Ak $k = 7$, dostaneme $7 \cdot {7 \choose 7} = 7$ poradí.

Dokopy tak máme $2 \cdot 128 + 7+42+105+140+105+42+7 = 704$ poradí, v ktorých mohol Ďuro zabaliť zvyšné perníčky.

Dopočítanie bez kombinačných

čísel

Možnosti, kedy je perníček číslo $9$ na kôpke alebo zbalený, už máme spočítané. Rovnako ako vyššie si uvedomíme, že ak perníček číslo $9$ položí mama na kôpku skôr ako Ďuro zabalí prvý perníček, tak dostaneme rovnaké poradie, ako keby tam perníček číslo $9$ už ležal od začiatku.

V opačnom prípade existuje nejaký perníček s číslom $x$ (od $1$ po $7$), ktorý Ďuro zbalí tesne predtým, ako sa na kôpke objaví číslo $9$. Výsledné poradie balenia teda bude: najprv perníčky s číslom väčším ako $x$ (ak také na kôpke sú), potom perníček s číslom $x$, potom číslo $9$, a nakoniec perníčky s číslom menším ako $x$ (ak také sú). Pre dané číslo $x$ teda poradie závisí len na tom, ktoré perníčky boli okrem neho na začiatku na kôpke. Každý zo zvyšných $6$ perníčkov tam buď bol, alebo už bol zbalený, takže máme $2^6 = 64$ možností. Číslo $x$ zas môžeme vybrať $7$ spôsobmi. Pribudne nám teda $7 \cdot 64 = 448$ možností.

Hľadaný počet možných poradí tak je $2 \cdot 128 + 7 \cdot 64 = 704$.