Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:BooyabazookaKombinatorické myšlení

Kombinatorika trochu jinak

Kombinace I

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

Úloha č. 1

Kus mapy mezi městy opět chybí. Zvládnete si poradit i tentokrát?

  1. (a) Každou cestu z města A do B lze několika způsoby prodloužit na cestu z A do C. Kolika?
  2. (b) Prozradíme, že z města A do města C se dá dostat 42000 způsoby. Kolika způsoby se lze dostat z města A do města B?

Výsledek: (skrýt)
  1. (a) 14
  2. (b) 3\,000
Výsledek
Řešení: (skrýt)

Prodloužení cest je přesně tolik, kolik je cest z B do C. Ty rozdělíme na „vrchní“, „prostřední“ a „spodní“ a spočítáme jako 4+2+8 = 14.

Výsledek části (a) říká, že počet cest z A do C (42000) je čtrnáctinásobkem počtu cest z A do B, těch jsou pak 3000.

Řešení

Úloha č. 2

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

  1. (a) Kolika způsoby mohl závod skončit? (Dva závody považujeme za různé, pokud se liší alespoň na jedné pozici.)
  2. (b) Ke každému pořadí vlajek (např. ) lze dopsat několik pořadí jmen závodníků. Kolik?
  3. (c) Zjistěte, kolik je všech pořadí vlajek.
Výsledek: (skrýt)

(a): 8! = 8 \cdot 7 \cdots 2 \cdot 1 = 40320, (b): 3! = 3 \cdot 2 \cdot 1 = 6, (c): 8!/3! = 6720

Výsledek
Řešení: (skrýt)
  1. (a) Určujeme počet pořadí 8 závodníků. To lze buď postupným vybíráním na první, druhou atd. pozici, tedy jako 8 \cdot 7 \cdots 2 \cdot 1, anebo si vzpomeneme, že jsme se přesně touto situací zabývali na minulé hodině, a víme tak, že výsledek je 8!.

  2. (b) K vlajkám, které se vyskytují jen jednou, doplníme závodníky jednoznačně. Pak zbudou tři americké vlajky. Počet způsobů, kterak nim lze přiřadit americké závodníky spočteme opět buď postupným výběrem, anebo rovnou jako 3! = 6.

  3. (c) V části (b) jsme si rozmysleli, že každé pořadí vlajek lze doplnit na pořadí závodníků šesti způsoby, přičemž každé pořadí závodníků takto získáme přesně jednou. Platí tak, že pořadí závodníků (8!)je přesně šestkrát více než pořadí vlajek. Pořadí vlajek je tak 8!/3! = 6720.

Řešení

Úloha č. 3

Sprinterského závodu se účastní 8 závodníků a 3 nejlepší postupují na mistrovství světa.

  1. (a) Kolika způsoby může závod dopadnout na prvních třech místech? (Dva závody dopadly různě, pokud se liší alespoň na první, druhé nebo třetí pozici.)
  2. (b) Na mistrovství světa nehrají předchozí výsledky roli, takže důležité je pouze složení postupující trojice (bez ohledu na jejich vzájemné umístění). Kolikrát jsme v části (a) započítali tutéž postupující trojici?
  3. (c) Kolik postupujících trojic lze „namíchat“ z 8 závodníků? (Opět je důležité pouze složení postupující trojice.)

Výsledek: (skrýt)

(a): 8\cdot 7 \cdot 6 = 336, (b): 6, (c): 8\cdot 7 \cdot 6 / 6 = 56

Výsledek
Řešení: (skrýt)
  1. (a): Postupným výběrem na první, druhou a třetí pozici určíme výsledek jako 8\cdot 7 \cdot 6 = 336.
  2. (b): Jednu a tu samou trojici jsme započítali právě jednou za každé její možné pořadí. Počet těchto pořadí určíme výpisem (ABC, ACB, BAC, BCA, CAB, CBA), nebo opět postupným výběrem jako 3 \cdot 2 \cdot 1, nebo rovnou jako 3!.

  3. (c): Z části (b) víme, že každou trojici jsme v části (a) započetli šestkrát. Odpověď z části (a) (336) je tak šestkrát větší než ta, kterou hledáme nyní. Tou je tak 56.
Řešení

Úloha č. 4

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

  1. (a) V plaveckém finále závodí 8 plavců. Kolika způsoby může závod skončit na medailových pozicích? (Tj. dva závody považujeme za různé, pokud se liší alespoň na jedné medailové pozici.)
  2. (b) Na obrázku je 8 bodů. Kolik trojúhelníků s vrcholy v těchto bodech lze nakreslit?

  • (c) Trenér má k dispozici 8 náhradníků a zvažuje, kterou trojici z nich pošle do zítřejšího zápasu. Z kolika možností má na výběr?
  • (d) Kolika výstupy může skončit následující program? (Např. výstupy 168 a 186 považujeme za různé.)

    Výsledek: (skrýt)

    (a) = (d), (b) = (c)

    Výsledek
    Řešení: (skrýt)
    1. (a) \Leftrightarrow (d) Plavcům rozdáme čísla 1 až 8. První výběr v programu bude odpovídat výběru zlatého plavce, druhý stříbrného a třetí bronzového.

    2. (b) \Leftrightarrow (c) Vybranou trojici bodů ztotožníme s vybranou trojicí náhradníků. Možností je méně než v částech (a) a (d), jelikož v ani jednom případě nezapočítáváme trojice znovu za každé jejich pořadí.

    Řešení

    • Úloha č. 5

    Na turnaji hraje 6 týmů ve skupině A a dalších 6 týmů ve skupině B. Po bojích ve skupině vytvoří 2 nejlepší týmy z každé skupiny čtyřčlennou finálovou skupinu a boje v ní začnou nanovo. Kolik různých čtveřic se může ve finálové skupině potkat?

    Výsledek: (skrýt)

    (6 \cdot 5 /2)^2 = 225

    Výsledek
    Řešení: (skrýt)

    Určeme nejprve, kolika způsoby lze vybrat postupující dvojici ze skupiny A. Prvního postupujícího vybereme šesti způsoby a následně druhého pěti. Jenomže takto jsme postupující dvojici \{A, B\} započetli dvakrát. Jednou v pořadí (A,B) a jednou v pořadí (B, A). Výsledek vydělíme dvěma a vyjde 15.

    Stejně určíme počet možných postupujících dvojic ze skupiny B. Zbývá si uvědomit, že kterákoliv pevná postupující dvojice ze skupiny A může narazit na kteroukoliv z 15 možných dvojic ze skupiny B. Výsledek je tak 15 \cdot 15 = 225.

    Řešení

    Úloha č. 6

    Šachového turnaje se zúčastnilo 8 hráčů a každý s každým odehrál jednu partii. Za vítězství získal hráč 1 bod, za remízu půl bodu, za prohru žádný bod. Na konci turnaje měli všichni účastníci různé počty bodů. Hráč, který skončil na 2. místě, získal stejný počet bodů jako poslední čtyři dohromady. Určete výsledek partie mezi 4. a 6. hráčem v celkovém pořadí.

    Návodné úlohy:

    1. (a) Kolik utkání sehrají 4 hráči, když každý s každým sehraje jeden zápas?
    2. (b) Kolik bodů se rozdělí mezi 4 hráče, když každý s každým sehraje jeden zápas?
    3. (c) Kolik nejméně bodů získali hráči na 5. až 8. místě dohromady?
    4. (d) Kolik nejvýše bodů může v turnaji 8 hráčů získat ten, který skončí na druhém místě?

    Výsledek: (skrýt)

    Čtvrtý vyhrál.

    Výsledek
    Řešení: (skrýt)
    1. (a) Na prvního účastníka zápasu jsou čtyři možnosti, na druhého tři, přičemž takto každou dvojici hráčů započítáváme dvakrát. Výsledek je tak 4 \cdot 3 / 2 = 6.
    2. (b) V každém zápase se dohromady rozdělí jeden bod. Mezi čtveřici hráčů se tak rozdělí šest bodů.
    3. (c) Hráčí na pátém až osmém místě ziskali body minimálně ve vzájemných zápasech. Těchto bodů je podle části (b) šest.
    4. (d) Ukážeme, že druhý hráč v pořadí mohl získat nejvýše 6 bodů. Tolik bodů mohl získat například tak, že porazil všechny kromě absolutního vítěze, který získal plný počet bodů.

      Více než šest je ovšem na druhého hráče příliš mnoho. V úvahu připadá pouze 7 a 6.5, přičemž 7 by zjevně vedlo k absolutnímu vítězství v turnaji a nikoliv ke druhé místu.

      V případě zisku 6.5 bodu užijeme podmínku, že žádní dva hráči nezískali stejně bodů. Absolutní vítěz tak musel získat více než 6.5 bodu tedy 7. To je ale nesmysl, protože pak by vítěz všechny porazil a přitom druhý s nikým neprohrál.

    Z částí (c) a (d), že druhý hráč získal přesně 6 bodů, což je i součet bodů udělených hráčům na 5. až 8. místě. Podle části (c) ale tito hráči uhrají v součtu 6 bodů jedině tehdy, pokud všichni prohrají své zápasy s hráči z první čtyřky.

    Nyní je jasné, že šestý se čtvrtým prohrál.

    Řešení

    Shrnutí: V mnoha úlohách řešíme problém podobný tomuto: Potřebujeme spočítat počet způsobů, kterými lze ze skupiny 8 lidí vybrat 3 reprezentanty (obecněji ze skupiny 8 objektů vybíráme 3, přičemž nezáleží na pořadí, ve kterém k výběru dochází).

    Takovou úlohu není lehké řešit úplně přímo. Nejdříve řešíme jednodušší úlohu: Kolika způsoby lze mezi 8 lidí rozdělit zlatou, stříbrnou a bronzovou medaili? Vybrat „zlatého“ reprezentanta, „stříbrného“ reprezentanta a „bronzového“ reprezentanta lze 8\cdot7\cdot6 způsoby.

    Poté přichází klíčová otázka: Každou pevně zvolenou trojici reprezentantů jsme v předchozí úloze započítali víckrát. Kolikrát? Protože mezi skupinu 3 reprezentantů lze medaile rozdělit 3\cdot2\cdot1\ (=6) způsoby, započítali jsme každou trojici reprezentantů šestkrát. (Například z lidí \{A, B, C, D, E, F, G, H\} jsme trojici \{B, D, H\} (bez pořadí) započítali při udělování medailí jako (B,D,H), (B,H,D), (D,B,H), (D,H,B), (H,B,D) i (H,D,B)). To znamená, že neuspořádaných trojic je 6krát méně než uspořádaných trojic.

    Odpovědí na původní otázku Kolika způsoby lze z 8 lidí vybrat 3 reprezentanty? je tedy Tomuto číslu se říká kombinační číslo „osm nad třemi“. Používá se symbol {8\choose3}.

    Počet způsobů, kterými lze ze skupiny n lidí vybrat k reprezentantů, označujeme symbolem což čteme jako „$n$ nad $k$“.