Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:Booyabazooka

Kombinatorické myšlení

Kombinatorika trochu jinak

Postupné výběry

diskuze, ke stažení v PDF: zadání

Úloha č. 1

Ve fotbalové Lize mistrů se ve skupině potkávají tradičně $4$ týmy. V roce $2013$ se ve skupině D potkaly tyto týmy:

(a) Kolika způsoby mohla skupina skončit, když ji vyhrál Bayern Mnichov?
(b) Kolika způsoby mohla skupina skončit, když ji vyhrál Manchester City?
(c) Kolika způsoby mohla skupina skončit?
(d) Kolika způsoby mohla skupina skončit, když Viktoria Plzeň se umístila třetí?
(e) Kolikrát více je všech pořadí než těch, ve kterých je Viktoria Plzeň před CSKA Moskva?

Výsledek: (skrýt)

(a) 6 způsobů, (b) 6 způsobů, (c) 24 způsobů, (d) 6 způsobů, (e) dvakrát více.

Výsledek

Řešení: (skrýt)

Zbývající $3$ týmy se mohly seřadit $3\cdot2=6$ způsoby. Postupujeme například tak, že na druhé místo ve skupině můžeme dát jeden ze $3$ týmů a na třetí místo jeden ze $2$ zbývajících týmů.
Úloha je v principu stejná jako předchozí, tedy opět $6$ způsoby.
Na prvním místě bude jeden ze $4$ týmů. Čtyřikrát tak řešíme úlohu v principu stejnou jako (a) nebo (b). To dává $4\cdot6=24$ způsobů. Můžeme počítat i přímo umísťováním na 1., 2., 3. a 4. pozici, což vede na výpočet $4\cdot3\cdot2\cdot1=24$ .
Umístění Viktorie Plzeň je pevné a ostatní týmy lze uspořádat opět $6$ způsoby. Kdybychom úlohu řešili postupným umísťováním, tak začneme na 3. pozici a poté obsazujeme 1., 2. a 4., což vede na výpočet $1\cdot3\cdot2\cdot1=6$ .
(e) Viktorii Plzeň (VP) a CSKA Moskva (CM) lze vzájemně uspořádat jen dvěma způsoby. Přitom každému „dobrému“ pořadí ve skupině (ve kterém je VP před CM) odpovídá právě jedno „špatné“ pořadí (ve kterém je CM před VP a pořadí ostatních týmů je nezměněno) – viz tabulka níže. „Dobrá“ pořadí proto tvoří přesně polovinu všech možných pořadí.

Řešení

Úloha č. 2

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Následující úloha se skládá z několika podúloh. Rozdělte podúlohy do několika skupin (může to být i jen jediná skupina) tak, že všechny podúlohy v jedné skupině mají stejný výsledek. Výsledek podúloh v rámci skupiny není nutné určit a není podstatný. Hledejte důvody pro svá rozhodnutí. Skrýt.

(a) Určete počet různých cest ze západního města do východního.

(b) V restauraci v rámci poledního menu nabízejí na výběr ze

$3$ polévek,

$4$ hlavních jídel a

$3$ dezertů. Host si objedná jednu polívku, jedno hlavní jídlo a na závěr jeden dezert. Kolika způsoby může své menu sestavit?

(d) Kolik úseček s různobarevnými konci lze dokreslit do obrázku?

(e) Do každého políčka tabulky

$3\times3$ napíšeme jedno z písmen

$A, B, C, D$ . Kolika způsoby lze takto tabulku vyplnit?

Výsledek: (skrýt)

Podúlohy (b), (d), (e) tvoří jednu skupinu. Podúloha (a) je sólo. Stejnětak i podúloha (c) je sólo.

Výsledek

Řešení: (skrýt)

Host si vybere nejdříve třeba jedno ze $4$ hlavních jídel. To je jako vybrat si jednu ze $4$ linek vedoucí z 1. do 2. města. Vybrat si ze $3$ polívek je jako vybrat si jednu ze $3$ linek vedoucí z 2. do 3. města. Nakonec výběr ze $3$ dezertů odpovídá výběru ze $3$ linek mezi 3. a 4. městem.
Celkově tedy jedné cestě jednoznačně přiřadíme jedno menu a totéž lze provést i naopak. Podúlohy tedy počítají totéž.
Vybrat si jedno ze $4$ hlavních jídel je jako vybrat si podlaží „čtyřpatrového“ kvádru. Výběr ze $3$ polívek je jako výběr jedné ze $3$ pozic „vlevo“, „uprostřed“, „vpravo“. Výběr ze $3$ dezertů odpovídá výběru ze $3$ pozic „vepředu“, „uprostřed“, „vzadu“.
Jednomu menu tak můžeme vzájemně jednoznačně přiřadit jednu krychličku, takže počet způsobů sestavení menu je stejný jako počet krychliček.
Kdyby tabulka měla jen jedno políčko, lze ji vyplnit $4$ způsoby. Kdyby měla $2$ políčka, lze ji vyplnit $4\cdot4$ způsoby. Kdyby měla dokonce $3$ políčka, lze ji vyplnit už $4\cdot4\cdot4$ způsoby, atd. Počet způsobů vyplnění tabulky s $9$ políčky je tedy mnohem větší než počet cest v podúloze (d).
(c) Úsečka má dva konce. Je tedy potřeba rozlišit tři případy podle barev konců:
1. bílý a černý konec
2. černý a šedý konec
3. šedý a bílý konec
Z této úvahy vidíme, že podúloha (c) je svou povahou odlišná od skupiny (b), (d), (e) i od podúlohy (a). Byl by víceméně zázrak, pokud by náhodou vyšla stejně. Můžeme pro jistotu ověřit, že počet úseček je $4\cdot3 + 3\cdot3 + 3\cdot4 = 33$ , zatímco počet cest v podúloze (d) je $4\cdot3\cdot3=36$ .

Řešení

Úloha č. 3

Na obrázku jsou výsledky běhu na 200 m mužů z Olympijských her v Londýně z roku 2012.

(a) Kolika způsoby se mohly obsadit stupně vítězů? (tj. dva závody považujeme za různé, pokud se liší alespoň na jedné medailové pozici)
(b) Kolika způsoby mohl závod skončit tak, aby pořadí vlajek bylo úplně stejné jako při skutečném závodě? (tj. )
(c) Jak by se změnila odpověď na otázku (b), pokud by Alex Quinonez běžel o sekundu rychleji?
(d) Kolika způsoby by mohl závod skončit tak, aby pořadí vlajek bylo ?
(e) Každé pořadí vlajek se objeví při několika různých pořadích závodníků. Při kolika?
Prozradíme, že celkem existuje $6720$ pořadí vlajek. Zjistěte z toho, kolik existuje různých pořadí závodníků. Umíte počet pořadí závodníků spočítat i přímo? (tj. bez využití čísla $6720$ )

Výsledek: (skrýt)

(a) $8\cdot 7 \cdot 6 = 336$ , (b) $6$ způsobů, (c) $6$ způsobů, (d) $6$ způsobů, (e) $6$ pořadí, (f) $6720\cdot 6$ nebo též přímo $8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 = 40320$ .

Výsledek

Řešení: (skrýt)

Na zlatou medaili máme na výběr z $8$ závodníků. Na stříbrnou medaili máme na výběr ze zbývajících $7$ závodníků a na bronzovou ze zbývajících $6$ . To dává $8\cdot7\cdot6=336$ možností.
Lze prohazovat jen jamajské běžce, což lze udělat $6$ způsoby.
(c) Nezměnila by se. Opět je možné prohazovat pouze jamajské běžce.
Opět je možné prohazovat pouze jamajské běžce, a to $6$ způsoby.
Při zachování pořadí vlajek je možné prohazovat jamajské běžce. Proto každému pořadí vlajek odpovídá právě $6$ pořadí závodníků.
Z části (e) vyplývá, že všech různých pořadí závodníků je $6720\cdot 6$ . Bylo by možné počet pořadí spočítat i „přímo“ podobně jako jsme spočítali část (a). Tentokrát ale rozdělíme nejen medaile ( $8\cdot7\cdot6$ způsoby), ale pokračujeme i přidělením „bramborové medaile“ jednomu z $5$ zbývajících závodníků, poté přidělením pátého místa, šestého atd. Dostáváme tak $8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 = 40320$ různých pořadí závodníků. Z těchto úvah vyplývá, jakým způsobem lze spočítat počet pořadí všech vlajek. Umíme totiž „přímo“ spočítat počet všech pořadí závodníků a umíme též určit poměr mezi počtem pořadí závodníků a počtem pořadí vlajek (v tomto případě je poměr $6$ ).

Řešení

Úloha č. 4

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Závodu se zúčastnilo $5$ sportovců. Kolika způsoby se můžou obsadit stupně vítězů?
Na obrázku je $5$ bodů. Kolik trojúhelníků s vrcholy v těchto bodech lze nakreslit?

(d) Kolika způsoby lze naplánovat letecký výlet do

$3$ měst? (V jednom městě začneme a do dalších dvou cestujeme.) Každá dvě města z těchto pěti jsou spojena obousměrnou leteckou linkou. Na obrázku jsou příklady tří takových výletů.

(e) Z čísel

$2, 3, 4, 5, 6$ vybereme tři různá a spočteme jejich součin. Kolik různých součinů takto můžeme získat?

Výsledek: (skrýt)

Podúlohy (a), (c), (d) tvoří skupinu. Podúloha (b) je sólo. Podúloha (e) je také sólo.

Výsledek

Řešení: (skrýt)

Program v prvním cyklu vybere jedno z $5$ lichých čísel ( $1, 3, 5, 7, 9$ ) na 1. pozici. To je jako jednomu z $5$ sportovců dát zlatou medaili. V druhém cyklu vybere program jiné liché číslo a to dá na 2. pozici. To ja jako jednomu ze $4$ zbývajících sportovců dát stříbrnou medaili. Podobně i ve třetím cyklu program vybere dosud nevybrané liché číslo, což je jako vybrat bronzového sportovce. Podúlohy počítají totéž.
Pokud bychom města označili čísly $1, 3, 5, 7, 9$ , můžeme výlet zapsat třemi různými čísly. První číslo odpovídá městu, ve kterém výlet začne. Druhé číslo odpovídá dalšímu navštívenému městu a poslední číslo značí město, kde výlet skončí. Podúlohy si proto navzájem odpovídají.
Zdůvodníme, že počet trojúhelníků je menší než počet výletů z podúlohy (d). Body mohou zastupovat města. Každý trojúhelník spojuje tři různá města. Uvažujme například trojúhelník spojující obě jižní města a nejvýchodnější město. Mezi těmito městy lze ale naplánovat více výletů, například ty dva, které jsou nakresleny v podúloze (d) čárkovaně a tečkovaně. Lze si rozmyslet, že v rámci jednoho trojúhelníku lze naplánovat vždy $6$ výletů, takže počet trojúhelníků je $6$ -krát menší než počet výletů.
Zdůvodníme, že počet součinů je ještě menší než počet trojúhelníků z části (b). Bodům by bylo možné přiřadit čísla $2, 3, 4, 5, 6$ . Trojúhelník spojuje tři čísla, která můžeme vynásobit (narozdíl od výletů zde nezáleží na pořadí). Takto můžeme dostat součin kterýchkoliv tří různých čísel, takže trojúhelníků je aspoň tolik jako součinů. Problém ale je, že například trojúhelník spojující čísla $2,5,6$ dá stejný součin jako trojúhelník spojující čísla $3,4,5$ . Součinů je tedy méně.

Řešení

Úloha č. 5

Na obrázku jsou výsledky závodu v rychlobruslení na 1000 m žen z Olympijských her v Soči z roku 2014.

(a) Kolika způsoby mohl závod skončit tak, aby nedošlo ke změnám na medailových pozicích?
(b) Při kolika různých pořadích závodnic by bylo stejné pořadí vlajek jako při skutečném závodě?
(c) Každé pořadí vlajek se objeví při několika různých pořadích závodnic. Při kolika?
(d) Zjistěte počet všech možných pořadí závodnic a počet pořadí vlajek.

Výsledek: (skrýt)

(a) $24$ , (b) $24$ , (c) $24$ , (c) $24$ , (d) počet pořadí závodnic je $5040$ a počet pořadí vlajek $5040/24 = 210$ .

Výsledek

Řešení: (skrýt)

Medailové pozice jsou tedy pevně rozdělené. Zbývají $4$ závodnice, které mohly skončit na 4. pozici. Na 5. pozici máme na výběr ze $3$ zbývajících závodnic, na 6. pozici ze $2$ a 7. pozice zbyde pro poslední závodnici. To dává $4\cdot3\cdot2=24$ možností.
Pořadí si mohou měnit jen Holanďanky. Na 2. místo máme na výběr jednu ze $4$ Holanďanek, na 3. místo jednu ze $3$ zbývajících Holanďanek a na 5. místo jednu ze zbývajících $2$ . To dává $4\cdot3\cdot2=24$ různých pořadí závodnic, pro které je pořadí vlajek jako při skutečném závodě.
Sice bychom Holanďankám nepřiřazovali 2., 3., 5. a 6. pozici jako v části (b), ale v principu jde o stejnou úlohu. Tedy opět $24$ různých pořadí.
Jak jsme zjistili v částech (b) a (c), jednomu pořadí vlajek odpovídá $24$ pořadí závodnic. To platí pro každé pořadí vlajek. Všech pořadí závodnic je tedy $24$ -krát více než všech pořadí vlajek. Přitom počet pořadí závodnic je $7\cdot$ 65421

Řešení

Úloha č. 6

Všech dvanáct linek z plánu je třeba rozdělit mezi letecké společnosti tak, aby každá ze společností mohla dopravit cestující ze západního města do východního. Kolika způsoby to lze provést, jestliže:

(a) rozdělujeme mezi čtyři letecké společnosti?
(b) rozdělujeme mezi tři letecké společnosti?
(c) rozdělujeme mezi dvě letecké společnosti?

Výsledek: (skrýt)

$24\cdot24\cdot=13\,824$
$12\cdot12\cdot12=1\,728$
$14\cdot14\cdot14=2\,744$

Výsledek

Řešení: (skrýt)

Každá společnost musí dostat právě jednu linku mezi sousedními městy, aby mohla dopravit cestující ze západního města až do východního. Mezi dvěma sousedními městy lze linky rozdělit $4\cdot3\cdot2=24$ způsoby (1. společnost má na výběr ze $4$ linek, 2. společnost ze $3$ zbývajících linek a 3. společnost ze $2$ linek). Celkový počet způsobů je tedy $24\cdot24\cdot24=13\,824$ (linky mezi první dvojicí měst umíme rozdělit $24$ způsoby, stejnětak linky mezi druhou dvojicí měst i mezi třetí dvojicí měst).
Mohli bychom úlohu řešit například i tak, že nejdříve si 1. společnost vybere svoji cestu ze západu na východ. To může udělat $4\cdot4\cdot4$ způsoby. Potom si 2. společnost vybírá ze zbývajících linek svou cestu, což může udělat $3\cdot3\cdot3$ způsoby. Podobně 3. společnost si může vybrat $2\cdot2\cdot2$ způsoby a jedna cesta zbyde na 4. společnost. Celkem dostáváme $4\cdot4\cdot4\cdot3\cdot3\cdot3\cdot2\cdot2\cdot2=13\,824$ způsobů, jak linky rozdělit.
Chvíli se budeme zabývat situací jen mezi dvěma sousedními městy. Jedna letecká společnost získá $2$ linky. Ty si může vybrat $6$ způsoby (kdybychom linky označili A, B, C, D, tak si může vybrat AB, AC, AD, BC, BD, nebo CD). Zbývající $2$ nerozdělené linky si mohou dvě další společnosti rozdělit jen $2$ způsoby. Takže linky mezi sousedními městy lze rozdělit $6\cdot2=12$ způsoby. Celkem tak dostaneme $12\cdot12\cdot12=1\,728$ možností, jak linky rozdělit.
Opět se nejdříve zaměříme na situaci mezi dvěma sousedními městy. Pokud každou ze $4$ linek obarvíme jednou ze $2$ barev (které odpovídají společnostem), dostaneme i nějaká nepřípustná obarvení (která jedné ze společností neumožňují přepravovat cestující). Nicméně počet všech obarvení se snadno spočítá, protože je roven $2\cdot2\cdot2\cdot2=16$ . Nepřípustná obarvení jsou pouze $2$ – jsou to ta jednobarevná, která přiřadila všechny linky jedné společnosti. Počet přípustných obarvení je proto $16-2=14$ . Nakonec zase spočteme počet všech způsobů jako $14\cdot14\cdot14=2\,744$ .

Řešení

Shrnutí: (Postupný výběr) (tedy například vybíráme zlatého, stříbrného a bronzového medailistu). V takových případech máme na výběr $\underbrace{n\cdot (n-1)\cdots (n-k+1)}_{k\, \text{čísel}}$ možností.

Hodiny

Bonusy

Postupné výběry

Úloha č. 1

Úloha č. 2

Úloha č. 3

Úloha č. 4

Úloha č. 5

Úloha č. 6