3. Komanč Mocný Syseľ vzorové riešenie

K tejto úlohe máme videonávod.

V ľubovoľnej možnosti, ako rozdeliť skalpy pre náčelníkov, majú Winnetou, Apasuke a Komanke aspoň jeden skalp. Dajme im teda po jednom skalpe a zamerajme sa na to, ako rozdeliť zvyšných \(44\) skalpov.

V tejto situácii chce každý náčelník dostať ešte nejaký párny počet skalpov. Zároveň máme ešte párny počet skalpov, ktoré sme nepoužili (čo je dobre, skúste si premyslieť, čo by znamenalo, keby máme v tomto bode nepárny počet skalpov na rozdelenie). Môžeme teda riešiť analogický problém – rozdeľme \(22\) párov skalpov medzi \(5\) náčelníkov.

V tejto časti je dôležité si veľmi dobre premyslieť, či týmto postupom nezarátame nejaké možnosti dvakrát, či na nejakú možnosť nezabudneme, alebo či nenájdeme nejakú možnosť, ktorá neprislúcha žiadnemu rozdeleniu skalpov. Zoberme si ľubovoľné rozdelenie dvojičiek. Ak si označíme postupne počty dvojičiek pre náčelníkov \(a, b, c, d, e\), potom vieme, že platí \(a + b + c + d + e = 22\). Takémuto rozdeleniu dvojičiek zodpovedá rozdelenie skalpov, kde náčelníci dostanú postupne \(2a, 2b, 2c+1, 2d+1, 2e+1\) skalpov, kde si môžeme overiť, že \(2a + 2b + (2c+1) + (2d+1) + (2e+1) = 47\). Môžeme si taktiež premyslieť, že rovnako to funguje aj naopak – ku každému rozdeleniu skalpov vieme nájsť prislúchajúce rozdelenie dvojičiek. Tým pádom vieme s istotou povedať, že keď spočítame všetky možné rozdelenia dvojičiek, bude sa tento počet rovnať počtu všetkých možných rozdelení skalpov.

Poďme teda rozdeliť \(22\) dvojičiek medzi \(5\) náčelníkov. Môžeme použiť techniku „oddeľovačov“. Zoraďme si \(22\) dvojičiek vedľa seba do radu. Zoberme si \(4\) oddeľovače a uložme ich medzi nejaké dve susediace dvojičky (kde oddeľovače nemusia byť nutne medzi rôznymi susedmi). Takto sme rozdelili všetky dvojičky do \(5\) skupín. Teraz vieme dvojičky prideliť náčelníkom tak, že každému náčelníkovi dáme všetky dvojičky z jednej skupiny.

Tu je taktiež dôležité uviesť, že takýmto postupom zarátame každé rozdelenie dvojičiek práve raz, a nevytvoríme také usporiadanie dvojičiek a oddeľovačov, ktoré nezodpovedá žiadnemu rozdeleniu dvojičiek. Už sme si ukázali, ako sa od konkrétneho usporiadania dvojičiek a oddeľovačov vieme dopracovať k rozdeleniu dvojičiek pre náčelníkov. Ľahko vieme popísať aj opačný postup. Ak vieme, koľko dvojičiek má ktorý náčelník, jednoducho uložíme všetky dvojičky prvého náčelníka vedľa seba a na koniec dáme oddeľovač. Potom spravíme to isté s dvojičkami druhého, tretieho a štvrtého náčelníka, a na konci už iba pridáme dvojičky posledného, bez oddeľovača na konci (môžete si to predstaviť ako vykladanie nákupu v obchode na pokladničný pás – každý si vyloží svoj nákup a dá zaň oddeľovač). Znova teda platí argument, že ak porátame koľko existuje možných spôsobov rozdelenia dvojičiek a oddeľovačov, nájdeme zároveň počet všetkých možných rozdelení dvojičiek náčelníkom.

Ako však zistiť, koľkými spôsobmi môžeme umiestniť oddeľovače? Všimnime si, že po umiestnení oddeľovačov máme v rade \(26\) objektov (\(22\) dvojičiek a \(4\) oddeľovače). Pre ľubovoľné rozmiestnenie platí, že máme \(26\) miest, na ktorých môžu dvojičky a oddeľovače byť. Čo robí konkrétne rozloženie unikátnym, je pozícia oddeľovačov. Musíme teda vybrať \(4\) z \(26\) miest, kam oddeľovače uložíme. Keďže vyberáme miesta bez opakovania a na poradí jednotlivých oddeľovačov nezáleží, odpoveď na otázku koľkými spôsobmi vieme vybrať \(4\) z \(26\) miest nám dajú kombinačné čísla¹. Tomuto počtu zodpovedá kombinačné číslo \[\binom{26}{4}=\frac{26!}{4!22!}=14\,950.\] Náčelníci si teda vedia rozdeliť skalpy \(14\,950\) spôsobmi.