Kombinatorika od nuly

Pátek 23. 10. · 10:55
Asi 40 minut na telefonu
Pravidla, variace, permutace

Jak na to

1Jdi shora dolů. Každý krok má jednu myšlenku, řešený příklad z hodin a kvíz. Čísla jsou malá, počítáš z hlavy.
2Když netrefíš, přečti si vysvětlení pod otázkou a jeď dál. Chyba tady je levnější než zítra.
3Ráno, jestli bude čas: teorie na začátek písemky a písemka nanečisto.

1Všechno jsou políčka

Kombinatorika se ptá pořád na totéž: kolika způsoby jde něco udělat? Možnosti nevypisuješ. Nakreslíš políčka, jedno za každé rozhodnutí, do každého napíšeš, kolik možností zbývá, a vynásobíš. V hodině jste kreslili podtržítka, je to totéž.

Řešený příklad z hodiny

Př. 8: Máme osm běžců ve finále na 100 m. Kolika způsoby je můžeme uspořádat na stupních vítězů?

Kolik je míst? Stupně vítězů jsou 3 políčka.
Na 1. místo může kdokoli: 8. Na 2. už jen ti, co nevyhráli: 7. Na 3.: 6.
Vynásobím.

72. místo·81. místo·63. místo=336

Proč násobím: ke každému z 8 vítězů je 7 možných druhých, to je 8 · 7 dvojic, a ke každé dvojici 6 třetích.

Druhý příklad z hodiny

Př. 2a: Z místa A do B vedou čtyři trasy, z B do C tři. Kolika způsoby lze vybrat trasu z A do C a zpět?

Čtyři úseky jsou čtyři políčka. Nic se nezakazuje, zpátky smím jít i stejnou trasou:

4A→B·3B→C·3C→B·4B→A=144

Př. 2b: Totéž, ale žádná ze sedmi cest nesmí být použita dvakrát. Zpátky mám vždy o jednu možnost míň:

4·3·2jinou·3jinou=72

Zkus políčka

Kolik políček, co do nich, vynásobit.

Máš 4 trička a 3 kraťasy. Kolik různých oblečení si můžeš vzít?
Pět běžců, rozdává se jen zlatá a stříbrná medaile. Kolika způsoby?
Kolik dvojjazyčných slovníků je potřeba, aby šlo překládat mezi angličtinou, francouzštinou, němčinou a ruštinou z každé do každé?
PIN má 4 číslice 0–9, mohou se opakovat. Kolik je PINů?
K obědu jsou 3 polévky, 4 hlavní jídla a 2 dezerty. Kolik je různých obědů (polévka, jídlo, dezert)?

2Násobit, nebo sčítat?

„A zároveň“ → krát

Rozhodnutí jdou po sobě: tričko a k němu kalhoty, trasa tam a pak zpět. To je pravidlo součinu.

„Nebo“ → plus

Možnosti se vylučují, nastane buď jedna, nebo druhá. To je pravidlo součtu. Uvnitř každé větve násobíš, větve sečteš.

Řešený příklad z hodiny

Př. 7: V košíku je 12 jablek a 10 hrušek. Petr si má vybrat buď jablko, anebo hrušku tak, aby Věra, která si po něm vybere jedno jablko a jednu hrušku, měla co největší možnost výběru. Co si má vybrat Petr?

Petr vezme jablko: zbude 11 jablek a 10 hrušek. Věra bere jablko a zároveň hrušku: 11 · 10 = 110.
Petr vezme hrušku: zbude 12 jablek a 9 hrušek: 12 · 9 = 108.
Petr si má vzít jablko.

Trik „aspoň jednou“: doplněk

„Aspoň“ se počítá špatně. Spočítej všechny možnosti − ty, kde to nenastane vůbec.

DÚ z hodiny: Na vrchol hory vedou čtyři cesty a lanovka. Kolika způsoby se dostanu nahoru a zpět tak, aby aspoň jednou byla použita lanovka?

Všechny: nahoru 5 možností a dolů 5: 5 · 5 = 25.
Bez lanovky, jen pěšky: 4 · 4 = 16.
Aspoň jednou lanovkou: 25 − 16 = 9.

A „lanovkou právě jednou“? Dvě větve: lanovkou nahoru a pěšky dolů, nebo naopak: 1 · 4 + 4 · 1 = 8.

Krát, nebo plus?

„A zároveň“ je krát, „nebo“ je plus.

Ve třídě je 17 dívek a 13 kluků. Kolika způsoby vyberete jednoho zástupce?
Vybíráte jednu dívku a jednoho chlapce, dívek je 12, chlapců 10. Kolik je dvojic?
Čtyři cesty a lanovka na vrchol. Nahoru a zpět tak, aby zpáteční cesta byla jiná než cesta nahoru?
Z A do B vedou 3 cesty, z B do C 2 cesty a z A do C jedna přímá. Kolika způsoby se dostanu z A do C?
Hodíš červenou a modrou kostkou. Kolik výsledků obsahuje aspoň jednu šestku?

3Podmínka jde první

Když má nějaké místo podmínku (číslo nesmí začínat nulou, poslední cifra určuje dělitelnost, modrá musí být uprostřed), vyplň to políčko jako první. Teprve pak ostatní.

Řešené příklady z hodiny

Př. 1: Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou.

9desítky: 1–9, ne 0·9jednotky: i 0, ale bez té první=81

Př. 4: Totéž, ale trojciferná.

9ne 0·9i 0, bez 1. cifry·8bez dvou použitých=648

Vlajky (př. 9)

Vlajka ze tří různobarevných vodorovných pruhů, barvy bílá, červená, modrá, zelená, žlutá.

a) Všechny vlajky: 5 · 4 · 3 = 60.
b) S modrým pruhem: modrá může být nahoře, uprostřed, nebo dole (3 možnosti), zbylé dva pruhy ze 4 barev: 3 · 4 · 3 = 36.
c) Modrý uprostřed: nejdřív políčko s podmínkou: 4 · 1 · 3 = 12.
d) Uprostřed není červený: doplněk, všechny − červený uprostřed: 60 − 12 = 48.

Dělitelnost, kterou budeš potřebovat

2: poslední cifra sudá · 5: poslední 0 nebo 5
4: poslední dvojčíslí dělitelné 4 · 25: končí 00, 25, 50, 75
3: ciferný součet dělitelný 3 · 6: dělitelné 2 i 3

Podmínka první

Nejdřív políčko s podmínkou, pak zbytek.

Kolik je všech trojciferných čísel? (Cifry se smí opakovat.)
Kolik trojciferných čísel z cifer 1, 2, 3, 4, 5 (bez opakování) je dělitelných pěti?
Vlajky z př. 9: kolik vlajek nemá modrý pruh vůbec?
Čtyřciferná čísla z cifer 1, 2, 3, 4, 5 (mohou se opakovat). Kolik jich je dělitelných dvěma?
Totéž, ale dělitelných pěti?

4Faktoriál a permutace

Permutace = seřadit všechny prvky. Políček je tolik, kolik je prvků, a čísla v nich klesají až k jedničce. Tomu součinu se říká faktoriál.

Faktoriál

n! = n · (n − 1) · … · 2 · 1

0! = 1	dohoda, v sešitu v rámečku
3! = 6	4! = 24
5! = 120	6! = 720

Krácení

Větší faktoriál rozepiš jen tak daleko, až narazíš na menší, a ten se pokrátí:

8!6! = 8 · 7 · 6!6! = 56

Řešený příklad z hodiny

Př. 17: V parlamentu chce vystoupit šest poslanců A, B, C, D, E, F. Určete počet všech možných pořadí jejich vystoupení.

6·5·4·3·2·1=720

Zapíšeš: P(6) = 6! = 720.

Faktoriál

Seřadit všechny = n!

V kolika pořadích můžeš sníst 3 různé bonbony?
Kolika způsoby lze seřadit 5 různých knih na polici?
Kolik přesmyček má slovo KRUH (i nesmyslných)?
Kolik je 7!5!?
Kolik je 0!?

5Variace V(k, n)

Variace = vybírám k prvků z n, záleží na pořadí a nic se neopakuje. Jsou to políčka, kterých je jen k: začneš na n a jdeš dolů.

V(k, n) = n · (n − 1) · … (k činitelů)

V(k, n) = n!(n − k)!

Ze sešitu: V(3, 8) = 8 · 7 · 6 = 336. To jsou přesně běžci z kroku 1.

Kdy to je variace: funkce (předseda, místopředseda), medaile, místa v pořadí, různé cifry, pruhy vlajky. Když se prvky smí opakovat (PIN), už to variace není, ale políčka fungují dál: v každém je pořád n.

Řešený příklad z hodiny

Př. 11: Výbor sportovního klubu tvoří šest mužů a čtyři ženy.

a) Kolika způsoby z nich lze vybrat předsedu, místopředsedu, jednatele a hospodáře?

Lidí je 10, funkce 4 a záleží, kdo má kterou: V(4, 10).
10 · 9 · 8 · 7 = 5040

b) Tak, aby ve funkci předsedy byl muž a ve funkci místopředsedy žena, nebo obráceně.

Předseda muž (6) a místopředseda žena (4), zbylých 8 lidí na dvě funkce: 6 · 4 · 8 · 7 = 1344.
Nebo obráceně: předsedkyně žena (4), místopředseda muž (6): 4 · 6 · 8 · 7 = 1344.
Větve se vylučují, sčítám: 1344 + 1344 = 2688.

Variace

k políček, začni na n.

Kolik je V(2, 5)?
Kolik je V(3, 10)?
Ze 20 členů se volí předseda a místopředseda. Kolika způsoby?
Rozvrh na jeden den má 6 hodin, předmětů je 12 a každý nejvýše jednou. Jak zapíšeš počet rozvrhů?

6Triky u pořadí

V hodinách (př. 17, 18 a DÚ s lavicí) se opakují čtyři situace. Každá má jeden trik.

„Ihned po sobě“ = blok

Slep je do jednoho prvku a pak řaď. A vystupuje ihned po E:

E ABCDF

5 prvků: 5! = 120. Když chtějí jen „vedle sebe“ v libovolném pořadí, ještě krát 2: 2 · 5! = 240.

„Někdy po“ = polovina

A vystupuje (kdykoli) po E. Ke každému pořadí, kde je A po E, existuje zrcadlové, kde je před. Proto přesně polovina:

6!2 = 360

Na kraji

Táborník A stojí na kraji: vyber kraj (2), ostatní seřaď:

2 · (n − 1)!

Pro 5 táborníků: 2 · 4! = 48.

Nestojí vedle sebe

Doplněk: všechna pořadí − ta, kde stojí vedle sebe (blok AB nebo BA):

n! − 2 · (n − 1)!

Pro 4 lidi: 24 − 2 · 6 = 12.

Triky

Blok, polovina, kraj, doplněk.

Šest poslanců. V kolika pořadích vystupuje A ihned po E?
Šest poslanců. V kolika pořadích vystupuje A (kdykoli) po E?
Šest hochů v šestimístné lavici, dva chtějí sedět vedle sebe. Kolika způsoby se posadí?
Pět táborníků do řady, A stojí na kraji. Kolika způsoby?
Čtyři lidé do řady, A a B nesmí stát vedle sebe. Kolika způsoby?

7Rovnice s variacemi

V hodině jste počítali př. 13 a 15. Postup je pořád stejný:

1Podmínka: n je přirozené a n ≥ k (z menšího počtu nevyberu víc).
2Rozepiš V(k, n) na k činitelů: V(2, n) = n(n − 1).
3Vyřeš. Co je na obou stranách, vykrať.
4Zkontroluj podmínku a záporné nebo neceločíselné kořeny zahoď.

Řešené příklady z hodiny

Př. 13a: Určete počet prvků, z nichž lze vytvořit 240 dvoučlenných variací.

V(2, n) = 240, podmínka n ≥ 2.
n(n − 1) = 240
n² − n − 240 = 0 → (n − 16)(n + 15) = 0
n = 16, kořen −15 nevyhovuje. Prvků je 16.

Rychlá kontrola: hledáš dvě sousední čísla, jejichž součin je 240. To je 16 · 15.

Př. 13b: Určete počet prvků, z nichž lze vytvořit dvakrát více čtyřčlenných variací než tříčlenných.

V(4, n) = 2 · V(3, n), podmínka n ≥ 4.
n(n − 1)(n − 2)(n − 3) = 2 · n(n − 1)(n − 2)
Vykrátím n(n − 1)(n − 2) (není nula): n − 3 = 2
n = 5. Prvků je 5.

Rovnice

Rozepiš a hledej sousední čísla.

Vyřeš V(2, n) = 56.
Vyřeš V(2, n) = 90.
Jaká je podmínka u V(3, n)?
Vyřeš V(3, n) = 3 · V(2, n).

Na jedničku

Delší příklady z hodiny. Projdi postup, až budeš mít čas.

Př. 15 Zvětší-li se počet prvků o dva, zvětší se počet tříčlenných variací desetkrát. Určete původní počet prvků.

V(3, n + 2) = 10 · V(3, n), podmínka n ≥ 3

(n + 2)(n + 1)n = 10 · n(n − 1)(n − 2)

Vykrátím n: (n + 2)(n + 1) = 10(n − 1)(n − 2)

n² + 3n + 2 = 10n² − 30n + 20

9n² − 33n + 18 = 0 → 3n² − 11n + 6 = 0

n = (11 ± 7) : 6, tedy 3 nebo 2/3 (nevyhovuje)

Původně 3 prvky. Kontrola: V(3, 5) = 60 = 10 · V(3, 3).

DÚ Zvětší-li se počet prvků o dva, zvětší se počet tříčlenných variací o 150. Určete původní počet prvků.

V(3, n + 2) − V(3, n) = 150, podmínka n ≥ 3

(n + 2)(n + 1)n − n(n − 1)(n − 2) = 150

Vytknu n: n[(n² + 3n + 2) − (n² − 3n + 2)] = 150

n · 6n = 150 → n² = 25

n = 5. Kontrola: 210 − 60 = 150.

Př. 14 Telefonní číslo je devítimístné, začíná dvojčíslím 23, neobsahuje žádné dvě stejné číslice a je dělitelné 25. Kolik telefonních čísel přichází v úvahu?

Dělitelné 25 = končí 00, 25, 50, 75. Dvě nuly nejdou (stejné cifry), 25 taky ne (dvojka už je na začátku). Zbývá 50 a 75.

Končí 50: použité 2, 3, 5, 0, zbývá 6 cifer na 5 prostředních míst: V(5, 6) = 6 · 5 · 4 · 3 · 2 = 720.

Končí 75: použité 2, 3, 7, 5, zase 6 cifer na 5 míst: 720.

720 + 720 = 1440

Př. 18 Kolika způsoby může n táborníků nastoupit a) do řady, b) do řady s A na kraji, c) do řady, kde A a B nestojí vedle sebe?

a) n!

b) 2 · (n − 1)!

c) n! − 2 · (n − 1)! = (n − 2) · (n − 1)!

8Teorie na začátek písemky

Pan Stolařík dává na začátek trochu teorie. Kdyby bylo „vyslov“ nebo „definuj“, napiš to takhle, jak to máte v sešitu:

Pravidlo součtu (nebo, disjunkce): Jsou-li A₁, …, A_n množiny, které mají po řadě p₁, …, p_n prvků, a každé dvě jsou disjunktní, pak A₁ ∪ … ∪ A_n má p₁ + … + p_n prvků.
Pravidlo součinu (a zároveň, konjunkce): Počet všech uspořádaných k-tic, jejichž 1. člen lze vybrat n₁ způsoby, 2. člen po výběru 1. členu n₂ způsoby, …, a poslední člen po výběru všech předchozích n_k způsoby, je roven n₁ · n₂ · … · n_k.
Variace: k-členná variace z n prvků je uspořádaná k-tice, ve které se každý z n prvků vyskytuje nejvýše jednou. Značí se V(k, n) a V(k, n) = n!(n − k)!.
Permutace z n prvků je každá n-členná variace z těchto prvků (uspořádaná n-tice, každý prvek právě jednou). P(n) = n!
Faktoriál: n! = n · (n − 1) · … · 2 · 1, 0! = 1, n ∈ ℕ₀.

9Jaký je to typ?

Před každým příkladem si polož dvě otázky:

Záleží na pořadí?Prohodím dva vybrané. Je to jiná možnost? (funkce, místa, cifry → ano)

ano

Používám všechny prvky?

ano

Permutacen!

ne, jen k

VariaceV(k, n)

Kombinaceaž po písemce

Když se úloha skládá z kroků různého druhu (polévka, pak jídlo…), cifry se smí opakovat, nebo má podmínku na jedno místo, prostě kresli políčka. Variace i permutace jsou jen jejich zkratka.

Poznej typ

Nepočítej, jen urči, co použiješ.

Kolika způsoby lze seřadit 7 různých knih na polici?
Kolika způsoby lze rozdat zlatou, stříbrnou a bronzovou medaili mezi 12 závodníků?
V jídelně jsou 3 polévky a 4 hlavní jídla. Kolik je různých obědů?
Kolik trojciferných čísel lze sestavit z cifer 1–9, když se nesmí opakovat?
Kolik je čtyřciferných čísel z cifer 1, 2, 3, 4, 5, když se cifry mohou opakovat?
Ze 20 členů klubu se volí předseda, místopředseda, pokladník a zapisovatel.

10Kde se nejčastěji ztrácí body

Nula na začátku. První cifra čísla má jen 9 možností (1–9).
Smí se opakovat? Přečti zadání dvakrát. Bez opakování čísla v políčkách klesají, s opakováním zůstávají.
„Ihned po“ není „po“. Ihned po = blok (5!), někdy po = polovina (6! : 2).
„Aspoň“ = všechny − žádné. Nepočítej větve ručně.
Rovnice: napiš podmínku n ≥ k a na konci ji zkontroluj.

11Písemka nanečisto

Deset příkladů napříč vším. Nejdřív si v hlavě nakresli políčka, pak klikni.

Generálka

Osm z deseti je dobrý výsledek.

Kolik je dvojciferných čísel, ve kterých se žádná cifra neopakuje?
Devět závodníků, rozdává se zlatá, stříbrná a bronzová medaile. Kolika způsoby?
Kolika způsoby se 5 lidí postaví do fronty?
Pět lidí do řady, Petr a Jana chtějí stát vedle sebe. Kolika způsoby?
Kolik trojciferných čísel z cifer 1, 2, 3, 4, 5 (bez opakování) je sudých?
Vyřeš V(2, n) = 30.
Zjednoduš 10!8!.
Zámek na kolo má 3 kolečka s číslicemi 0–9. Kolik je kombinací?
Na vrchol vedou 4 cesty a lanovka. Kolika způsoby nahoru a zpět, aby aspoň jednou byla použita lanovka?
Šest poslanců. V kolika pořadích vystupuje B (kdykoli) před C?