Domácí úkol z kombinatoriky, 14. října 2024
Přestože tento domácí úkol nebudete odevzdávat, měli byste si jej ve vlastním zájmu sepsat. Nezapomeňte vždy zapsat i úvahu, kterou jste k výsledku došli, a to způsobem, kterým byste svůj postup vysvětlili spolužákovi.
Vzorové řešení zadaných úloh bude uveřejněno v interaktivní osnově v pátek 18. října 2024, abyste si svůj domácí úkol mohli sami opravit.
1. Kolika způsoby lze vybrat z karetní hry (mající po osmi kartách od každé ze čtyř barev) neuspořádanou hromádku osmi karet tak, aby byly vybrány karty právě dvou různých barev?
2. Tvoříme anagramy ze slova MISSISSIPPI.
(a) Kolik anagramů existuje?
(b) V kolika případech nejsou všechna čtyři písmena S těsně vedle sebe?
(c) V kolika případech nejsou ani všechna čtyři písmena S ani všechna čtyři písmena I těsně vedle sebe?
3. Máte k dispozici 5 druhů ovoce: jablka, banány, pomeranče, hrušky a švestky.
(a) Kolika způsoby si z těchto druhů ovoce lze vybrat 10 kusů (různé plody stejného druhu ovoce nelze rozlišit)?
(b) V kolika případech jsou mezi vybranými alespoň 2 banány a nejvýše 3 jablka a nejvýše 3 hrušky?
Řešení:
1. Pro volbu dvou barev, které vybrané karty mají mít, vybíráme dvouprvkovou podmnožinu ze čtyřprvkové množiny barev, je možné je tedy vybrat = 6 způsoby. Ze šestnáctiprvkové množiny karet těchto dvou barev vybíráme osmiprvkovou podmnožinu karet, což je možné provést (g6) = 12870 způsoby, přičemž však ve dvou případech bylo vybráno všech 8 karet jedné nebo druhé barvy. Proto tato šestnáctiprvková množina má osmiprvkových podmnožin, které obsahují alespoň jednu kartu od každé barvy, právě 12870 — 2 = 12868. Pro každou ze 6 možností, jak vybrat dvojici barev, máme 12868 možností, jak karty zvolit, podle pravidla součinu je hledaný počet 6 • 12868 = 77208.
2. (a) Ve slově MISSISSIPPI jsou čtyři písmena S, čtyři písmena I, dvě
písmena P a jedno písmeno M. Máme celkem 11 pozic pro písmena, z nichž čtyři pozice pro S lze volit (141) = 330 způsoby, pro každou takovou volbou máme Q) = 35 způsobů, jak volit polohu písmen I, pokaždé pak máme (^j = 3 možnosti, kam umístit písmena P, na poslední volné místo je možné jen jediným způsobem dát M. Podle pravidla součinu je hledaný počet anagramů 330 • 35 • 3 = 34650. (Také je možné využít vzorec pro počet pořadí s opakováním:
iSäí = 34650-)
(b) Množina všech anagramů je sjednocením dvou disjunktních podmnožin, z nichž první obsahuje ty anagramy, které mají všechna čtyři písmena S těsně vedle sebe, a ta druhá ty ostatní. Počet anagramů v té první můžeme určit tak, že všechna čtyři písmena S nahradíme jediným písmenem „čtyřnásobné S". Nyní máme 8 písmen, stejným postupem jako výše zjistíme, že počet těchto anagramů je (®) ' (2) ' ^ = irk = ^40. Podle pravidla součtu je hledaný počet anagramů, v nichž nejsou všechna čtyři písmena S těsně vedle sebe, roven 34650 — 840 = 33810.
(c) Počet anagramů, které mají všechna čtyři písmena I těsně vedle sebe, je stejný jako počet těch anagramů, které mají všechna čtyři písmena S těsně vedle sebe, tedy 840. Ovšem počet těch anagramů, které mají všechna čtyři písmena S těsně vedle sebe nebo všechna čtyři písmena I těsně vedle sebe, není dvakrát větší, protože některé anagramy splňují obě podmínky současně. Jejich počet zjistíme tak, že všechna čtyři písmena S nahradíme jediným písmenem „čtyřnásobné S" a také všechna čtyři písmena I nahradíme jediným písmenem „čtyřnásobné I". Pak máme pět písmen, přičemž jediným opakujícím se písmenem je písmeno P,
které máme dvakrát. Počet těchto anagramů spočítáme podobně jako výše, je roven ' 3! = §j = 60. Protože těchto 60 anagramů se objevuje mezi 840 anagramy majícími všechna čtyři písmena S vedle sebe i mezi 840 anagramy majícími všechna čtyři písmena I vedle sebe, je počet anagramů, které mají všechna čtyři písmena S těsně vedle sebe nebo všechna čtyři písmena I těsně vedle sebe, roven 840 -2 — 60 = 1620. Podle pravidla součtu je hledaný počet anagramů, v nichž nejsou všechna čtyři písmena S těsně vedle sebe ani všechna čtyři písmena I těsně vedle sebe, roven 34650 - 1620 = 33030.
3. (a) Zvolených 10 kusů ovoce si můžeme roztřídit podle jejich druhů do pěti přihrádek. Podle pravidla bijekce je způsobů takové volby právě tolik, kolik existuje slov o 14 písmenech, které jsou zapsány pomocí 10 písmen O a čtyř písmen I: každé takové slovo odpovídá volbě tolika plodů prvního druhu, kolik je napsaných O před prvním I, tolika plodů druhého druhu, kolik je napsaných O mezi prvním I a druhým I, atd. Protože takových slov je tolik, kolika způsoby lze vybrat ze 14 možných pozic čtyři pozice pro I, je hledaný počet (x44) = 1001.
(b) Protože máme vybrat alespoň dva banány, dáme si je stranou a budeme vybírat zbylých 8 kusů ovoce. Podobně jako v případě (a)
4) = 495. Mezi
těmito výběry ovoce však jsou i ty, kdy jsme vybrali alespoň 4 jablka nebo alespoň 4 hrušky, což odporuje zadaným podmínkám. Musíme tedy spočítat, kolik je takových výběrů. Nejprve si ke dvěma odloženým banánům odložíme i čtyři jablka, zbývající 4 kusy ovoce lze vybrat (®) = 70 způsoby. Stejný počet dostaneme, když ke dvěma odloženým banánům místo jablek odložíme čtyři hrušky. Ovšem volba dvou banánů, čtyř jablek a čtyř hrušek se objevila v obou případech. Proto je počet výběrů, kdy jsme kromě dvou banánů také vybrali alespoň čtyři jablka nebo alespoň čtyři hrušky, roven 70 • 2 — 1 = 139. Podle pravidla součtu je hledaný počet roven 495 — 139 = 356.