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
(a): 4, (b): 4, (c): 5\cdot4=20, (d): 4.
Výsledek: (a), (b), (d) dávají stejný výsledek a (c), (e) dávají stejný výsledek.
Určete počet cest ze západního města do východního, v nichž
V celém řešení budeme značit plné linky P a čárkované linky Č.
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ů.
Na levém obrázku se do nejjižnějšího města lze dopravit 8 způsoby. Na pravém obrázku se do nejjižnějšího města lze dopravit 16 způsoby.
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?
Čí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.
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.
24\cdot2 + 36 = 84
Město označené číslem 24 označme A a to s číslem 36 označme B. Cesty ze západu na východ rozdělíme na dvě skupiny podle toho, které z měst A, B je na cestě předposlední. Jelikož je cest do B přesně 36 a každá z nich lze jednoznačně rozšířit na cestu druhého typu, máme takových cest 36.
Podobně cest do A je 24 a každá z nich lze přesně dvěma způsoby prodloužit do západního města. Cest prvního typu je tak 48. Výsledek úlohy je tedy 36+48 = 84.
Turnaje se účastní Brazílie, Česko, Čína, Německo a Švédsko. Kolik je možných medailových trojic, ve kterých je
(a): 4\cdot3 = 12, (b): 4\cdot3 = 12, (c): 5\cdot4\cdot3 = 60, (d): 4\cdot3 = 12, (e): 4\cdot3 = 12.
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ě.
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.