kombinatorika

Příklad 415

Kolik způsoby lze vytvořit 6-ti ciferné číslo tak, aby bylo sudé a žádné cifry se v něm neopakovaly?

Řešení	Ukázat>
Rozdělíme na dva případy. (a) nula je na konci: $9\cdot8\cdot7\cdot6\cdot5\cdot1=15120$ možností. (b) ula není na na konci: $8\cdot8\cdot7\cdot6\cdot5\cdot4=53760$ možností. Celkem $68880$ čísel.

Příklad 416

Kolik čtyřciferných přirozených čísel lze vytvořit z číslic 0, 2, 5?

Řešení	Ukázat>
$2\cdot3^3$

Příklad 417

Tabulka na odpovědi u testu se skládá z 33 řádku (každý řádek odpovídá jedné otázce) s pěti čtverečky (každý odpovídá odpovědi). U každé otázky je potřeba vybrat jedno z pěti řešení, z nichž je právě jedno správné, a začernit odpovídající čtvereček. Některé otázky mohou zůstat bez odpovědi, ale není možné začernit více než jeden čtvereček v řádku. Za správnou odpěď je $20$ bodů, za špatnou $-5$ bodů a za neoznačené řešení $0$ bodů.
(a) Kolik obrazců takto může vzniknout?
(b) Kolik obrazců může vzniknout, když test byl ohodnocen 100 body?

Řešení	Ukázat>
(a) Na každém řádku je 6 nezávislých možností: $6^{33}$ obrazců. (b) Označíme $x$ počet správných odpovědí, $y$ počet špatných ospovědí ( $x,y\in\mathbb N_0$ ). Musí platit $\begin{cases}20x-5y=100\\x+y\leq33\\y\geq0\end{cases}\ \Rightarrow\ \begin{cases}y=4x-20\\5\leq x\leq10\end{cases}$ Řádky pro správnou odpověď můžeme vybrat ${33\choose x}$ způsoby. Řádky pro špatnou odpověď můžeme vybrat ${33-x\choose4x-20}$ a každý můžeme vyplnit čtyřmi způsoby. Celkový počet řešení je $\sum_{x=5}^{10}{33\choose x}\cdot{33-x\choose4x-20}\cdot4^{4x-20}$

Řešení

Ukázat>

(a) Na každém řádku je 6 nezávislých možností:

$6^{33}$ obrazců.
(b) Označíme

$x$ počet správných odpovědí,

$y$ počet špatných ospovědí (

$x,y\in\mathbb N_0$ ).
Musí platit

$\begin{cases}20x-5y=100\\x+y\leq33\\y\geq0\end{cases}\ \Rightarrow\ \begin{cases}y=4x-20\\5\leq x\leq10\end{cases}$

Řádky pro správnou odpověď můžeme vybrat

${33\choose x}$ způsoby.
Řádky pro špatnou odpověď můžeme vybrat

${33-x\choose4x-20}$ a každý můžeme vyplnit čtyřmi způsoby.
Celkový počet řešení je

$\sum_{x=5}^{10}{33\choose x}\cdot{33-x\choose4x-20}\cdot4^{4x-20}$

Příklad 418

Kolik existuje pětimístných přirozených čísel, která mají ve svem zápisu sudý počet sudých cifer?

Řešení	Ukázat>
Čísla rozdělíme na dvě disjunktní skupiny. (a) Na prvním místě je sudá cifra - 4 možnost. Ze zbývajících čtyř míst vybereme 1 nebo 3 místa pro sudou cifru - ${4\choose1}+{4\choose3}$ možností. Na každé volné místo můžeme nezávisle umístit jednu z pěti cifer. $4\cdot\left[{4\choose1}+{4\choose3}\right]\cdot5^4$ (b) Na prvním místě je lichá cifra - 5 možností. Ze zbývajících čtyř míst vybereme 0 nebo 2 nebo 4 místa pro sudou cifru - ${4\choose0}+{4\choose2}+{4\choose4}$ možností. Na každé volné místo můžeme nezávisle umístit jednu z pěti cifer. $5\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]\cdot5^4$ Celkem $4\cdot\left[{4\choose1}+{4\choose3}\right]\cdot5^4+5\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]\cdot5^4$ čísel.

Řešení

Ukázat>

Čísla rozdělíme na dvě disjunktní skupiny.
(a) Na prvním místě je sudá cifra - 4 možnost. Ze zbývajících čtyř míst vybereme 1 nebo 3 místa pro sudou cifru -

${4\choose1}+{4\choose3}$ možností. Na každé volné místo můžeme nezávisle umístit jednu z pěti cifer.

$4\cdot\left[{4\choose1}+{4\choose3}\right]\cdot5^4$
(b) Na prvním místě je lichá cifra - 5 možností. Ze zbývajících čtyř míst vybereme 0 nebo 2 nebo 4 místa pro sudou cifru -

${4\choose0}+{4\choose2}+{4\choose4}$ možností. Na každé volné místo můžeme nezávisle umístit jednu z pěti cifer.

$5\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]\cdot5^4$
Celkem

$4\cdot\left[{4\choose1}+{4\choose3}\right]\cdot5^4+5\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]\cdot5^4$

čísel.

Příklad 419

Kolik existuje přirozených šesticiferných čísel, v jejichž zápisu jsou právě tři číslice 3?

Řešení	Ukázat>
Čísla rozdělíme na dvě disjunktní skupiny. (a) Na prvním místě je trojka: Vybereme pozice pro zbylé dvě trojky a zbývající tři volná místa můžeme dát libovolnou cifru kromě trojky - ${5\choose2}\cdot9^3$ (b) Na prvním místě není trojka (a taky ne nula). Vybereme pozice pro trojky, vybereme první cifru a na zbývající dvě volná místa můžeme dát libovolnou cifru kromě trojky - ${5\choose3}\cdot8\cdot9^2$ Celkem ${5\choose2}\cdot9^3+{5\choose3}\cdot8\cdot9^2$ čísel.

Řešení

Ukázat>

Čísla rozdělíme na dvě disjunktní skupiny.
(a) Na prvním místě je trojka: Vybereme pozice pro zbylé dvě trojky a zbývající tři volná místa můžeme dát libovolnou cifru kromě trojky -

${5\choose2}\cdot9^3$
(b) Na prvním místě není trojka (a taky ne nula). Vybereme pozice pro trojky, vybereme první cifru a na zbývající dvě volná místa můžeme dát libovolnou cifru kromě trojky -

${5\choose3}\cdot8\cdot9^2$
Celkem

${5\choose2}\cdot9^3+{5\choose3}\cdot8\cdot9^2$

čísel.

Příklad 420

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>
čísla rozdělíme na disjunktní skupiny. 1. 7,2,0,0: $2\cdot3=6$ možností 2. 7,7,2,2: $\frac{4!}{2!2!}=6$ možností 3. 5,2,2,0 nebo 7,1,1,0: $3\cdot3=9$ možností 4. 5,2,1,1 nebo 7,5,5,1: $\frac{4!}{2!}=12$ možností Celkem $2(6+9+12)=54$ možností.

Příklad 421

$M$ je množina všech přirozených čísel menších než $50\,000,$ v jejichž dekadickém zápisu není žádná z číslic 0, 3, 4, 6, 8 a každá ze zbývajících je v něm nejvýše jednou. Určete počet sudých a lichých čísel v množině $M.$

Řešení	Ukázat>
Podle zadání máme k dispozici čísla 1, 2, 5, 7, 9. V množině $M$ je 1. $2\cdot4!$ pěticiferných čísel 2. $5!$ čtyřciferných čísel 3. $5\cdot4\cdot3$ trojciferných čísel 4. $5\cdot4$ dvouciferných čísel 5. $5$ jednociferných čísel. Celkem $48+120+60+20+5=253$ čísel. Sudých čísel je 1. $1$ jednociferné 2. $4$ dvouciferná 3. $4\cdot3$ trojciferná 4. $4\cdot3\cdot2$ čtyřciferná 5. $1\cdot3\cdot2\cdot1\cdot1$ pěticiferných Celkem $47$ sudých čísel a $253-47=206$ lichých čísel.

Řešení

Ukázat>

Podle zadání máme k dispozici čísla 1, 2, 5, 7, 9. V množině

$M$ je
1.

$2\cdot4!$ pěticiferných čísel
2.

$5!$ čtyřciferných čísel
3.

$5\cdot4\cdot3$ trojciferných čísel
4.

$5\cdot4$ dvouciferných čísel
5.

$5$ jednociferných čísel.
Celkem

$48+120+60+20+5=253$ čísel.
Sudých čísel je
1.

$1$ jednociferné
2.

$4$ dvouciferná
3.

$4\cdot3$ trojciferná
4.

$4\cdot3\cdot2$ čtyřciferná
5.

$1\cdot3\cdot2\cdot1\cdot1$ pěticiferných
Celkem

$47$ sudých čísel a

$253-47=206$ lichých čísel.

Příklad 422

Kolika způsoby můžeme napsat číslo $85$
(a) jako součet 10 kladných sčítanců?
(b) Pro jaký počet kladných sčítanců je počet různých způsobů největší? Předpokládáme, že rozlišujeme pořadí sčítanců.

Řešení	Ukázat>
(a) ${85-1\choose10-1}={84\choose9}$ (b) Je-li $k$ počet sčítanců, je počet způsobů ${84\choose k-1}$ . Každé takové číslo představuje jeden člen v řádku Pascalova trojúhelníku. V sudém řádku je lichý počet členů a největší je ten prostřední. Tj. $k=43$

Příklad 423

Najděte počet sudých čísel, která existují mezi čísly 10000 a 79999 a v nichž se žádná číslice neopakuje.

Řešení	Ukázat>
(a) Existuje $3\cdot8\cdot7\cdot6\cdot4$ čísel, která mají první cifru sudou. (b) Existuje $4\cdot8\cdot7\cdot6\cdot5$ čísel, která mají první cifru lichou. Celkem $10752$ čísel.

Příklad 424

Kolik různých deseticiferných čísel můřeme vytvořit z cifer $\{2, 3, 4, 5, 6, 8\},$ když
(a) se každá lichá cifra v čísle vyskytuje přesně 3 krát a každá sudá právě jednou?
(b) každá cifra je použita aspoň jednou a jsou seřazeny vzestupně?

Řešení	Ukázat>
(a) Vybereme nísta pro sudé cifry ${10\choose4}.$ Na vybraných místech je můžeme uspořádat $4!$ způsoby. Vybereme místa pro cifru $3$ ${6\choose3}$ způsoby. Místa pro cifru $5$ už jsou jednoznačně daná. Celkem ${10\choose4}\cdot{6\choose3}\cdot4!$ čísel. (b) analogie s příkladem 395. ${10-1\choose6-1}={9\choose5}$

Příklad 425

Kolik různých součtů může padnout při hodu třemi kostkami, kde jedna je 6stěnná, druhá 8stěnná a třetí 12stěnná? Každá kostka je normálně číslována celými čísly od 1 do počtu stěn.

Řešení	Ukázat>
Nejmenší součet je 3 a nejvyšší 26. Existuje 24 různých součtů.

Příklad 426

Kolik různých součtů lze hodit, pokud současně házíme jednou osmistěnnou a dvěma desetistěnnými kostkami?

Řešení	Ukázat>
Nejmenší součet je 3 a nejvyšší 28. Existuje 26 různých součtů.

Příklad 427

V tenisovém klubu se sešlo 6 hráčů. V kolika dvojicích si mohou zahrát dvouhru?

Řešení	Ukázat>
${6\choose2}=15$

Příklad 428

Na poličce je 12 různých knih. Vybereme z nich 5 takových, že žádné dvě na poličce nestály vedle sebe. Kolika působy to lze udělat?

Řešení	Ukázat>
Všech výběrů je ${12\choose5}$ aspoň 2 vedle sebe $11\cdot{10\choose3}$ aspoň 3 vedle sebe $10\cdot{9\choose2}$ aspoň 4 vedle sebe $9\cdot{8\choose1}$ aspoň 5 vedle sebe $8\cdot{7\choose0}$ Podle PIE je ${12\choose5}-11\cdot{10\choose3}+10\cdot{9\choose2}-9\cdot{8\choose1}+8\cdot{7\choose0}$ výběrů.

Příklad 429

Osm lidí s řidičskýıni průkazy jede na výlet. Na výběr mají 5 různých aut a do každého vejde všech osm lidí. Kolika způsoby mohou obsadit auta, pokud žádné auto nesmí zůstat prázdné?

Řešení	Ukázat>
Všech možností, jak obsadit 5 aut, je $5^8$ a můžeme to zapsat ${5\choose0}\cdot5^8.$ Počet možností, kdy je aspoň jedno auto prázdné, je ${5\choose1}\cdot4^8$ Počet možností, kdy jsou aspoň dvě auta prázdná, je ${5\choose2}\cdot3^8$ Počet možností, kdy jsou aspoň tři auta prázdná, je ${5\choose3}\cdot2^8$ Počet možností, kdy jsou aspoň čtyři auta prázdná, je ${5\choose4}\cdot1^8$ Celkem podle PIE ${5\choose0}\cdot5^8-{5\choose1}\cdot4^8+{5\choose2}\cdot3^8-{5\choose3}\cdot2^8+{5\choose4}\cdot1^8=\sum_{k=0}^5(-1)^k{5\choose k}\cdot(5-k)^8$

Řešení

Ukázat>

Všech možností, jak obsadit 5 aut, je

$5^8$ a můžeme to zapsat

${5\choose0}\cdot5^8.$
Počet možností, kdy je aspoň jedno auto prázdné, je

${5\choose1}\cdot4^8$
Počet možností, kdy jsou aspoň dvě auta prázdná, je

${5\choose2}\cdot3^8$
Počet možností, kdy jsou aspoň tři auta prázdná, je

${5\choose3}\cdot2^8$
Počet možností, kdy jsou aspoň čtyři auta prázdná, je

${5\choose4}\cdot1^8$
Celkem podle PIE

${5\choose0}\cdot5^8-{5\choose1}\cdot4^8+{5\choose2}\cdot3^8-{5\choose3}\cdot2^8+{5\choose4}\cdot1^8=\sum_{k=0}^5(-1)^k{5\choose k}\cdot(5-k)^8$

Příklad 430

Byli jsme tři, kouřili před školou a trápili se představou, že kouření může přinášet vážně zdravotní komplikace. Tu přistoupil vysílený muž a rozdal nám 5 různých reklamních letáčků tak, aby měl každý z nás alespoň jeden. Kolika způsoby to mohl provést? Pokud někdo dostal více letáků, tak nerozlišujeme pořadí, ve kterěm je dostal.

Řešení	Ukázat>
Stejné jako příklad 429. $\sum_{k=0}^3(-1)^k{3\choose k}\cdot(3-k)^5$

Příklad 431

Byli jsme čtyři, seděli v baru a popíjeli. Trápilo nás špatné svědomí, že místo abychom ve životě dělali něco pořádného, jsme závislí na alkoholu. Tu k nám přistoupil rozjařený barman a namíchal nám sedm různých drinků tak, aby každý dostal alespoň jeden. Kolika způsoby to mohl provést, jestliže rozlišujeme pořadí drinků, které jsme vypili.

Řešení	Ukázat>
Nápoje můžeme seřadit do řady $7!$ způsoby. Do mezer mezi nimi můžeme umístit tři "hranice" ${6\choose3}$ způsoby. Celkem $7!\cdot {6\choose3}$ způsobů.

Příklad 432

Janě zbylo od narozenin 6 různých čokoládových bonbónů. Chce si je rozdělit na čtyři po sobě jdoucí dny tak, aby každý den snědla alespoň jeden. Kolik má možností, jestliže rozlišujeme pořadí, ve kterém bonbóny sní?

Řešení	Ukázat>
Stejné jako příklad 431. Je $6!\cdot{5\choose3}$ způsobů.

Příklad 433

Ze slova ABRAKADABRA vybereme 5 písmen a z nich sestavíme nové slovo. Kolik takových slov můžeme vytvořit?

Řešení

Ukázat>

Typ 4+1 znamená 4 stejná písmena a 1 jiné.

typ	počet výběrů	počet uspořádání	celkem
5+0	$1$	$1$	1
4+1	$1\cdot4=4$	$\frac{5!}{4!}=5$	20
3+2	$1\cdot2=2$	$\frac{5!}{3!2!}=10$	20
3+1+1	$1\cdot{4\choose2}=6$	$\frac{5!}{3!}=20$	120
2+2+1	${3\choose2}\cdot3=9$	$\frac{5!}{2!2!}=30$	270
2+1+1+1	$3\cdot4=12$	$\frac{5!}{2!}=60$	720
1+1+1+1+1	$1$	$5!=120$	120

Celkem $1271$ slov.

Příklad 434

Ze slova MISSISSIPPI vybereme 5 písmen a z nich sestavíme nové slovo. Kolik takových slov můžeme vytvořit?

Řešení

Ukázat>

Stejný postup jako příklad 433.

typ	počet výběrů	počet uspořádání	celkem
4+1	$2\cdot3=6$	$\frac{5!}{4!}=5$	$30$
3+2	$2\cdot2=4$	$\frac{5!}{3!2!}=10$	$40$
3+1+1	$2\cdot3=6$	$\frac{5!}{3!}=20$	$120$
2+2+1	$3\cdot2=6$	$\frac{5!}{2!2!}=30$	$180$
2+1+1+1	$3$	$\frac{5!}{2!}=60$	$180$

Celkem 550 slov.

Příklad 435

Manžel má 12 známých, z toho 5 žen a 7 mužů. Manželka 7 žen a 5 mužů. Kolika způsoby můžeme sestavit skupinu 6 mužů a 6 žen tak, aby 6 osob znal manžel a 6 manželka? Předpokládáme, že manžel a manželka nemají společné známé.

Řešení	Ukázat>
Vyberu $k$ mužů ze známých manžela ( $k\in\{1..6\}$ ). To lze ${7\choose k}$ způsoby. Musím je doplnit muži $6-k$ , které zná manželka. To lze ${5\choose6-k}$ způsoby. Ženy, které zná manžel pak můžu vybrat ${5\choose6-k}$ způsoby a ženy, které zná manželka ${7\choose k}$ způsoby. Výběry jsou nezávislé a musíme je posčítat pro přípustná $k.$ Celkem $\sum_{k=1}^6{7\choose k}^2\cdot{5\choose6-k}^2$

Řešení

Ukázat>

Vyberu

$k$ mužů ze známých manžela (

$k\in\{1..6\}$ ). To lze

${7\choose k}$ způsoby.
Musím je doplnit muži

$6-k$ , které zná manželka. To lze

${5\choose6-k}$ způsoby.
Ženy, které zná manžel pak můžu vybrat

${5\choose6-k}$ způsoby a ženy, které zná manželka

${7\choose k}$ způsoby.
Výběry jsou nezávislé a musíme je posčítat pro přípustná

$k.$
Celkem

$\sum_{k=1}^6{7\choose k}^2\cdot{5\choose6-k}^2$

Příklad 436

Z deseti mužů, mezi nimiž je pan Novák, a z pěti žen, mezi nimiž je paní Nováková, se má vytvořit sedmičlenná skupina. Určete počet způsobů, jimiž to lze provést, jestliže v teto skupině
(a) má být paní Nováková a nemá být pan Novák.
(b) má být paní Nováková i pan Novák.
(c) mají být aspoň tři ženy.

Řešení	Ukázat>
(a) Ze skupiny odstraníme oba Novákovi, vybereme 6 lidí a vrátíme paní Novákovou: ${13\choose6}$ způsobů. (b) Ze skupiny odstraníme oba Novákovi, vybereme 5 lidí a vrátíme Novákovi: ${13\choose5}$ způsobů. (c) ${5\choose3}\cdot{10\choose4}+{5\choose4}\cdot{10\choose3}+{5\choose5}\cdot{10\choose2}$

666 příkladů z kombinatoriky

Komplexní úlohy II

Příklad 415

Příklad 416

Příklad 417

Příklad 418

Příklad 419

Příklad 420

Příklad 421

Příklad 422

Příklad 423

Příklad 424

Příklad 425

Příklad 426

Příklad 427

Příklad 428

Příklad 429

Příklad 430

Příklad 431

Příklad 432

Příklad 433

Příklad 434

Příklad 435

Příklad 436

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