kombinatorika

Příklad 522

Máme k dispozici tři bonbóny malinové a sedm bonbónů citronových. Chceme-li sníst osm bonbónů, kolika způsoby je to možne? Na pořadí záleží

Řešení	Ukázat
Situace se musí rozložit podle počtů, například malinových bonbónů. Celkem 8 + 28 + 56 = 92 možností.

Příklad 523

Heslo se skládá ze čtyř znaků. Víme, že tři znaky jsou "3, g, N" a čtvrtý znak je jedna z číslic "3, 5, 7, 9". Kolik je všech možných hesel?

Řešení	Ukázat
(a) heslo obsahuje 2 trojky -> $\dfrac{4!}{2!}$ možností (b) heslo obsahuje jen jednu trojku -> ${3\choose1}\cdot4!$ možností Celkem $\dfrac{4!}{2!}+{3\choose1}\cdot4!$ hesel.

Příklad 524

Závodu se účastnilo 7 soutěžících z týmu A a 3 soutěžící z týmu B. Závod vyhrál člen týmu B a na třetím místě byl člen týmu A. Kolik existuje různých obsazení prvních tří medailových pozic?

Řešení	Ukázat
$3\cdot7\cdot8=168$ obsazení.

Příklad 525

Kolik hesel můžeme vytvořit z velkých a malých písmen anglické abecedy, pokud heslo smí mít od pěti do osmi znaků a musí obsahovat alespoň jedno velké a alespoň jedno malé písmeno?

Řešení	Ukázat
$\displaystyle\sum_{i=8}^852^i-2\cdot26^i$

Příklad 526

Hra Domino je složená z kostek tvaru kvádru, na jejichž jedné straně jsou dvojice polí s 0 až 6 oky. (a) Kolik existuje různých dominových kostek? (b) Kolik existuje různých dvojic kostek, ktere mají aspoň jedno číslo stejné?

Řešení	Ukázat
(a) Různých dvojic je ${7\choose2}=21$ a stejných dvojic je $7.$ Celkem $28$ různých dominových kostek. (b) Označíme $A$ množinu kostek s různými dvojicemi, $\|A\|=21$ a $B$ množinu kostek se stejnými dvojicemi, $\|B\|=7.$ Ke každé kostce z $B$ můžeme přiložit 6 kostek z $A$ (a žádnou z $B$ ), tj. $6\cdot7=42$ možností. Ke každé kostce z $A$ můžeme přidat $5$ kostek z $A$ , tj. $21\cdot5=105$ možností. Celkem $42+105=147$ různých dvojic.

Řešení

Ukázat

(a) Různých dvojic je

${7\choose2}=21$ a stejných dvojic je

$7.$ Celkem

$28$ různých dominových kostek.
(b) Označíme

$A$ množinu kostek s různými dvojicemi,

$|A|=21$ a

$B$ množinu kostek se stejnými dvojicemi,

$|B|=7.$
Ke každé kostce z

$B$ můžeme přiložit 6 kostek z

$A$ (a žádnou z

$B$ ), tj.

$6\cdot7=42$ možností.
Ke každé kostce z

$A$ můžeme přidat

$5$ kostek z

$A$ , tj.

$21\cdot5=105$ možností.
Celkem

$42+105=147$ různých dvojic.

Příklad 527

Kolik značek Morseovy je možné vytvořit, sestavujeme-li tečky a čárky do skupin o jednom až čtyřech znacích?

Řešení	Ukázat
$2^1+2^2+2^3+2^4=30$

Příklad 528

Kolik aspoň osmipísmenných řetězců lze vytvořit z písmen slova "BALAKLAVA"?

Řešení	Ukázat
Devítipísmenných řetězců je $\dfrac{9!}{2!\cdot4!}.$ Osmipísmenné řetězce si rozdělíme na tři skupiny: (a) chybí jedno unikátní písmeno (B, K, V): takových řetězců je $\dfrac{8!}{2!\cdot4!}.$ (b) chybí A: $\dfrac{8!}{2!\cdot3!}.$ (c) chybí L: $\dfrac{8!}{4!}.$ Celkem $\dfrac{9!}{2!\cdot4!}+3\cdot\dfrac{8!}{2!\cdot4!}+\dfrac{8!}{2!\cdot3!}+\dfrac{8!}{4!}$

Příklad 529

Kolika různými způsoby může proběhnout zápas mezi tenisty A a B hraný na tři vítězné sety?

Řešení	Ukázat
A může vyhrát třemi výsledky (a) 3:0 -> zápas měl jeden průběh. (b) 3:1 -> zápas může mít tři různé průběhy (B vyhrál 1., 2., nebo 3. set) (c) 3:2 -> zápas může mít šest různých průběhů (utkání se musí dostat do stavu 2:2. To znamená, že B musí z prvních čtyř setů vyhrát dva. Vybíráme ${4\choose2}=6$ Stejné argumenty platí, když vyhraje B. Celkem 20 různých průběhů.

Řešení

Ukázat

A může vyhrát třemi výsledky
(a) 3:0 -> zápas měl jeden průběh.
(b) 3:1 -> zápas může mít tři různé průběhy (B vyhrál 1., 2., nebo 3. set)
(c) 3:2 -> zápas může mít šest různých průběhů (utkání se musí dostat do stavu 2:2. To znamená, že B musí z prvních čtyř setů vyhrát dva. Vybíráme

${4\choose2}=6$
Stejné argumenty platí, když vyhraje B. Celkem 20 různých průběhů.

Příklad 530

V obchodě mají 6 různých druhů USB flashek. Čtyři kamarádi si je tam jdou koupit, každý jednu. Kolika různými způsoby si mohou vybrat flashky tak, aby se některá opakovala?

Řešení	Ukázat
Všech možných nákupů je $6^4.$ Všech nákupů bez opakování je $V_4(6)=\frac{6!}{2!}.$ Celkem $6^4-\frac{6!}{2!}.$

Příklad 531

Urči počet deseticiferných čísel, jejichž ciferný součet je roven 10.

Řešení	Ukázat
Do deseti přihrádek rozmisťuju 10 kuliček - každá přihrádka reprezentuje cifru. Do první musím dát jednu kuličku - na začátku nemůže být nula. Zbylých 9 rozmisťuju libovolně (kombinace s opakováním) ${10+9-1\choose9}={18\choose9}$ způsoby. Musím ale odečíst situaci, kdy je všech deset kuliček v první přihrádce. Celkem existuje ${18\choose9}-1$ čísel s požadovanou vlastností.

Řešení

Ukázat

Do deseti přihrádek rozmisťuju 10 kuliček - každá přihrádka reprezentuje cifru. Do první musím dát jednu kuličku - na začátku nemůže být nula. Zbylých 9 rozmisťuju libovolně (kombinace s opakováním)

${10+9-1\choose9}={18\choose9}$ způsoby. Musím ale odečíst situaci, kdy je všech deset kuliček v první přihrádce.
Celkem existuje

${18\choose9}-1$ čísel s požadovanou vlastností.

Příklad 532

Mějme řetězec "TESTOVACIRETEZEC"
(a) Kolika existuje anagramů tohoto řetězce?
(b) Kolik existuje anagramů tohoto řetězce, v nichž první nebo poslední písmeno nezůstane na svém místě?
(c) Kolik existuje třípísmenných řetězců, které jdou z písmen tohoto řetězce sestavit?

Řešení	Ukázat
(a) $\dfrac{16!}{2!\cdot3!\cdot4!}$ (b) první: $\dfrac{15!}{2!\cdot2!\cdot4!},$ poslední: $\dfrac{15!}{3!\cdot4!},$ obě: $\dfrac{14!}{2!\cdot4!}.$ Celkem $\dfrac{15!}{2!\cdot2!\cdot4!}+\dfrac{15!}{3!\cdot4!}-\dfrac{14!}{2!\cdot4!}$ (c) i) 3 stejná písmena: $2$ řetězce ii) 2 stejná + 1 jiné: $3\cdot9\cdot3=81$ iii) 3 různá: $V_3(10)=720$ Celkem $803$ řetězců.

Příklad 533

Tři děti si mají rozdělit 6 různých hraček. Kolika způsoby se o ně mohou podělit tak, aby každé dítě mělo alespoň jednu hračku?

Řešení	Ukázat
K hračkám: možno postupovat i naopak: pro každou hračku se rozhodneme, komu ji dáme: $3^6$ možností. Odečteme možnosti, kdy jedno dítě nic nedostalo: $3\cdot2^6$ možností. Stavy, kdy všechno dostalo jedno dítě jsme odečetli dvakrát, jednou je přičteme: $3$ možnosti. $729-192+3=540.$ způsobů

Příklad 534

V obchodě je 15 druhů pohlenic v dostatečném počtu. Kolika způsoby lze zaslat třem adresátům po dvou různých pohlednicích?

Řešení	Ukázat
$\left[{15\choose2}\right]^3$

Příklad 535

Kolika způsoby lze setavit pětičlenný tým z 15-ti dívek a 10-ti chlapců, když tým musí obsahovat aspoň 2 chlapce a aspoň dvě dívky?

Řešení	Ukázat
${15\choose2}{10\choose3}+{15\choose3}{10\choose2}$

Příklad 536

Kolik 7-písmenných řetězců můžeme sestavit z písmen anglické abecedy, když řetězec musí obsahovat aspoň 3 samohlásky?

Řešení	Ukázat
Všech řetězců je $26^7.$ Řetězců bez samohlásky je $20^7.$ Řetězců s jednou samohláskou je $6$ (samohláska) $\cdot7$ (pozice) $\cdot20^6$ (zbytek). Řetězců se dvěma samohláskami (a) stejné: $6\cdot{7\choose2}\cdot20^5$ (b) různé: ${6\choose2}\cdot7\cdot6\cdot20^5$ Celkem $26^7-20^7-6\cdot7\cdot20^6-6\cdot{7\choose2}\cdot20^5-{6\choose2}\cdot7\cdot6\cdot20^5$

Příklad 537

Kolika způsoby můžeme uspořádat písmena slova "PLAY", když první písmeno nemůže být "A" a druhé nemůže být "Y"?

Řešení	Ukázat
Všech uspořádání je $4!$ Uspořádání, v nichž je "A" první je $3!,$ stejně tak uspořádání, v nichž je "Y" druhé. Uspořádání, v nichž je na začátku "AY" je $2!$ Podle PIE je $4!-2\cdot3!+2!$ vhodných uspořádání.

Příklad 538

Kolik 10-ti písmenných řetězců obsahujících aspoň 8 souhlásek můžeme sestavit z písmen anglické abecedy, pokud se v nich písmena neopakují?

Řešení	Ukázat
Postup: vybereme souhlásky, pak vybereme samohlásky a pak přerovnáme (a) právě 8 souhlásek: ${20\choose8}\cdot{6\choose2}\cdot10!$ (b) právě 9 souhlásek: ${20\choose9}\cdot{6\choose1}\cdot10!$ (c) právě 10 souhlásek: ${20\choose10}\cdot{6\choose0}\cdot10!$ Celkem ${20\choose8}\cdot{6\choose2}\cdot10!+{20\choose9}\cdot{6\choose1}\cdot10!+{20\choose10}\cdot{6\choose0}\cdot10!$

Příklad 539

Kolik anagramů slova "MISSISSIPPI" neobsahuje podslovo "PSI"?

Řešení	Ukázat
Všech anagramů je $\dfrac{11!}{4!4!2!}.$ Anagramů s aspoň jedním podslovem "PSI" je $\dfrac{9!}{3!3!}.$ Anagramů se dvěma podslovy "PSI" je $\dfrac{7!}{2!2!2!}.$ Celkem podle PIE $\dfrac{11!}{4!4!2!}-\dfrac{9!}{3!3!}+\dfrac{7!}{2!2!2!}.$

Příklad 540

Je dána třípísmenná abeceda. Určete počet 5-ti písmenných slov, v nichž je každé písmeno abecedy aspoň jednou.

Řešení	Ukázat
Jsou dva typy slov (a) 2+2+1: ${3\choose1}$ (výběr individuálního znaku) $\dfrac{5!}{2!2!}$ (přerovnání) (b)1+1+3: ${3\choose1}$ (výběr trojnásobného znaku) $\dfrac{5!}{3!}$ (přerovnání) Celkem ${3\choose1}\left[\dfrac{5!}{2!2!}+\dfrac{5!}{3!}\right]$

666 příkladů z kombinatoriky

Komplexní úlohy VI

Příklad 522

Příklad 523

Příklad 524

Příklad 525

Příklad 526

Příklad 527

Příklad 528

Příklad 529

Příklad 530

Příklad 531

Příklad 532

Příklad 533

Příklad 534

Příklad 535

Příklad 536

Příklad 537

Příklad 538

Příklad 539

Příklad 540

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