Součet a součin II

Úloha č. 1

Turnaje se účastní Brazílie, Česko, Čína, Německo a Švédsko, hraje se systémem každý s každým. Na závěr první dva týmy sehrají finálový zápas.

Kolik je možných finálových dvojic (vítěz, poražený finalista), ve kterých je

1. (a) vítězem Česko?
2. (b) vítězem Německo?
3. (c) vítězem libovolný tým a poraženým finalistou libovolný jiný tým?
4. (d) Čína poraženým finalistou?

Úloha č. 2

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

Úloha č. 3

Určete počet cest ze západního města do východního, v nichž

1. (a) jsou použité linky stejného typu.
2. (b) se typy linek střídají.
3. (c) je přesně jedna linka čárkovaně.

Úloha č. 4

Pro každé město určete, kolika způsoby se do něj lze dopravit ze severního města. Čísla vepisujte do kroužků.

Řešení: (skrýt)

V obou částech určíme postupně počet cest vedoucích do každého města podobně jako na předchozí hodině. Všimněte si, že v druhé části můžeme využít čísla z části první a ušetřit tak práci. Také je zajímavé, že v obou částech vyšly mocniny dvou. Je to náhoda?

Úloha č. 5

Čísla v kroužcích značí, kolika různými způsoby se do daného města lze dostat z toho nejzápadnějšího. Doplňte linky tak, že každá z nich směřuje ze západu na východ a protíná přesně jednu přerušovanou čáru.

Řešení: (skrýt)

Možných řešení je více, například ta na obrázku.

Úloha č. 6

Určete počet cest ze západního města do východního. Čísla v kroužcích mají význam z předchozí úlohy.

Úloha č. 7

Turnaje se účastní Brazílie, Česko, Čína, Německo a Švédsko. Kolik je možných medailových trojic, ve kterých je

1. (a) vítězem Švédsko?
2. (b) vítězem Čína?
3. (c) vítězem libovolný tým, stříbrným medailistou libovolný jiný tým a bronzovým medailistou kterýkoliv ze zbývajících týmů?
4. (d) Brazílie bronzovým medailistou?
5. (e) Česko stříbrným medailistou?

Úloha č. 8

1. (a) Rozhodněte, kterou z linek vyznačených přerušovanou šipkou máme zrušit, aby se počet cest ze západu na východ snížil méně.
2. (b) Pro každé z měst určete, kolik do něj vede různých cest z města nejzápadnějšího (bez rušení jediné linky).
3. (c) Pokud jste počítali správně, vyšla vám v prostředním řádku tři prvočísla. Rozhodněte, zda by vycházela prvočísla i dále, pokud bychom soustavu linek prodloužili ve stejném duchu.

Řešení: (skrýt)

1. (a) První řešení: Města označíme jako na obrázku. Zrušením vodorovné linky přijdeme o všechny cesty z A do E, které začínají tahem do B. Ztratíme tedy přesně tolik linek, kolik je cest z B do E.
   

Podobně v případě zrušení druhé linky ztratíme přesně tolik cest, kolik je cest z C do E. Ty ale můžeme podle druhého tahu dále rozdělit na cesty přes B či D. Celkový počet cest, které tedy ztratíme je roven součtu počtů cest z B do E a z D do E. To je jistě více než v prvním případě, takže počet cest se sníží méně zrušíme-li vodorovnou linku.

Druhé řešení: Pro obě varianty počet cest z východu na západ prostě určíme. Budeme přitom postupovat jako na minulé hodině postupným určování počtu cest vedoucích do jednotlivých cest. Při zrušení vodorovné linky zbude 30 cest a v druhém případě jich zbude 26. Počet tedy klesne méně v prvním případě.

(b) Postupujeme jako v minulé hodině a postupně tak určíme všechny výsledky.

(c) Nenecháme se unést výskytem tří prvočísel a dopočítáme následující člen v řadě. Vyjde nám 153, což je dělitelné třemi, takže navrhovaná hypotéza neplatí.

Pokud jste zvídaví, můžete se zamyslet nad další hypotézou: členy dělitelné třemi se v takto definované posloupnosti vyskytují pravidelně ob dva členy (neboli počínaje trojkou je každý třetí je dělitelný třemi).

Shrnutí: V mnoha úlohách se počty možností násobí a sčítají. Například pokud z města $A$ do $B$ vede 7 linek a z města $B$ do $C$ vede 5 linek, tak z města $A$ do $C$ vede $7\cdot5$ cest. Když ještě z $C$ do $D$ vede 9 linek, tak z $A$ do $D$ vede celkem $7\cdot5\cdot9$ cest.

Násobení se děje, kdykoliv můžeme prvky z jedné skupiny bez omezení kombinovat s prvky z druhé skupiny.

Matematicky se tato skutečnost vyjadřuje pomocí množin a uspořádaných dvojic. Řekněme, že množina $A$ má $a$ prvků a množina $B$ má $b$ prvků. Počet uspořádaných dvojic, v nichž na prvním místě je prvek z množiny $A$ a na druhém místě prvek z množiny $B$, je $a\cdot b$. Právě jsme popsali kombinatorické pravidlo součinu.

Obecně: Mějme ne dvě, ale rovnou $k$ množin $M_1, M_2, \dots, M_k$. Počty jejich prvků označme $m_1, m_2, \dots, m_k$. Uvažujme uspořádané $k$-tice, v nichž na prvním místě je prvek z množiny $M_1$, na druhém místě prvek z množiny $M_2$, atd. až na $k$-tém místě je prvek z množiny $M_k$. Počet těchto uspořádaných $k$-tic je $m_1\cdot m_2\cdot\ldots\cdot m_k$.

Předpokládejme, že nějakou skupinu lze rozdělit na 2 zcela nezávislé menší skupiny. Počty prvků menších skupin dají dohromady přirozeně počet prvků původní skupiny. Například v úloze 6 vede do východního města $24\cdot2$ „horních“ cest a 36 „dolních“ cest. To dává $24\cdot2 + 36$ cest. Podobně v úloze 3 (c) jsme cesty rozdělili dokonce do tří skupin - skupina cest začínajících čárkovanou linkou, skupina cest s prostřední čárkovanou linkou a skupina cest končících čárkovanou linkou.

V matematice situaci popíšeme opět pomocí množin. Dvě menší skupiny reprezentujeme pomocí množin $A$ a $B$, jejichž počty prvků jsou $a$ a $b$. To, že jsou „nezávislé“, znamená, že neobsahují žádné společné prvky, tj. $A \cap B = \emptyset$ (takovým množinám říkáme „disjunktní“). Tyto množiny vytváří dohromady množinu $A \cup B$, jejíž počet prvků je $a+b$. Tomuto říkáme kombinatorické pravidlo součtu.

Obecně: Mějme množinu, kterou lze rozdělit na $k$ disjuktních podmnožin $M_1, M_2, \dots, M_k$, jejichž počet prvků je $m_1, m_2, \dots, m_k$. Uvažujeme tedy množinu $M_1\cup M_2\cup\dots\cup M_k$, kde pro libovolné indexy $i$, $j$ platí $M_i \cap M_j = \emptyset$. Počet prvků množiny $M_1\cup M_2\cup\dots\cup M_k$ je $m_1+ m_2+\dots+m_k$.