2. Krejzy Monstr Sirkus (κ ≤ 2) vzorové riešenie

Zadanie

Crazy Monsters Circus vlastní \(n\) zvieratiek. Predvádzajú s nimi akrobatické kúsky na červenom a modrom podstavci, na ktoré sa zvieratká stavajú do rôznych pozícií. Jedna pozícia vyzerá nasledovne: Všetky zvieratká sú rozdelené na dve skupiny. Jedna skupina tvorí vežu na červenom podstavci, druhá na modrom podstavci. Žiadne zvieratko neostane mimo. Veža z \(k\) zvieratiek vyzerá tak, že prvé zvieratko stojí na podstavci, druhé stojí na prvom zvieratku, tretie na druhom a tak ďalej až \(k\)-te zvieratko stojí na \((k-1)\)-vom zvieratku. V závislosti od kladného celého čísla \(n\) určte, koľko rôznych pozícií môžu zvieratká zaujať.

Pozície, ktoré sa líšia usporiadaním zvieratiek na podstavcoch, pokladáme za rôzne. Pre lepšiu názornosť na obrázku nižšie uvádzame zopár (nie nutne všetky) pozícií pre \(3\) zvieratká. Všimnite si, že všetky pozície sú rôzne.

V úlohách, ktoré hľadajú všeobecný vzorec pre \(n\) je vhodné najprv sa pozrieť, ako nám výsledok vychádza pre malé hodnoty, napr. \(n = 1, 2, \cdots\). To nám môže dosť pomôcť v nájdení všeobecného vzorca, no nie je to všetko. Nemôžeme len tak povedať, že pre \(n = 1, 2\) to platí, a teda to bude platiť vždy. Potrebujeme ukázať, že to naozaj tak bude vo všeobecnosti, čo si aj ukážeme. Okrem toho ďalším vhodným postupom môže byť aj matematická indukcia. Pre tých, čo o nej doteraz nepočuli, článok o nej nájdete napríklad v Zbierke KMS, ktorá je dostupná aj online.

Pozrime sa teda najprv na malé hodnoty \(n\). Pre \(n = 1\) máme len \(2\) možnosti, buď je zvieratko na modrom podstavci, alebo je na červenom. Ak vezmeme \(n = 2\), začína to byť zaujímavejšie. Skúsme sa zamyslieť nad tým, kde môže byť druhé zvieratko. Druhé zvieratko môže buď ísť na iný podstavec ako prvé, alebo vyskočiť na chrbát prvého zvieratka, alebo môže vziať prvé zvieratko na plecia. Celkovo má teda \(3\) možnosti. Treba ale vziať do úvahy aj to, že prvé zvieratko má \(2\) možnosti, kam sa postaví. Ku každej z tých možností pripadajú \(3\) možnosti pre druhé zvieratko, teda dokopy je možností \(6\). Vypísaním možností sa dá prísť aj na to, že pre \(n = 3\) je \(24\) možností, teda \(4\) možnosti pre tretie zvieratko.

Nejaký nápad na vzorec by sme takto mohli dostať (vyzerá to tak, že \(n\)-té zvieratko má vždy \(n+1\) možností, teda celkový počet možností bude \((n+1)!\)), no treba aj overiť, či je ozaj správny. Skúste si premyslieť, že v skutočnosti je rovnako správne rozmýšľať nad dvomi podstavcami ako nad jedným poradím zvieratiek, ktoré je v nejakom mieste oddelené čiarou, ktorá znamená predel medzi podstavcami.

Keď prichádza nové \(n\)-té zvieratko, v tomto poradí už ich je \(n-1\). Koľkými spôsobmi môže byť zapísaných \(n-1\) čísel (zvieratká) do poradia? Na prvé miesto \(n-1\), na ďalšie \(n-2\) a tak ďalej. Celkovo je to \((n-1)!\) Na koľko rôznych miest môže prísť nové zvieratko? Môže prísť na ľubovoľné miesto od \(1\) po \(n\), teda má n možností. Zamyslieť sa však musíme ešte nad tým, že máme dva podstavce, čiže niekam musíme dať čiaru. Podobnou úvahou ako pred chvíľou zistíme, že možností pre čiaru je \(n+1\). A to je všetko, máme \(n\) zvieratiek na dvoch podstavcoch. Koľko teda bolo možností pre \(n\) zvieratiek?

Pre \(n\) zvieratiek je \((n-1)! \cdot n \cdot (n+1) = (n+1)!\) možností.