KOMBINATORIKA – ŘEŠENÉ PŘÍKLADY Příklad 1 Pan Alois dostal od vedení NP Šumava za úkol vytvořit propagační poster se čtyřmi fotografiemi Šumavského národního parku, každou z jiného ročního období (viz obrázek). Po hodinách hledání a několika selekcích shromáždil Alois 12 fotografií z jara, 20 fotografií z léta, 8 fotografií z podzimu a 15 fotografií ze zimy. Kolika způsoby může pan Alois sestavit poster? Řešení: Dejme tomu, že pan Alois to vezme popořadě od jara do zimy. Pro výběr fotky z jara má Alois dvanáct možností. Tady není co počítat. Ke každé fotce z jara může Alois přidat na poster právě jednu fotku z léta. Těch má na výběr celkem dvacet, takže počet všech možností, jak může na poster umístit fotky z jara a léta je roven 12 20 240. Pro libovolnou kombinaci fotek z jara a léta (připomínám, že těch kombinací je 240) má Alois k dispozici 8 různých fotek z podzimu. Takže počet všech možností, jak vybrat do posteru fotky od jara do podzimu je roven 240 8 1920. Pevně věřím, že v této fázi úlohy už je všem badatelům z řad čtenářů jasné, že počet všech možností, jak sestavit poster podle obrázku výše, je roven 1920 15 28 800 .
V příkladu 1 jsme použili tzv. kombinatorické pravidlo součinu. Počet všech uspořádaných k–tic, jejichž první člen lze vybrat právě n1 způsoby, druhý člen po výběru prvního právě n2 způsoby, třetí člen po výběru předchozích dvou právě n3 způsoby atd., až k-tý člen po výběru (k – 1)–ho členu právě nk způsoby, je roven n1 n2 ... n k . Zpět k příkladu 1. Vybírali jsme čtveřice fotek, tj. k = 4. n1 = 12 (fotku z jara – 1. člen – lze vybrat dvanácti způsoby) n2 = 20 (fotku z léta – 2. člen – lze vybrat dvaceti způsoby) n3 = 8 (fotku z podzimu – 3. člen – lze vybrat osmi způsoby) n4 = 15 (fotku ze zimy – 4. člen – lze vybrat patnácti způsoby) Počet všech uspořádaných čtveřic = n1 n2 n3 n4 28 800. Pozn. V definici kombinatorického pravidla součinu stojí, že při výběru členu je třeba vždy zohlednit výběr členů předchozích. V příkladu 1 tomu tak nebylo, protože jsme brali pokaždé z jiné hromádky fotek. U dalšího příkladu již tomu tak bude.
Příklad 2 Ve třídě je 18 žáků. Na začátku hodiny si učitel hodlá postupně „proklepnout“ tři žáky ze znalostí předchozí látky. Kolika způsoby to může provést? Řešení: Učitel má osmnáct možností, jak provést výběr prvního žáka (členu) do trojice nešťastníků tj. n1 = 18. Proklepne ho a napaří mu bůra, páčto nic neuměl. Zkoušet jednoho žáka dvakrát po sobě, to se nedělá. Při výběru druhého nešťastníka musí učitel zohlednit předchozí výběr, takže má už jen sedmnáct možností, jak provést výběr druhého žáka ke zkoušení (tj. n2 = 17). Vybere ho, proklepne ho a napaří mu známku. Počet možností, jak vybrat posledního z trojice nešťastníků, se tím pochopitelně zúží na šestnáct (n3 = 16), jelikož dva žáci už to mají pro ten den za sebou. Celkem má tedy učitel 18 17 16 4896 možností, jak ten den vyzkoušet tři žáky. Pozn. Je třeba si uvědomit, že záleží na pořadí, ve kterém jdou žáci k tabuli. Kdyby totiž první žák na všechny otázky odpověděl správně, těžko bude učitel tytéž otázky klást i dalšímu žákovi v pořadí. Naopak, jelikož první žák nic nevěděl, je pravděpodobné, že tytéž otázky (nebo aspoň podobné) dostane i druhý zkoušený žák.
Variace k-té třídy z n prvků je každá uspořádaná k-tice sestavená pouze z těchto n prvků tak, že každý prvek je v ní obsažen nejvýše jednou. Značení: Vk (n) Počet variací k-té třídy z n prvků určíme jednoduše – číslo n násobíme číslem menším o jedna, pak číslem menším o dva, menším o tři atd. S násobením skončíme ve chvíli, až budeme mít v součinu celkem k činitelů. To je celé. Zpět k příkladu 2. Jak už bylo řečeno v poznámce výše, při zkoušení záleží na pořadí a žádný žák nemůže být během jedné hodiny zkoušen více než jednou. Hledáme-li počet všech možností, jak může učitel ten den „proklepnout“ tři žáky, určujeme vlastně počet variací třetí třídy z osmnácti prvků. n = 18 k=3
(ve třídě je 18 žáků (prvků), při násobení tedy začneme číslem 18) (učitel vybírá trojici, v součinu tudíž budou právě tři činitelé)
V3 18 18 17 16 4896
Příklad 3 Z kolika prvků lze vytvořit 287 430 variací třetí třídy? Řešení: Co se to po nás vlastně chce? Kdybychom na tento příklad „napasovali“ situaci z příkladu 2, tak bychom vlastně chtěli vědět, kolik by ve třídě muselo být žáků, aby měl učitel 287 430 možností, jak proklepnout trojici žáků. Asi by to byla hodně velká třída. Zpět k příkladu. Platí: V3 n n n 1 n 2 287 430 , kde n značí počet prvků. Rovnice n n 1 n 2 287 430 je rovnice třetího stupně, která je sice obecně řešitelná, ale je to abych tak řekl „jiná liga“. Půjdeme na to zdravým selským rozumem. Levá strana rovnice je součin tří po sobě jdoucích přirozených čísel seřazených sestupně. Takže když odmocníme číslo 287 430 třetí odmocninou, měli bychom se dostat zhruba k tomu prostřednímu číslu, ne? 3
287 430 65,99494911..
Z toho by jeden usoudil, že prostřední číslo bude rovno 66, že součin vypadá takto: 67 66 65 a že hledaný počet prvků je tudíž roven 67. Ověřte sami.
Permutace z n prvků je každá variace n-té třídy z těchto n prvků. Značení: P(n) Počet permutací z n prvků je dán vztahem: Pn Vn n n n 1 n 2 ... 3 2 1 (součin jednoduše rozepíšeme až do jedničky, neboť n = k)
Abychom se moc nenadřeli, budeme takový součin značit n! a číst „en faktoriál“. Tak například 4! = 4 3 2 1 , 6! = 6 5 4 3 2 1 atd. Ne vždy je nutné součin rozepisovat až do jedničky. Ukážeme si to na dalším příkladu. Příklad 4 Vypočítej
102 ! . 100 !
Řešení: Nejdříve se vysmějeme všem, co to nabouchali do kalkulačky a teď zírají na hlášku MATH ERROR. A teď zpátky k příkladu. Větší faktoriál si rozepíšeme, ovšem nikoli až do jedničky, z čehož by nás nejspíš omyli, ale jen po ten menší faktoriál.
102 ! 102 101 100 ! = 102 101 10 302 100 ! 100 !
Hotovo.
Pozn. Permutace znamená pořadí. Číslo 100! lze chápat jako počet všech možných pořadí, jaké může utvořit zástup sta lidí. To je obrovské číslo. Počet všech pořadí z 0 prvků 0! = 1.
Příklad 5 Kolika způsoby lze u ústní části maturity z anglického jazyka postupně vyzkoušet sedm maturantů, z nichž jeden měl na vysvědčení z anglického jazyka dvojku, dva měli trojku a zbytek čtyřku a) libovolně, b) nejdříve „dvojkaře“, pak „trojkaře“ a nakonec „čtyřkaře“? Každý maturant si tahá jednu otázku a každá otázka může být tažena pouze jednou. Řešení: a) Tady je to jednoduché. Zajímá nás počet všech možných pořadí sedmi studentů. Ten je roven 7! = 5040. b) Zkombinujeme permutace s pravidlem kombinatorického součinu. Označíme-li „dvojkaře“ číslem 2, „trojkaře“ číslem 3 a „čtyřkaře“ číslem 4, pak hledáme uspořádané sedmice ve tvaru 2334444. Pro pořadí „dvojkaře“ existuje 1! = 1 možnost. Vybereme ho a přejdeme k „trojkařům“. Pro pořadí „trojkařů“ existují 2! = 2 možnosti. Vybereme jednoho, pak druhého a přejdeme ke „čtyřkařům“. Pro pořadí „čtyřkařů“ existuje 4! = 24 možností. Celkem tedy existuje 1! 2! 4! 48 možných pořadí vyhovujících podmínkám b).
Příklad 6 Zvětší-li se počet prvků o dva, zvětší se počet permutací z těchto prvků utvořených a) 42krát, b) o 39 600. Řešení: Základem je správné označení. n n! n+2 (n + 2)!
původní počet prvků počet permutací z n prvků zvětšený počet prvků počet permutací z (n + 2) prvků
a) n 2! 42n ! n 2n 1n ! 42n ! n 2n 1 42
n 2 3n 40 0
Větší faktoriál rozepíšeme až na úroveň toho menšího. Vydělíme výrazem n! (který nemůže být nula, takže bez obav). Vyřešíme kvadratickou rovnici. D 169
D 13
n1 5
n 2 8
Platí pouze výsledek n = 5, jelikož stěží budeme určovat pořadí z mínus osmi prvků. Pozn. Tuto část příkladu šlo řešit mnohem efektivněji. Stačí si uvědomit, že číslo 42 = 7 6 . Z toho vyplývá, že n 2n 1n ! 7 6 n ! , takže n + 2 = 7 a současně n + 1 = 6. Těmto rovnostem vyhovuje pouze číslo 5.
b) n 2! 39 600 n ! Větší faktoriál rozepíšeme až na úroveň toho menšího. n 2n 1n ! 39 600 n! n 2n 1n!n! 39 600 n !n 2n 1 1 39 600 n ! n 2 3n 1 39 600
Faktoriálu na levé straně se žádnou klasickou úpravou rovnice nezbavíme. Pomůžeme si však jednoduchým fíglem: číslo 39 600 budeme postupně dělit dvěma, třemi, čtyřmi, pěti atd., až dostaneme číslo, které už nám při dalším dělení nevyjde beze zbytku. 39 600 = 2 19 800 2 3 6 600 2 3 4 1 650 2 3 4 5 330 2 3 4 5 6 55 To znamená, že 39 600 = 55 6! . A teď hybaj k rovnici.
n ! n 2 3n 1 6 !55 n = 6, závorka = 55 ZK: 6 2 3 6 1 55
