kombinatorika

Příklad 501

Určete počet všech sedmiciferných čísel, v jejichž dekadickem zápisu je každá z cifer $\{1, 2, 3, 4, 5, 6, 7\}$ a ve kterých je sedmička vpravo od pětky.

Řešení	Ukázat
Jedná se přesně o polovinu všech čísel, která můžeme z těchto cifer vytvořit, tj. $\frac12\cdot7!$

Příklad 502

Určete počet všech pěticiferných přirozených čísel dělitelných devíti, v jejichž dekadickem zápisu se vyskytují pouze cifry 2, 4, 6.

Řešení	Ukázat
Nejmenší vytvořitelné číslo 22222 má ciferný součet 10. Největší vytvořitelné číslo 666666 má ciferný součet 30. Aby bylo číslo dělitelné devíti, musí být jeho ciferný součet dělitelný devíti. Připadají tedy do úvahy součty 18 a 27. Ovšem ze sudých čísel nevytvoříme lichý součet. Ciferný součet tedy musí být 18. Ten se z daných cifer dá vytvořit třemi způsoby: $2+2+2+6+6$ - existuje $\dfrac{5!}{2!3!}$ přerovnání. $6+4+4+2+2$ - existuje $\dfrac{5!}{2!2!}$ přerovnání. $4+4+4+4+2$ - existuje $\dfrac{5!}{4!}$ přerovnání. Celkem $\dfrac{5!}{2!3!}+\dfrac{5!}{2!2!}+\dfrac{5!}{4!}$ čísel.

Řešení

Ukázat

Nejmenší vytvořitelné číslo 22222 má ciferný součet 10. Největší vytvořitelné číslo 666666 má ciferný součet 30. Aby bylo číslo dělitelné devíti, musí být jeho ciferný součet dělitelný devíti. Připadají tedy do úvahy součty 18 a 27. Ovšem ze sudých čísel nevytvoříme lichý součet. Ciferný součet tedy musí být 18. Ten se z daných cifer dá vytvořit třemi způsoby:

$2+2+2+6+6$ - existuje

$\dfrac{5!}{2!3!}$ přerovnání.

$6+4+4+2+2$ - existuje

$\dfrac{5!}{2!2!}$ přerovnání.

$4+4+4+4+2$ - existuje

$\dfrac{5!}{4!}$ přerovnání.
Celkem

$\dfrac{5!}{2!3!}+\dfrac{5!}{2!2!}+\dfrac{5!}{4!}$ čísel.

Příklad 503

Uchazeč o přijetí na VŠ musí úspěšně složit všechny čtyři zkoušky. Za každou úspěšně vykonanou zkoušku získá buď 2, nebo 3, nebo 4 body. Pro přijetí stačí dosáhnout aspoň 13 bodů. Kolik různých "vysvědčení" je možné takto vytvořit, aby byl uchazeč přijat?

Řešení	Ukázat
(a) získá 16 bodů: 1 možnost (b) získá 15 bodů: součet bude $4+4+4+3.$ V tomto součtu můžeme trojku umístit na 4 místa -> 4 možnosti (c) získá 14 bodů: součet $4+4+4+2$ -> 4 možnosti, nebo součet $4+4+3+3$ -> ${4\choose2}=6$ možností. (d) získá 13 bodů: součet $4+3+3+3$ -> 4 možnosti, nebo součet $4+4+2+3$ -> ${4\choose1}\cdot{3\choose1}=12$ možností. Celkem $1+4+4+6+4+12=31$ různých vysvědčení.

Řešení

Ukázat

(a) získá 16 bodů: 1 možnost
(b) získá 15 bodů: součet bude

$4+4+4+3.$ V tomto součtu můžeme trojku umístit na 4 místa -> 4 možnosti
(c) získá 14 bodů: součet

$4+4+4+2$ -> 4 možnosti, nebo součet

$4+4+3+3$ ->

${4\choose2}=6$ možností.
(d) získá 13 bodů: součet

$4+3+3+3$ -> 4 možnosti, nebo součet

$4+4+2+3$ ->

${4\choose1}\cdot{3\choose1}=12$ možností.
Celkem

$1+4+4+6+4+12=31$ různých vysvědčení.

Příklad 504

Určete součet všech čtyřciferných čísel sestavených z číslic 1, 3, 5, 7 když se číslice v čísle nesmí opakovat.

Řešení	Ukázat
Bude $4!=24$ různých čísel. Každá z uvedených cifer se bude na místě jednotek vyskytovat ve čtvrtině případů, na místě desítek, stovek i tisíců stejně tak. Součet bude $6(7+5+3+1)+60(7+5+3+1)+600(7+5+3+1)+6000(7+5+3+1)=6666\cdot16=106656$

Příklad 505

Máme karty očíslované čísly 1 až 20. Kolika způsoby z nich můžeme vybrat tři karty tak, aby aspoň na dvou z nich byla dvouciferná čísla a aspoň na dvou z nich byla sudá čísla?

Řešení	Ukázat
Aspoň dvě dvouciferná čísla můžeme vytáhnout $9\cdot{11\choose2}+{11\choose3}$ způsoby. Aspoň dvě sudá čísla můžeme vytáhnout $10\cdot{10\choose2}+{10\choose3}$ způsoby. Aspoň dvě sudá dvouciferná čísla můžeme vytáhnout $14\cdot{6\choose2}+{6\choose3}$ způsoby. Podle PIE je celkem $9\cdot{11\choose2}+{11\choose3}+10\cdot{10\choose2}+{10\choose3}-14\cdot{6\choose2}-{6\choose3}$ výběrů.

Řešení

Ukázat

Aspoň dvě dvouciferná čísla můžeme vytáhnout

$9\cdot{11\choose2}+{11\choose3}$ způsoby.
Aspoň dvě sudá čísla můžeme vytáhnout

$10\cdot{10\choose2}+{10\choose3}$ způsoby.
Aspoň dvě sudá dvouciferná čísla můžeme vytáhnout

$14\cdot{6\choose2}+{6\choose3}$ způsoby.
Podle PIE je celkem

$9\cdot{11\choose2}+{11\choose3}+10\cdot{10\choose2}+{10\choose3}-14\cdot{6\choose2}-{6\choose3}$ výběrů.

Příklad 506

Určete součet všech pěticiferných čísel, které je možné napsat pomocí cifer 1, 2, 3, 4, 5, přičemž každá cifra se vyskytuje právě jednou. Stejnou úlohu řešte pro pěticiferná čísla, které je možné napsat pomoci cifer $\{1,..,9\}$ když se každá cifra vyskytuje nejvýše jednou.

Řešení	Ukázat
Stejně jako příklad 504. (a) $24(1+2+3+4+5)\cdot11111$ ( $24=\frac{5!}5$ ) (b) $3024(1+2+\dots+9)\cdot11111$ ( $3024=\frac{9\cdot8\cdot7\cdot6\cdot5}{5}$ )

Příklad 507

Kolika způsoby můžeme vybrat z čísel od 1 do 30 tři čísla tak, aby jejich součet byl dělitelný
(a) dvěma
(b) třemi?

Řešení	Ukázat
(a) Jsou dva případy. Buďto vytáhneme tři sudá čísla, což lze udělat ${15\choose3}$ způsoby, nebo jedno sudé a dvě lichá čísla. To lze $15\cdot{15\choose2}$ způsoby. Celkem ${15\choose3}+15\cdot{15\choose2}$ způsobů. (b) Jsou dva případy. Buďto vytáhneme tři čísla, která mají stejný zbytek po dělení třemi. Pro každý možný zbytek (0, 1, 2) je ${10\choose3}$ možností, celkem $\left[{10\choose3}\right]^3.$ Nebo vytáhneme tři čísla, z nichž každé má jiný zbytek po dělení třemi. Pro každý zbytek je 10 možností, celkem $10^3.$ Celkem $\left[{10\choose3}\right]^3+10^3$ způsobů.

Řešení

Ukázat

(a) Jsou dva případy. Buďto vytáhneme tři sudá čísla, což lze udělat

${15\choose3}$ způsoby, nebo jedno sudé a dvě lichá čísla. To lze

$15\cdot{15\choose2}$ způsoby.
Celkem

${15\choose3}+15\cdot{15\choose2}$ způsobů.
(b) Jsou dva případy. Buďto vytáhneme tři čísla, která mají stejný zbytek po dělení třemi. Pro každý možný zbytek (0, 1, 2) je

${10\choose3}$ možností, celkem

$\left[{10\choose3}\right]^3.$ Nebo vytáhneme tři čísla, z nichž každé má jiný zbytek po dělení třemi. Pro každý zbytek je 10 možností, celkem

$10^3.$
Celkem

$\left[{10\choose3}\right]^3+10^3$ způsobů.

Příklad 508

Určete počet všech čtyřciferných čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než $\{0, 1, 2, 5, 7\}.$

Řešení	Ukázat
Ciferný součet musí být 9, nebo 18 (součet 27 z těchto cifer nevytvoříme). (a) součet 18: jsou možné dva typy (i) $5+5+7+1$ , nebo (ii) $7+7+2+1$ . Oba typy mají $\frac{4!}{2!}$ možností uspořádání cifer. (b) součet 9: jsou možné 4 typy (i) $7+2+0+0$ s $2\cdot\frac{3!}{2!}$ permutacemi (ii) $5+2+1+1$ s $\frac{4!}{2!}$ permutacemi (iii) $5+2+2+0$ , nebo $7+1+1+0$ oba s $(\frac{4!}{2!}-\frac{3!}{2!})$ permutacemi Celkem $3\cdot\frac{4!}{2!}+2\cdot\frac{3!}{2!}+2(\frac{4!}{2!}-\frac{3!}{2!})=5\cdot\frac{4!}{2!}$ čísel.

Řešení

Ukázat

Ciferný součet musí být 9, nebo 18 (součet 27 z těchto cifer nevytvoříme).
(a) součet 18: jsou možné dva typy (i)

$5+5+7+1$ , nebo (ii)

$7+7+2+1$ . Oba typy mají

$\frac{4!}{2!}$ možností uspořádání cifer.
(b) součet 9: jsou možné 4 typy
(i)

$7+2+0+0$ s

$2\cdot\frac{3!}{2!}$ permutacemi
(ii)

$5+2+1+1$ s

$\frac{4!}{2!}$ permutacemi
(iii)

$5+2+2+0$ , nebo

$7+1+1+0$ oba s

$(\frac{4!}{2!}-\frac{3!}{2!})$ permutacemi
Celkem

$3\cdot\frac{4!}{2!}+2\cdot\frac{3!}{2!}+2(\frac{4!}{2!}-\frac{3!}{2!})=5\cdot\frac{4!}{2!}$ čísel.

Příklad 509

Do restaurace dorazí 10 matematiků a objednávají si u číšníka pití. "Doneste nam každému jednu láhev džusu, tak že aspoň dva budou pomerančové, nejvýše pět borůvkových a počet jablečných džusů bude prvočíslo." Číšník měl v ledničce 15 lahví pomerančového, 10 borůvkového a 12 jablečného džusu. Kolika způsoby může objednávku realizovat? (Není důležité, co který matematik pije, ale pouze počty donesených lahví.)

Řešení	Ukázat
Objednávku rozdělíme podle počtu jablečných džusů: (a) 2 jablečné: musíme přidat dva pomerančové. Zbytek rozdělíme mezi pom. a borův. To lze ${6+2-1\choose6}=7$ způsoby. Musíme ale odečíst objednávku se šesti borůvkovými džusy, tj. $6$ objednávek (b) 3 jablečné: obdobně ${5+2-1\choose5}=6$ objednávek (c) 5 jablečných: ${3+2-1\choose3}=4$ objednávky (d) 7 jablečných: ${1+2-1\choose1}=2$ objednávky Celkem $6+6+4+2=18$ objednávek.

Řešení

Ukázat

Objednávku rozdělíme podle počtu jablečných džusů:
(a) 2 jablečné: musíme přidat dva pomerančové. Zbytek rozdělíme mezi pom. a borův. To lze

${6+2-1\choose6}=7$ způsoby. Musíme ale odečíst objednávku se šesti borůvkovými džusy, tj.

$6$ objednávek
(b) 3 jablečné: obdobně

${5+2-1\choose5}=6$ objednávek
(c) 5 jablečných:

${3+2-1\choose3}=4$ objednávky
(d) 7 jablečných:

${1+2-1\choose1}=2$ objednávky
Celkem

$6+6+4+2=18$ objednávek.

Příklad 510

Zkouška má dvě části: výpočetní a teoretickou. Výpočetní část obsahuje sedm příkladů a teoretická část obsahuje pět otázek. Kolik je možností, jak přiřadit bodové hodnocení příkladům a otázkám, jestliže součet bodů za výpočetní část je 65 a každý ze sedmi příkladů musí být za alespoň 5 bodů. Součet bodů za teoretickou část je 15, přičemž každá z pěti otázek musí být za alespoň jeden bod?

Řešení	Ukázat
Rozdělíme body za výpočetní část: Každému příkladu přiřadíme 5 bodů. Zbylých 30 bodů můžeme rozdělit libovolně (kombinace s opakováním) ${30+7-1\choose30}$ způsoby. Body za teoretickou část přiřadíme obdobným způsobem. Každé otázce přiřadíme bod a zbylých 10 bodů libovolně ${10+5-1\choose10}$ způsoby. Protože výběry jsou nezávislé je celkem ${36\choose30}\cdot{14\choose10}$ možností, jak přiřadit body.

Řešení

Ukázat

Rozdělíme body za výpočetní část: Každému příkladu přiřadíme 5 bodů. Zbylých 30 bodů můžeme rozdělit libovolně (kombinace s opakováním)

${30+7-1\choose30}$ způsoby. Body za teoretickou část přiřadíme obdobným způsobem. Každé otázce přiřadíme bod a zbylých 10 bodů libovolně

${10+5-1\choose10}$ způsoby. Protože výběry jsou nezávislé je celkem

${36\choose30}\cdot{14\choose10}$ možností, jak přiřadit body.

Příklad 511

Kolik existuje osmiciferných kódů sestavených z číslic 0 až 9, které obsahují právě šest různých číslic?

Řešení	Ukázat
Nejprve vybereme oněch 6 číslic. To lze ${10\choose6}$ způsoby. Nyní jsou dvě možnosti: (a) dvě číslice jsou dvakrát, ty vebereme ${6\choose2}$ způsoby a permutujeme $\dfrac{8!}{2!\cdot2! }$ (b) jedna číslice je třikrát. Vybereme ji ${6\choose1}$ způsoby a permutujeme $\dfrac{8!}{3! }$ Celkem ${10\choose6}\left[{6\choose2}\dfrac{8!}{2!\cdot2! }+{6\choose1}\dfrac{8!}{3! }\right]$

Příklad 512

Kolika způsoby lze rozesadit do řady osm studentů (po dvou ze čtyř různých škol) tak, aby žádní dva spolužáci neseděli vedle sebe?

Řešení	Ukázat
Všech možných uspořádání je $8!$ Uspořádání s aspoň jednou sousedící dvojicí je ${4\choose1}\cdot2\cdot7!$ Uspořádání s aspoň dvěma sousedícími dvojicemi je ${4\choose2}\cdot2^2\cdot6!$ Uspořádání s aspoň třemi sousedícími dvojicemi je ${4\choose3}\cdot2^3\cdot5!$ Uspořádání s aspoň čtyřmi sousedícími dvojicemi je ${4\choose4}\cdot2^4\cdot4!$ Podle PIE je celkový počet uspořádání $\displaystyle8!-\left[{4\choose1}\cdot2\cdot7!-{4\choose2}\cdot2^2\cdot6!+{4\choose3}\cdot2^3\cdot5!-{4\choose4}\cdot2^4\cdot4!\right]=\sum_{i=0}^4(-2)^i\cdot{4\choose i}\cdot(8-i)!$

Řešení

Ukázat

Všech možných uspořádání je

$8!$
Uspořádání s aspoň jednou sousedící dvojicí je

${4\choose1}\cdot2\cdot7!$
Uspořádání s aspoň dvěma sousedícími dvojicemi je

${4\choose2}\cdot2^2\cdot6!$
Uspořádání s aspoň třemi sousedícími dvojicemi je

${4\choose3}\cdot2^3\cdot5!$
Uspořádání s aspoň čtyřmi sousedícími dvojicemi je

${4\choose4}\cdot2^4\cdot4!$
Podle PIE je celkový počet uspořádání

$\displaystyle8!-\left[{4\choose1}\cdot2\cdot7!-{4\choose2}\cdot2^2\cdot6!+{4\choose3}\cdot2^3\cdot5!-{4\choose4}\cdot2^4\cdot4!\right]=\sum_{i=0}^4(-2)^i\cdot{4\choose i}\cdot(8-i)!$

Příklad 513

Kolika způsoby lze rozesadit kolem kulatého stolu šest studentů (po dvou ze tří různých škol) tak, aby žádní dva spolužáci neseděli vedle sebe? (Rozesazení, která na sebe přejdou pootočením stolu, považujeme za stejná.)

Řešení	Ukázat
Stejně jako příklad 512. Celkem $\displaystyle \sum_{i=0}^3(-2)^i\cdot{3\choose i}\cdot(5-i)!$

Příklad 514

Tabulka je rozdělena na $16\times16$ políček. Trpaslík po ní skáče dvěma směry - vpravo nebo dolů - přičemž střídá skoky o 2 (mezi startovním a cílovým polem je jedno políčku) a o 3 (mezi startovním a cílovým polem jsou dvě políčka) políčka (žádné 2 za sebou jdoucí skoky nejsou stejné délky). Začíná skokem délky 2 z levého horního políčka. Kolika cestami se může trpaslík dostat do pravého dolního políčka?

Řešení	Ukázat
Trpaslík musí vodorovně udělat tři kroky délky 2 a tři kroky délky 3. Stejně tak svisle. Řada 2-3-2-3-atd. je pevně daná. Musíme tedy vybrat 3 dvojky, které budou vodorovně a 3 trojky, které budou vodorovně. Výběry jsou nezávislé. Celkem ${6\choose3}\cdot{6\choose3}$ cest.

Příklad 515

Určete, kolik existuje anagramů slova "ANAKONDA" takových, aby se souhlásky a samohlásky střídaly.

Řešení	Ukázat
Jsou dva možné typy slov: XYXYXYXY, nebo YXYXYXYX, kde X reprezentuje souhlásku a Y samohlásku. Přerovnání samohlásek existuje $\dfrac{4!}{3!},$ přerovnání souhlásek je $\dfrac{4!}{2!}.$ Celkem $2\cdot\dfrac{4!}{3!}\cdot\dfrac{4!}{2!}$ anagramů.

Příklad 516

Balíček obsahuje 20 karet čtyř různých barev. Osm karet je černých a jsou očíslované, takže jsou rozlišitelné. Dále jsou tam 2 zelené, 6 žlutých a 4 červené karty. Tyto katry očíslované nejsou, takže karty stejných barev považujeme za nerozlišitelné. Z balíčku rozdáme 4 karty. Kolik existuje rozdání, v nichž jsou právě dvě černé karty?

Řešení	Ukázat
Černé karty můžeme vybrat ${8\choose2}$ způsoby, k nim pak ${4\choose2}$ ostatní barvy (kombinace s opakováním). Celkem ${8\choose2}{4\choose2}$ rozdání.

Příklad 517

Určete počet všech kladných trojciferných čísel, která obsahují aspoň jednu číslici 1.

Řešení	Ukázat
Všech trojciferných čísel je $9\cdot10^2.$ Čísel, která neobsahují žádnou jedničku je $8\cdot9^2$ . Celkem $9\cdot10^2-8\cdot9^2$ požadovaných čísel.

Příklad 518

Určete počet anagramů slova "STUPIDITA", ve kterých se nevyskytují žádná dvě stejná písmena vedle sebe.

Řešení	Ukázat
Podle PIE $\dfrac{9!}{2!\cdot2!}-\dfrac{2\cdot8!}{2!}+7!$

Příklad 519

V kavárně prodávají kávu ve čtyřech velikostech (malá, střední, velká a extra velká) a čtyř odrůd (keňskou, sumaterskou, hawajskou a kolumbijskou). Zákazníci si mohou ochutit kávu pěti příchuťmi (čokoláda, vanilka, lískové oříšky, maliny a kokosový ořech). Kolik různých kávových nápojů mohou servírovat?

Řešení	Ukázat
$4(\text{velikost})\cdot4(\text{druh})\cdot2^5(\text{s nebo bez sirupu})=512$

Příklad 520

Kolika způsoby lze umístit 9 červených, 9 zelených a 9 modrých kamenů na šachovnici $3\times3$ tak, že některý řádek je celý pokryt kameny stejné barvy? Na jednom políčku může být maximálně jeden kamen (tedy může být i prázdné).

Řešení	Ukázat
Aspoň jeden řádek pokrytý stejnou barvou: $3$ (výběr řádku) $\cdot3$ (výběr barvy na řádku) $\cdot4^6$ (pokrytí zbylých 6 polí) Aspoň dva řádky: ${3\choose2}\cdot3^2\cdot4^3$ Tři řádky: $3\cdot3\cdot3$ Podle PIE $9\cdot4^6-27\cdot4^3+27$