kombinatorika

Příklad 301

Ve třídě je 35 žáků. 20 z nich navštěvuje matematický kroužek, 11 fyzikální a 10 žáků nenavštěvuje žádný z těchto kroužků. Kolik žáků navštěvuje matematický i fyzikální kroužek? Kolik jich navštěvuje jen matematický kroužek?

Řešení	Ukázat
Podle PIE platí $\begin{eqnarray}\|F\cup M\|&=&\|F\|+\|M\|-\|F\cap M\|\\25&=&11+20-x\\ x&=&6\end{eqnarray}$ Oba kroužky navštěvuje 6 žáků, jen matematický pak $20-6=14$ žáků.

Příklad 302

V oddělení výzkumného ústavu pracuje několik osob, z nichž každá zná alespoň jeden z těchto tří světových jazyků - angličtinu, němčinu nebo francouzštinu. Šest osob ovládá angličtinu, šest němčinu a sedm francouzštinu. Čtyři osoby hovoří anglicky i německy, 3 osoby německy i francouzsky a 2 osoby francouzsky i anglicky. Všechny tři jazyky ovládá jedna osoba. Kolik osob pracuje v oddělení?

Řešení	Ukázat
Podle PIE $\begin{eqnarray}\|A\cup F\cup N\|&=&6+6+7-(4+3+2)+1\\\|A\cup F\cup N\|&=&11 \end{eqnarray}$ V ústavu pracuje 11 osob.

Příklad 303

V oddělení ústavu pracuje několik osob, z nichž každá ovládá aspoň jeden cizí jazyk: 7 osob ovládá angličtinu, 7 němčinu, 1 španělštinu, 8 francouzštinu, 5 umí německy a anglicky, 4 německy a francouzsky, 3 francouzsky a anglicky, 1 španělsky a německy, 1 španělsky a anglicky, 1 španělsky a francouzsky, 2 umí německy, francouzsky, anglicky, 1 umí španělsky, německy, anglicky, 1 španělsky, francouzsky, německy, 1 španělsky, francouzsky, anglicky a 1 osoba ovládá všechny 4 jazyky. Určete, kolik osob pracuje v ústavu?

Řešení	Ukázat
Podle PIE $\begin{eqnarray}\|A\cup F\cup N\cup S\|&=&7+7+8+1-(5+4+3+1+1+1)+(2+1+1+1)-1\\\|A\cup F\cup N\cup S\|&=&12\end{eqnarray}$ V ústavu pracuje 12 osob.

Příklad 304

Zkoušku, která se skládala ze tří příkladů psalo 120 studentů. 1. příklad vyřešilo 55 studentů, druhý 44 a třetí 34. Všechny tři příklady vyřešilo 12 studentů a právě dva příklady 25 studentů. Kolik studentů nevyřešilo ani jeden příklad?

Řešení	Ukázat
Podle PIE aspoň jeden příklad vyřešilo $\begin{eqnarray}\|1.\cup 2.\cup3.\|&=&\|1.\|+\|1.\|+\|3.\|-(\|1.\cap2.\| +\|1.\cap 3.\|+\|2.\cap 3.\|)+\|1.\cap 2.\cap3.\|\\\|1.\cup 2.\cup3.\|&=&55+44+34-25+12\\ \|1.\cup 2.\cup3.\|&=&120\end{eqnarray}$ Takže každý student spočítal aspoň jeden příklad.

Příklad 305

V ročníku je 200 studentů. 100 z nich udělalo zkoušku z matematiky (M), 150 z fyziky (F) a 175 z češtiny (Č). M i F udělalo 75 studentů, M i Č 80 studentů a F a Č udělalo 130 studentů. Jaký je nejvyšší možný počet studentů, kteří neudělali ani jednu zkoušku? Kolik nejméně a nejvíce studentů udělalo všechny zkoušky?

Řešení	Ukázat
Když označíme $y=\|M\cap F\cap C\|$ , tak podle PIE $\begin{eqnarray}200\ge\|M\cup F\cup C\|&=&100+150+175-(75+80+130)+y\ge175\\200\ge140&+&y\ge175\\ 35\ge&y&\ge60\end{eqnarray}$ Všechny tři zkoušky udělalo minimálně 35 studentů a maximálně 60 studentů. Pak $200-140-35=25$ je maximální počet studentů, kteří nudělali ani jednu zkoušku.

Příklad 306

Kolik existuje přirozených čísel menších nebo rovnajících se 100, která nejsou dělitelná žádným z čísel 2, 3, 5?

Řešení	Ukázat
Pokud si označíme $D$ množinu čísel dělitelných dvěma ( $\le100$ ), obdobně $T$ a $P$ , pak $\|D\|=[\frac{100}2]=50$ ( $[x]$ značí celou část čísla $x$ ) $\|T\|=[\frac{100}3]=33$ $\|P\|=[\frac{100}5]=20$ $\|D\cap T\|=[\frac{100}6]=16$ , $\|D\cap P\|=[\frac{100}{10}]=10$ , $\|T\cap P\|=[\frac{100}{15}]=6$ $\|D\cap T\cap P\|=[\frac{100}{30}]=3$ . Podle PIE je počet čísel dělitelných aspoň jedním uvedeným číslem roven $\|D\cup T\cup P\|=50+33+20-(16+10+6)+3=74$ Počet čísel, která nejsou dělitelná žádným z uvedených čísel je $100-74=26$ .

Řešení

Ukázat

Pokud si označíme

$D$ množinu čísel dělitelných dvěma (

$\le100$ ), obdobně

$T$ a

$P$ , pak

$|D|=[\frac{100}2]=50$ (

$[x]$ značí celou část čísla

$x$ )

$|T|=[\frac{100}3]=33$

$|P|=[\frac{100}5]=20$

$|D\cap T|=[\frac{100}6]=16$ ,

$|D\cap P|=[\frac{100}{10}]=10$ ,

$|T\cap P|=[\frac{100}{15}]=6$

$|D\cap T\cap P|=[\frac{100}{30}]=3$ .
Podle PIE je počet čísel dělitelných aspoň jedním uvedeným číslem roven

$|D\cup T\cup P|=50+33+20-(16+10+6)+3=74$
Počet čísel, která nejsou dělitelná žádným z uvedených čísel je

$100-74=26$ .

Příklad 307

Kolik existuje kladných celých čísel menších než 420, která nejsou dělitelná žádným z čísel 2, 5, 7?

Řešení	Ukázat
Stejný postup jako předcházející příklad. $\|D\|=[\frac{419}2]=209$ $\|P\|=[\frac{419}5]=83$ $\|S\|=[\frac{419}7]=59$ $\|D\cap P\|=[\frac{419}{10}]=41$ , $\|D\cap S\|=[\frac{419}{14}]=29$ , $\|P\cap S\|=[\frac{419}{35}]=11$ $\|D\cap P\cap S\|=[\frac{419}{70}]=5$ . Podle PIE je počet čísel dělitelných aspoň jedním uvedeným číslem roven $\|D\cup P\cup S\|=209+83+59-(41+29+11)+5=275$ Počet čísel, která nejsou dělitelná žádným z uvedených čísel je $419-275=144$ .

Řešení

Ukázat

Stejný postup jako předcházející příklad.

$|D|=[\frac{419}2]=209$

$|P|=[\frac{419}5]=83$

$|S|=[\frac{419}7]=59$

$|D\cap P|=[\frac{419}{10}]=41$ ,

$|D\cap S|=[\frac{419}{14}]=29$ ,

$|P\cap S|=[\frac{419}{35}]=11$

$|D\cap P\cap S|=[\frac{419}{70}]=5$ .
Podle PIE je počet čísel dělitelných aspoň jedním uvedeným číslem roven

$|D\cup P\cup S|=209+83+59-(41+29+11)+5=275$
Počet čísel, která nejsou dělitelná žádným z uvedených čísel je

$419-275=144$ .

Příklad 308

Kolik prvků množiny $\{1, 2, \dots , 250\}$ není dělitelných ani 2, ani 5, ani 7, ani 11?

Řešení	Ukázat
Stejný postup jako příklad 306. Počet čísel, která nejsou dělitelná žádným z uvedených čísel je 79.

Příklad 309

Určete počet přirozených čísel menších než 210, která jsou nesoudělná s číslem 210.

Řešení	Ukázat
Číslo $210=2\cdot3\cdot5\cdot7.$ Hledáme tedy počet čísel, která nejsou dělitelná žádným z uvedených činitelů. Postup jako příklad 306. Nesoudělných čísel je 49.

Příklad 310

Osm dětí hraje hru, při níž se dobrovolně rozdělí na SKŘÍTKY, ČARODĚJE a OBRY. Aby se hra mohla uskutečnit, musí být pro každou roli aspoň jeden adept. Jaký je počet všech možných rozdělení vhodných pro tuto hru?

Řešení	Ukázat
Všech možných rozdělení je $3^8.$ Rozdělení, kdy není obsazena jedna role, je $3\cdot2^8.$ Rozdělení, kdy nejsou obsazeny dvě role, jsou $3.$ Podle PIE je počet vhodných rozdělení $3^8-3\cdot2^8+3.$

Příklad 311

Určete kolik existuje možností, jak rozdělit 20 zaměstnanců do tří dílen tak, aby byl splněn předpis, že v žádné dílně, pokud se v ní pracuje, nesmí nikdo pracovat sám.

Řešení	Ukázat
Všech možných rozdělení je $3^{20}.$ Rozdělení, kdy v jedné dílně je 1 člověk, je $3\cdot{20\choose1}\cdot2^{19}.$ Rozdělení, kdy ve dvou dílnách je vždy jen 1 člověk, je $3\cdot2\cdot{20\choose2}.$ Podle PIE je počet vhodných rozdělení $3^{20}-3\cdot{20\choose1}\cdot2^{19}+3\cdot2\cdot{20\choose2}.$

Příklad 312

Šestnáct chlapců máme rozdělit do dvou družstev po osmi. Kolika způsoby to můžeme udělat, jestliže Martin chce být s Petrem v jednom družstvu, Jirka s Tomášem v jednom družstvu a Honza nechce být v jednom družstvu s Karlem? Všichni chlapci mají různá jména.

Řešení	Ukázat
Máme dvě rozlišitelná družstva H (s Honzou) a K (s Karlem). Všech možných rozdělení do těchto družstev je ${14\choose7}.$ Rozdělení, kde Martin není s Petrem (A) je ${2\choose1}\cdot{12\choose6}$ a rozdělení, kde Jirka není s Tomášem (B) je také ${2\choose1}\cdot{12\choose6}.$ Rozdělení, kde Martin není s Petrem a současně Jirka není s Tomášem $(A\cap B)$ je ${2\choose1}\cdot{2\choose1}\cdot{10\choose5}.$ Podle PIE je počet rozdělení, která porušují aspoň jednu podmínku, je $\|A\cup B\|=\|A\|+\|B\|-\|A\cap B\|=2\cdot{12\choose6}+2\cdot{12\choose6}-4\cdot{10\choose5}=4\cdot{12\choose6}-4\cdot{10\choose5}.$ Počet správných rozdělení je pak ${14\choose7}-4\cdot{12\choose6}+4\cdot{10\choose5}.$

Řešení

Ukázat

Máme dvě rozlišitelná družstva H (s Honzou) a K (s Karlem). Všech možných rozdělení do těchto družstev je

${14\choose7}.$
Rozdělení, kde Martin není s Petrem (A) je

${2\choose1}\cdot{12\choose6}$ a rozdělení, kde Jirka není s Tomášem (B) je také

${2\choose1}\cdot{12\choose6}.$
Rozdělení, kde Martin není s Petrem a současně Jirka není s Tomášem

$(A\cap B)$ je

${2\choose1}\cdot{2\choose1}\cdot{10\choose5}.$
Podle PIE je počet rozdělení, která porušují aspoň jednu podmínku, je

$|A\cup B|=|A|+|B|-|A\cap B|=2\cdot{12\choose6}+2\cdot{12\choose6}-4\cdot{10\choose5}=4\cdot{12\choose6}-4\cdot{10\choose5}.$
Počet správných rozdělení je pak

${14\choose7}-4\cdot{12\choose6}+4\cdot{10\choose5}.$

Příklad 313

Kolika způsoby můžeme posadit do řady 3 Angličany, 3 Francouze a 3 Turky, tak aby žádní tři krajané neseděli vedla sebe?

Řešení	Ukázat
Označíme-li si $\|A\|$ počet rozesazení, v nichž jsou všichni Angličani vedle sebe (a analogicky $\|F\|$ a $\|T\|$ ), pak $\|A\|=\|F\|=\|T\|=7!\cdot3!$ $\|A\cap F\|=\|A\cap T\|=\|F\cap T\|=5!\cdot3!\cdot3!$ $\|A\cap F\cap T\|=3!\cdot3!\cdot3!\cdot3!$ Protože všech možných rozesazení je $9!,$ je podle PIE počet správných rozesazení $9!-[3\cdot7!\cdot3!-3\cdot5!\cdot(3!)^2+(3!)^4]$

Příklad 314

Kolika způsoby lze seřadit do fronty 5 Čechů, 4 Maďary a 3 Rusy tak, aby žádní příslušníci téhož národa netvořili jeden souvislý blok?

Řešení	Ukázat
Obdobně jako Příklad 313. A=Češi, B=Maďaři, C=Rusové (pohromadě). Všech uspořádání je $12!$ $\|A\|=8!\cdot5!,$ $\|B\|=9!\cdot4!,$ $\|C\|=10!\cdot3!$ $\|A\cap B\|=5!\cdot5!\cdot4!,$ $\|A\cap C\|=6!\cdot5!\cdot3!,$ $\|B\cap C\|=7!\cdot3!\cdot4!,$ $\|A\cap B\cap C\|=3!\cdot5!\cdot4!\cdot3!$ Podle PIE je správných uspořádání $12!-(8!\cdot5+9!\cdot4!+10!\cdot3!)+(5!\cdot5!\cdot4!+6!\cdot5!\cdot3!+7!\cdot3!\cdot4!)-3!\cdot5!\cdot4!\cdot3!$

Řešení

Ukázat

Obdobně jako Příklad 313. A=Češi, B=Maďaři, C=Rusové (pohromadě).
Všech uspořádání je

$12!$

$|A|=8!\cdot5!,$

$|B|=9!\cdot4!,$

$|C|=10!\cdot3!$

$|A\cap B|=5!\cdot5!\cdot4!,$

$|A\cap C|=6!\cdot5!\cdot3!,$

$|B\cap C|=7!\cdot3!\cdot4!,$

$|A\cap B\cap C|=3!\cdot5!\cdot4!\cdot3!$
Podle PIE je správných uspořádání

$12!-(8!\cdot5+9!\cdot4!+10!\cdot3!)+(5!\cdot5!\cdot4!+6!\cdot5!\cdot3!+7!\cdot3!\cdot4!)-3!\cdot5!\cdot4!\cdot3!$

Příklad 315

Určete, kolik je takových permutací 6-prvkové množiny $\{1, 2, 3, 4, 5, 6\},$ které nemají ani jeden prvek na stejném místě jako v základním uspořádání "123456".

Řešení	Ukázat
Určíme počet permutací, kdy je aspoň $k$ čísel na svém místě: vybereme oněch $k$ čísel, to lze ${6\choose k}$ způsoby. Zbylá čísla (je jich $6-k$ ) můžeme libovolně přerovnat. To lze $(6-k)!$ způsoby. Celkem tedy ${6\choose k}\cdot(6-k)!=\dfrac{6!}{k!}$ Podle PIE je počet permutací, v nichž je aspoň jedno číslo na svém místě, $\dfrac{6!}{1!}-\dfrac{6!}{2!}+\dfrac{6!}{3!}-\dfrac{6!}{4!}+\dfrac{6!}{5!}-\dfrac{6!}{6!}.$ Všech možných permutací je $6!,$ takže počet permutací, v nichž není žádné číslo na svém místě, je $6!-\left[\dfrac{6!}{1!}-\dfrac{6!}{2!}+\dfrac{6!}{3!}-\dfrac{6!}{4!}+\dfrac{6!}{5!}-\dfrac{6!}{6!}\right]$

Řešení

Ukázat

Určíme počet permutací, kdy je aspoň