kombinatorika

Příklad 481

Kolik existuje tříciferných čísel, která mají všechny cifry různé a mají sudý ciferný součet?

Řešení	Ukázat
Jsou čtyři typy čísel (a) SLL: $4\cdot5\cdot4=80$ (b) SSS: $4\cdot4\cdot4\cdot3=48$ (c) LSL: $5\cdot5\cdot4=100$ (d) LLS: $5\cdot4\cdot5=100$ Celkem 328 čísel

Příklad 482

Máme posloupnost délky 6, která je tvořená písmeny "A" a "B". Kolik je takových posloupnosti, v nichž žádná dvě "A" nesousedí?

Řešení	Ukázat
Posloupnosti rozdělíme podle počtu "A" (a) 0 "A" -> ${7\choose0}=1$ možnost (b) 1 "A" -> ${6\choose1}=6$ možností (c) 2 "A" -> ${5\choose2}=10$ možností (d) 3 "A" -> ${4\choose3}=4$ možnosti Celekm 21 posloupností.

Příklad 483

Ze slova "LAJOLLA" vybereme tři písmena a sestavíme z nich třípísmenné slovo. (a) Kolika způsoby to můžeme udělat? (b) Kolika způsoby můžeme sestavit sedmipísmenné slovo? Každé písmeno můžeme použít nejvýše tolikrát, kolikrát se vyskytuje ve slově "LAJOLLA".

Řešení	Ukázat
(a) Jsou tři typy slov (i) žádné písmeno se neopakuje: ${4\choose3}\cdot 3!=24$ (ii) právě dvě "A" nebo právě dvě "L": opakující se písmeno můžu vybrat dvěma způsoby, třetí písmeno pak třemi způsoby: $2\cdot3\cdot\dfrac{3!}{2!}=18$ (iii) právě tři "L": $1$ Celkem $24+18+1=43$ slov (b) Sedmipísmenných slov je $\dfrac{7!}{3!\cdot2!}=420$

Příklad 484

Koncertní mistr má nacvičených 6 skladeb. Z nich na koncertě zahraje 4 skladby. Po skončení programu zahraje 2 přídavky s tím, že oba vybere pouze ze skladeb, které ten den už hrál, s výjimkou poslední. Kolik různých posloupností skladeb může na koncertě zaznít?

Řešení	Ukázat
První 4 skladby může zahrát $V_4(6)$ způsoby, přídavky pak $V_2(3)$ způsoby. Celkem $V_4(6)\cdot V_2(3)$ posloupností.

Příklad 485

Kolik existuje anagramů slova "ABRAKADABRA" takových, že v nich žádná dvě písmena "A" nesousedí a současně nesousedí ani žádná dvě písmena "B"?

Řešení	Ukázat
Všech slov, v nichž "A" nesousedí je ${7\choose5}\cdot\dfrac{6!}{2!\cdot2!}.$ Všech slov, v nichž "A" nesousedí a současně "B" sousedí, je ${6\choose5}\cdot\dfrac{5!}{2!}.$ Celkem ${7\choose5}\cdot\dfrac{6!}{2!\cdot2!}-{6\choose5}\cdot\dfrac{5!}{2!}$ požadovaných anagramů.

Příklad 486

Kolik pětibitových řetězců obsahuje aspoň tři "0" vedle sebe nebo aspoň tři "1" vedle sebe?

Řešení	Ukázat
Jsou tři typy pro jedničky (a) 3 jedničky: 3 možnosti (b) 4 jedničky: 2 možnosti (c) 4 jedniček: 1 možnost Pro nuly je to stejné. Celkem 12 řetězců.

Příklad 487

Kolik existuje 10-ciferných čísel, ve kterých je součet číslic rovných 3?

Řešení	Ukázat
Jsou tři typy čísel: (a) 3 jedničky a 7 nul: ${9\choose2}$ možností. (b) 1 jednička, 1 dvojka a 8 nul: $2\cdot{9\choose1}$ možností. (c) 1 trojka a 9 nul: $1$ možnost. Celkem ${9\choose2}+2\cdot{9\choose1}+1$ čísel.

Příklad 488

Na štábu je 6 generálů, 8 plukovníků a 10 majorů. Kolika způsoby z nich můžeme vytvořit osmičlennou komisi. (Důležitá je jen hodnost, nikoli jmeno.)

Řešení	Ukázat
Všech výběrů je ${10\choose8}$ (kombinace s opakováním). Mezi těmito výběry jsou ale i takové, v nichž je 8 generálů (1 výběr) a 7 generálů (2 výběry). Celkem ${10\choose8}-3$ komisí.

Příklad 489

Určete počet všech pěticifernych přirozených čísel dělitelných čtyřmi, jejichž dekadický zápis se skládá z číslic 0, 2, 3, 5, 7, 8 a každá z těchto číslic je v něm nejvýše jednou.

Řešení	Ukázat
Aby číslo bylo dělitelné čtyřmi, musí být dělitelné čtyřmi poslední dvojčíslí. Rozdělíme si koncová dvojčíslí na dvě kategorie podle toho, zada obsahují nulu. (a) 08, 20, 80: $3\cdot V_3(4)$ (b) 28, 32, 52, 72: $4[V_3(4)-V_2(3)]$ Celekm $7V_3(4)-4V_2(3)$ čísel.

Příklad 490

Máme 5 prázdných rozlišitelných sáčků. Do každého z nich máme dát 1 až 4 bonbóny. Bonbóny vybíráme z 15 různých druhů a od každého druhu máme dostatečnou zásobu bonbónů. Kolik je možných způsobů, jak to udělat?

Řešení	Ukázat
Nadefinujeme si šestnáctý druh - "prázdný" bonbón. Pro jeden sáček pak vybíráme čtveřici a opakování je povoleno. Je tedy ${16+4-1\choose4}={19\choose4}$ různých výběrů. Od tohoto počtu musíme odečíst jeden výběr, při němž vybereme 4 "prázdné" bonbóny. Celkem $\left[{19\choose4}-1\right]^5$ způsobů.

Příklad 491

Kolik existuje anagramů slova "RINTINTIN", ve kterých jsou vždy dvě "I" vedle sebe, ale ne tři "I" vedle sebe?

Řešení	Ukázat
Spočítáme počet anagramů, v nichž jsou aspoň dvě "I" vedle sebe. Dvě "I" zabalíme do "balíku" a (permutace s opakováním) určíme počet: $\dfrac{8!}{2!\cdot 3!}.$ Nyní určíme počet slov, v nichž jsou 3 "I" vedle sebe. Těch je $\dfrac{7!}{2!\cdot 3!}.$ Při prvním počítání jsme započítali slova s třemi sousedními "I" dvakrát. Např. slovo "RIIINNNTT" jako "RINNNTT" a "RINNNTT". Celkem je $\dfrac{8!}{2!\cdot 3!}-2\cdot\dfrac{7!}{2!\cdot 3!}$ požadovaných anagramů.

Řešení

Ukázat

Spočítáme počet anagramů, v nichž jsou aspoň dvě "I" vedle sebe. Dvě "I" zabalíme do "balíku" a (permutace s opakováním) určíme počet:

$\dfrac{8!}{2!\cdot 3!}.$
Nyní určíme počet slov, v nichž jsou 3 "I" vedle sebe. Těch je

$\dfrac{7!}{2!\cdot 3!}.$
Při prvním počítání jsme započítali slova s třemi sousedními "I" dvakrát. Např. slovo "RIIINNNTT" jako "RIIINNNTT" a "RIIINNNTT".
Celkem je

$\dfrac{8!}{2!\cdot 3!}-2\cdot\dfrac{7!}{2!\cdot 3!}$ požadovaných anagramů.

Příklad 492

Kolik existuje šesticiferných kódů sestavených z číslic 0 až 9, ve kterých se nevyskytují žádné dvě sudé číslice vedle sebe? Kód může začínat cifrou 0.

Řešení	Ukázat
Rozdělíme na disjunktní případy (a) kód neobsahuježádnou sudou cifru: $5^6$ možností (b) kód obsahuje právě jednu sudou cifru: ${6\choose1}\cdot5\cdot5^5$ (c) kód obsahuje právě dvě sudé cifry: ${5\choose2}\cdot5^2\cdot5^4$ (d) kód obsahuje právě tři sudé cifry: ${4\choose3}\cdot5^3\cdot5^3$ Celkem $5^6\left[1+{6\choose1}+{5\choose2}+{4\choose3}\right]$

Příklad 493

Kolik existuje šesticiferných přirozených čísel dělitelných čtyřmi, v jejichž dekadickem zápisu se vyskytují pouze číslice 1, 2, 3, 4, 5. Každá číslice se může vyskytovat vícekrát.

Řešení	Ukázat
Poslední dvojčíslí musí být dělitelné čtyřmi - přichází do úvahy pouze 12, 24, 32, 44, 52. Zbylé 4 cifry vybíráme libovolně. Celkem $6^4\cdot5$

Příklad 494

Ve fotbalovém turnaji bude hrát 5 družstev tak, že se střetne každé s každým jednou. Turnaj se hraje na jednom hřišti. Kolika způsoby můžeme stanovit pořadí utkání, když se v prvních třech utkáních musí představit všechna družstva?

Řešení	Ukázat
V turnaji se odehraje ${5\choose2}=10$ zápasů. Z těchto zápasů vybereme trojici. To můžeme udělat ${10\choose3}$ způsoby. Trojic jen se čtyřmi družstvy je ${5\choose4}\cdot{6\choose3}.$ Trojic jen se třemi družstvy je ${5\choose3}\cdot{3\choose3}.$ Podle PIE je počet vhodných trojic zápasů ${10\choose3}-{5\choose4}\cdot{6\choose3}+{5\choose3}\cdot{3\choose3}.$ Trojice můžeme uspořádat $3!$ způsoby. Celkem $\left[{10\choose3}-{5\choose4}\cdot{6\choose3}+{5\choose3}\cdot{3\choose3}\right]\cdot3!$ vhodných pořadí.

Řešení

Ukázat

V turnaji se odehraje

${5\choose2}=10$ zápasů. Z těchto zápasů vybereme trojici. To můžeme udělat

${10\choose3}$ způsoby.
Trojic jen se čtyřmi družstvy je

${5\choose4}\cdot{6\choose3}.$
Trojic jen se třemi družstvy je

${5\choose3}\cdot{3\choose3}.$
Podle PIE je počet vhodných trojic zápasů

${10\choose3}-{5\choose4}\cdot{6\choose3}+{5\choose3}\cdot{3\choose3}.$
Trojice můžeme uspořádat

$3!$ způsoby.
Celkem

$\left[{10\choose3}-{5\choose4}\cdot{6\choose3}+{5\choose3}\cdot{3\choose3}\right]\cdot3!$ vhodných pořadí.

Příklad 495

Kolika způsoby můžeme na běžné šachovnici $8 \times 8$ vybrat dvě různobarevná pole tak, aby obě neležela ve stejném řádku ani sloupci?

Řešení	Ukázat
Černé pole můžume vybrat 32 způsoby a pak bílé 24 způsoby. Celkem $32\cdot24=768$ možností.

Příklad 496

Kolika způsoby můžeme napsat číslo 50 jako součet třicetipěti sčítanců 1 a 2, když rozlišujeme pořadí sčítanců?

Řešení	Ukázat
Jestliže označíme $x$ počet jedniček, musí platit $x+2(35-x)=50\\x=20$ V součtu bude 20 jedniček a 15 dvojek. Stačí vybrat pozice pro jedničky, což lze ${35\choose20}$ způsoby.

Příklad 497

Kolika způsoby můžeme posadit 5 manželských párů kolem kulatého stolu tak, aby manželé seděli vždy vedle sebe? Ve dvou rozdílných rozesazeních má některý člověk jiného souseda po levé nebo po pravé ruce.

Řešení	Ukázat
Pokud si představíme páry jako jednotky, můžeme je rozesadit $4!$ způsoby. V každém páru jsou dvě možnosti, jak manžele posadit. Celkem $2^5\cdot4!$ způsobů

Příklad 498

Kolik existuje šestimístných přirozených čísel, která mají ve svém zápisu nejvýše jednu cifru 1?

Řešení	Ukázat
(a) žádná jednička: $8\cdot9^5$ čísel. (b) právě jedna jednička: (i) jednička je na 1. místě: $9^5$ čísel. (ii) jednička není na prvním místě: $8\cdot5\cdot9^4$ čísel. Celkem $8\cdot9^5+9^5+8\cdot5\cdot9^4$ čísel.

Příklad 499

Máme slovo"KOMBINATORIKA".
(a) Kolik různých slov můžeme vytvořit přerovnáním písmen v tomto slově?
(b) Kolik z těchto slov nemá za sebou 2 písmena K?
(c) Kolik z těchto slov (z bodu (a)) nemá za sebou dvě souhlásky ani dvě samohlásky?

Řešení	Ukázat
(a) $\dfrac{13!}{(2!)^4}=\dfrac{13!}{2^4}$ (b) počet slov, která mají 2 K za sebou je $\dfrac{12!}{2^3},$ celkem pak $\dfrac{13!}{2^4}-\dfrac{12!}{2^3}$ (c) Slova musí být typu XYXYXYXYXYXYX, kde X představuje souhlásku a Y samohlásku. Souhlásky můžeme rozmístit $\dfrac{7!}{2!}$ způsoby, samohlásky $\dfrac{6!}{(2!)^3}$ způsoby. Celekm $\dfrac{7!}{2!}\cdot\dfrac{6!}{(2!)^3}$ způsobů.

Řešení

Ukázat

(a)

$\dfrac{13!}{(2!)^4}=\dfrac{13!}{2^4}$
(b) počet slov, která mají 2 K za sebou je

$\dfrac{12!}{2^3},$ celkem pak

$\dfrac{13!}{2^4}-\dfrac{12!}{2^3}$
(c) Slova musí být typu XYXYXYXYXYXYX, kde X představuje souhlásku a Y samohlásku. Souhlásky můžeme rozmístit

$\dfrac{7!}{2!}$ způsoby, samohlásky

$\dfrac{6!}{(2!)^3}$ způsoby. Celekm

$\dfrac{7!}{2!}\cdot\dfrac{6!}{(2!)^3}$ způsobů.

Příklad 500

Určete počet šesticiferných přirozených čísel, jejichž ciferný součet je sudý.

Řešení	Ukázat
Vytvoříme všechna pěticiferná čísla. Těch je $9\cdot10^4.$ Každé takovéto číslo můžeme pěti způsoby doplnit na šesticiferné s požadovanou vlastností. Celkem $5\cdot9\cdot10^4$ čísel.

666 příkladů z kombinatoriky

Komplexní úlohy V

Příklad 481

Příklad 482

Příklad 483

Příklad 484

Příklad 485

Příklad 486

Příklad 487

Příklad 488

Příklad 489

Příklad 490

Příklad 491

Příklad 492

Příklad 493

Příklad 494

Příklad 495

Příklad 496

Příklad 497

Příklad 498

Příklad 499

Příklad 500

Napsat komentář Zrušit odpověď na komentář