Zadanie

Štyria rytieri – Liu, Zhen, Ning a David – sa vybrali na uhorský rytiersky turnaj. Žiaľ, vybrali sa tam príliš neskoro a v ich meste ostalo už len \(8\) koní – čierny, modrý, sivý, biely, hnedý, béžový, brontofúzikový a kapurkový.

Koľko je rôznych kombinácií, ako sa mohli do mesta vybrať, ak na jednom koni mohli ísť najviac dvaja rytieri a na čiernom aj modrom koníkovi musel ísť do mesta aspoň jeden rytier? Dve kombinácie považujeme za navzájom rôzne, ak aspoň jeden z rytierov prišiel na koni inej farby.

Možností ako mohli rytieri prísť do mesta je mnoho, dobrým začiatkom je rozdeliť si ich na niekoľko skupín, ktoré skúsime spočítať samostatne. Týchto rozdelení je viacero možných, v tomto vzorovom riešení to spravíme podľa toho, koľkí z rytierov išli spolu na koni. Sú tri rôzne skupiny možností ako mohli prísť do mesta – tie v ktorých išli rytieri ako dve dvojice, tie v ktorých išli ako jedna dvojica a dvaja samostatne, a nakoniec tie, v ktorých išiel každý sám. Máme tri skupiny, poďme každú spočítať.

Ak išli ako dve dvojice, vieme, že jedna dvojica išla na modrom koni a druhá na čiernom (na týchto dvoch koňoch musí vždy niekto jazdiť). Pozrime sa na modrého koňa – počet rôznych dvojíc, ktoré na ňom mohli ísť je kombinačné číslo 1 \(4\choose2\), pretože vyberáme dvoch rytierov zo štyroch a nezáleží nám na poradí v rámci danej dvojice. Tým, že určíme jednu dvojicu sme automaticky určili aj druhú. Celkový počet možností v prípade, že pôjdu rytieri ako dve dvojice je teda \(\binom 4 2=6\).

Druhá skupina možností je, že išli ako jedna dvojica a dvaja samostatne. Najprv nás zaujíma koľko je možností ako vytvoriť tú jednu dvojicu. Je to \(\binom 4 2\) tak ako v predchádzajúcej možnosti. Teraz ideme zisťovať koľko je možností ako rozdeliť tri posádky (jedna dvojica a dvaja samostatne) na \(8\) koní. Jedna posádka bude musieť sedieť na modrom koni, druhá na čiernom a tretia na jednom zo zvyšných (budeme ich zatiaľ brať ako jednu skupinu). Spočítajme možnosti tak, že budeme posádky postupne usádzať – prvá posádka má tri možnosti kde môže sedieť, druhá dve (lebo niekde už sedí prvá) a tretia si sadne tam kde ostalo miesto. To je \(3\cdot2\cdot1=6\) možností. Už nám ostáva vyriešiť len jednu vec, a to kam si sadne posádka ktorá bude sedieť na jednom zo zvyšných koní (nemodrom a nečiernom). To je ale jednoduché, zvyšných koní je \(6\), má preto \(6\) možností. Dajme to teda dokopy: je \(\binom 4 2\) možností ako vznikne dvojica, \(6\) možností ako sa rozsadia tri posádky a \(6\) možností ako si sadne jedna z posádok na jedného zo zvyšných koní. V tejto skupine je teda \(6\cdot6\cdot6=216\) možností.

Ostáva nám už len posledná skupina – tie možnosti pri ktorých išli všetci samostatne. Najprv obsadíme modrého koňa. Na to máme štyroch možných rytierov, takže \(4\) možnosti. Na čierneho koňa máme \(3\) možnosti, lebo jeden rytier už sedí na čiernom koni. Dvaja rytieri sedia, teraz zmeníme uhol pohľadu a na situáciu sa pozrieme očami tretieho rytiera: potrebuje si sadnúť na koňa, ostáva mu \(6\) možností. Nakoniec ostáva posledný rytier a vyberá si z piatich koní. Dokopy je teda v tejto skupine \(4\cdot3\cdot6\cdot5=360\) možností.

Keďže všetky tri skupiny dokopy obsahujú všetky možnosti, všetkých možností ako mohli rytieri prísť do mesta je \(6+216+360=582\).

  1. Ak vám pojem kombinačné číslo nič nehovorí, krátke vysvetlenie je napríklad tu https://cs.wikipedia.org/wiki/Kombina%C4%8Dn%C3%AD_%C4%8D%C3%ADslo↩︎

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ť.