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ň

$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]$

kombinatorika

666 příkladů z kombinatoriky

PIE

Příklad 301

Příklad 302

Příklad 303

Příklad 304

Příklad 305

Příklad 306

Příklad 307

Příklad 308

Příklad 309

Příklad 310

Příklad 311

Příklad 312

Příklad 313

Příklad 314

Příklad 315

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