kombinatorika

Příklad 457

Kolika způsoby můžeme na šachovnici $8\times8$ rozestavit pět nerozlišitelných věží tak, aby se neohrožovaly?

Řešení	Ukázat>
Vybereme sloupce, v nichž věže budou - ${8\choose5}$ . Pro první vybraný sloupec máme 8 možností, kam umístit věž, pro druhý vybraný sloupec máme jen 7 možností atd. Jedná se o variace $V_5(8).$ Celkem ${8\choose5}\cdot V_5(8).$ Zápis lze ještě upravit na $5!\cdot{8\choose5}^2$

Příklad 458

Kolika způsoby můžeme na šachovnici $8\times8$ rozestavit čtyři černé navzájem nerozlišitelné věže a čtyři bílé navzájem nerozlišitelné věže tak, aby žádná věž neohrožovala žádnou jinou?

Řešení	Ukázat>
Podle předcházející úlohy můžeme černé věže rozestavit $4!\cdot{8\choose4}^2$ způsoby. Na volné sloupce pak můžeme bílé rozestavit $4!$ způsoby. Celkem $\left(4!\cdot{8\choose4}\right)^2=(V_4(8))^2$ způsobů

Příklad 459

Kolik různých přirozených čísel může být vytvořeno jako součin dvou různých prvků množiny $\{1, 2, 3, 4, 5, 6\}?$

Řešení	Ukázat>
13

Příklad 460

Kolik 5-ticiferných čísel můžeme sestavit z číslic 1, 2, a 3, když každou musíme použít aspoň jednou?

Řešení	Ukázat>
Čísla jsou dvojího typu: a) jedna cifra je třikrát: $3\cdot\dfrac{5!}{3!}$ b) dvě cifry dvakrát: $3\cdot\dfrac{5!}{2!2!}$ Celkem $3\cdot\left[\dfrac{5!}{3!}+\dfrac{5!}{2!2!}\right]$

Příklad 461

Číslo PIN je čtyřciferné číslo, které nezačíná nulou. Kolik procent čísel PIN obsahuje aspoň jednu cifru 3?

Řešení	Ukázat>
Všech čtyřciferných čísel je $9\cdot10^3.$ Čtyřciferných čísel, která neobsahují číslo 3, je $8\cdot9^3$ Celkem $9\cdot10^3-8\cdot9^3$

Příklad 462

Na večírku bylo 7 žen a 5 mužů. Každý muž si na přivátanou potřásl rukou se všemi ostatními lidmi. Každá žena si potřásla rukou pouze s muži. Ke kolika potřesení rukou došlo na večírku?

Řešení	Ukázat>
Kdyby si podal ruku každý s každým, bylo by potřesení ${12\choose2}.$ Potřesení jenom mezi ženami je ${7\choose2}.$ Celkem ${12\choose2}-{7\choose2}.$

Příklad 463

Osm lidí, mezi nimi hostitelé Eva a Josef, sedí u kulatého stolu. Hostitelé nesedí vedle sebe a Eva sedí nejblíže ke kuchyni, aby mohla servírovat večeři. Kolika různými způsoby si mohou sednout?

Řešení	Ukázat>
Místo pro Evu je jednoznačně určené. Pak si Josef může sednou na 5 různých míst. Zbylí hosté si mohou sednout libovolně. Celkem $5\cdot6!$

Příklad 464

Kolik lichých trojciferných čísel má všechny cifry různé?

Řešení	Ukázat>
$5\cdot8^2$

Příklad 465

Čtverec $3\times 3$ je rozdělen na 9 jednotkových čtverců. Kolik existuje trojúhelníků s vrcholy ve vrcholech těchto čtverců?

Řešení	Ukázat>
Všech trojic bodů je ${16\choose3}.$ Ve čtverci jsou 4 svislé úsečky, 4 vodorovné a 2 dlouhé úhlopříčky. Na každé z těchto úseček jsou 4 body a trojice vybraná z těchto čtyř bodů nikdy netvoří trojúkelník. Musíme odečíst $10{4\choose3}.$ Dále jsou tam 4 kratší úhlopříčky a body na nich také netvoří trojúhelník a musíme je také odečíst. Celkem ${16\choose4}-10{4\choose3}-4$

Řešení

Ukázat>

Všech trojic bodů je

${16\choose3}.$
Ve čtverci jsou 4 svislé úsečky, 4 vodorovné a 2 dlouhé úhlopříčky. Na každé z těchto úseček jsou 4 body a trojice vybraná z těchto čtyř bodů nikdy netvoří trojúkelník. Musíme odečíst

$10{4\choose3}.$
Dále jsou tam 4 kratší úhlopříčky a body na nich také netvoří trojúhelník a musíme je také odečíst.
Celkem

${16\choose4}-10{4\choose3}-4$

Příklad 466

Kolik existuje přirozených dvojciferných čísel takových, že cifra na místě desítek je větší než cifra na místě jednotek?

Řešení	Ukázat>
Stačí vybrat libovolnou dvojici různých číslic. Z každého takového výběru sestavíme právě jedno číslo s požadovanou vlastností. ${10\choose2}$

Příklad 467

Kolika způsoby můžeme rozměnit dvacetikorunu, když máme k dispozici 2 desetikoruny, 4 pětikoruny a 20 korunových mincí?

Řešení	Ukázat>
Problém rozdělíme na tři případy podle počtu použitých desetikorun: (a) dvě desetikoruny -> jedna možnost (b) jedna desetikoruna -> musíme rozměnit už jen 10 korun. Počet způsobů je jednoznačně určen počtem použitých pětikorun -> tři možnosti (c) žádná desetikoruna -> musíme rozměnit 20 korun. Počet způsobů je jednoznačně určen počtem použitých pětikorun -> pět možnosti Celkem $1+3+5=9$ způsobů.

Řešení

Ukázat>

Problém rozdělíme na tři případy podle počtu použitých desetikorun:
(a) dvě desetikoruny -> jedna možnost
(b) jedna desetikoruna -> musíme rozměnit už jen 10 korun. Počet způsobů je jednoznačně určen počtem použitých pětikorun -> tři možnosti
(c) žádná desetikoruna -> musíme rozměnit 20 korun. Počet způsobů je jednoznačně určen počtem použitých pětikorun -> pět možnosti
Celkem

$1+3+5=9$ způsobů.

Příklad 468

V senátu USA je 100 členů, dva z každého státu. Kolika způsoby můžeme sestavit pětičlenný senátní výbor, když z žádného státu v něm nesmí být dva senátoři?

Řešení	Ukázat>
${50\choose5}\cdot2^5$

Příklad 459

Kolika způsoby můžeme přerovnat písmena ve výrazu "WYOMINGCOWBOYS"?

Řešení	Ukázat>
$\dfrac{14!}{2!2!3!}$

Příklad 470

Čtyři chlapci a tři dívky stojí v řadě. Pokud všichni chlapci musí stát vedle sebe, kolika způsoby se můžou postavit?

Řešení	Ukázat>
$4!\cdot4!$

Příklad 471

Ze skupiny devíti mužů a pěti žen vytváříme tým dvou mužů a čtyř žen. Jeden z mužů je Dan a jedna z žen je Lucie. Kolik existuje týmů, ve kterých jsou současně Dan i Lucie?

Řešení	Ukázat>
$8\cdot{4\choose3}$

Příklad 472

Kolik různých čtyřciferných čísel můžeme vytvořit přerovnáním číslic v čísle 1998?

Řešení	Ukázat>
$\dfrac{4!}{2!}$

Příklad 473

Na obrázku je 6 shodných kružnic s průměrem 1. Kolika způsoby se lze po obvodu kružnic dostat z bodu A do bodu B tak, aby cesta byla dlouhá $3\pi?$

Řešení	Ukázat>
$2^6$

Příklad 474

Je dáno 11 bodů podle obrázku. Kolik určují trojúhelníků?

Řešení	Ukázat>
Všech trojic je ${11\choose3}.$ Od nich musíme odečíst situace, kdy všechny tři body leží na přímce, tj. $2\cdot{5\choose3}+{4\choose3}.$ Celkem ${11\choose3}-2\cdot{5\choose3}-{4\choose3}$

Příklad 475

Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné, jejichž každá strana má velikost vyjádřenou jedním z čísel:
(a) 4, 5, 6, 7
(b) 1, 2, 8, 9

Řešení	Ukázat>
(a) strany trojúhelníka musí splňovat trojúhelníkovou nerovnost - ta je pro tato čísla vždy splněna. Strany tedy můžeme vybrat libovolně. Vybíráme trojici stran, strany se můžou opakovat a na jejich pořadí nezáleží - kombinace s opakováním: ${6\choose3}$ trojúhelníků. (b) V tomto případě není trojúhelníková nerovnost splněná pro situaci, kdy spojím dvě "malá" čísla (1,2) s některým "velkým" číslem (8,9). Dvě "malá" čísla můžu vybrat třemi způsoby a dvěma způsoby je můžu doplnit "velkým" číslem. Tj. $3\cdot2=6$ možností. Dále není nerovnost splněna pro strany 1-1-2 a 1-8-9. Celkem ${6\choose3}-8$ trojúhelníků.

Řešení

Ukázat>

(a) strany trojúhelníka musí splňovat trojúhelníkovou nerovnost - ta je pro tato čísla vždy splněna. Strany tedy můžeme vybrat libovolně. Vybíráme trojici stran, strany se můžou opakovat a na jejich pořadí nezáleží - kombinace s opakováním:

${6\choose3}$ trojúhelníků.
(b) V tomto případě není trojúhelníková nerovnost splněná pro situaci, kdy spojím dvě "malá" čísla (1,2) s některým "velkým" číslem (8,9). Dvě "malá" čísla můžu vybrat třemi způsoby a dvěma způsoby je můžu doplnit "velkým" číslem. Tj.

$3\cdot2=6$ možností. Dále není nerovnost splněna pro strany 1-1-2 a 1-8-9.
Celkem

${6\choose3}-8$ trojúhelníků.

Příklad 476

Máme skupinu 6 žen (2 učitelky, 2 soc. pracovnice, 2 doktorky) a skupinu 5 mužů (3 učitelé, 2 doktoři).
(a) Kolika způsoby z nich můžeme vybrat 6 lidí tak, aby aspoň 2 byli doktoři?
(b) Kolik různych skupin můžeme vytvořit takových, že v nich jsou 2 učitelé, 2 doktoři a 1 soc. pracovník?
(c) Kolik různych skupin můžeme vytvořit takových, že v nich jsou přesně 3 ženy a 2 muži a skladá se z aspoň 2 žen-doktorek a 1 muže-doktora?

Řešení	Ukázat>
a) ${4\choose2}{7\choose4}+{4\choose3}{7\choose3}+{4\choose4}{7\choose2}$ b) ${5\choose2}{4\choose2}{2\choose1}$ c) ${4\choose1}{2\choose1}{3\choose1}+{4\choose1}{2\choose2}$

Příklad 477

Na rovnoběžných přímkách $x$ a $y$ bylo nakresleno 6 bodů, 4 body na přímce $x$ a 2 body na přímce $y$ . Kolik trojúhelníků má všechny vrcholy v těchto bodech?

Řešení	Ukázat>
${4\choose2}\cdot{2\choose1}+{4\choose1}\cdot{2\choose2}$

Příklad 478

Každé dvě sousední číslice desetimístného čísla zapsaného číslicemi 1, 2 a 3 se liší o jedna. Kolik takových čísel existuje?

Řešení	Ukázat>
Řešení rozdělíme na dva případy: a) číslo začíná 1, nebo 3. Pak vždy musí následovat 2 a po ní opět 1, nebo 3 atd. Číslo bude vypadat _2_2_2_2_2, kde na volném místě máme vždy dvě možnosti, tj. celkem $2^5$ čísel. b) číslo začíná 2. Pak má tvar 2_2_2_2_2_. Opět celkem $2^5$ čísel. Celkem $2^5+2^5=2^6$ čísel.

Příklad 479

Jistý jazyk má 6 souhlásek {b, c, d, f, g, h} a 5 samohlásek {a, e, i, o, u}. Všechna slova tohoto jazyka jsou 11-ti písmenná.
V každém slově jsou použita všechna písmena a souhlásky a samohlásky se střídají. Kolik slov má tento jazyk?

Řešení	Ukázat>
$6!\cdot5!$

Příklad 480

Čtvercová zahrada je tvořena čtyřmi trojúhelníkovitými záhony tak, jak ukazuje obrázek. Zahradník chce osázet záhony květinami tak, aby každý záhon obsahoval jen jeden druh květin a květiny na záhonech se společnou stranou byly různé. Kolika způsoby může záhony osázet, když má k dispozici 5 druhů květin?

Řešení	Ukázat>
Řešení rozdělíme na dva případy: (a) Na severu i jihu je stejný druh květin. Ty můžeme vybrat pěti způsoby. Na západ pak můžeme vybrat květiny čtyř druhů a stejně tak na východ. Tj. $5\cdot4\cdot4=80$ možností. (b) Na severu a jihu jsou různé druhy. Ty můžeme vybrat $5\cdot4$ způsoby. Na západ i jih pak můžeme vždy vybrat ze tří druhů. Celkem $80+180=260$ možností.

Řešení

Ukázat>

Řešení rozdělíme na dva případy:
(a) Na severu i jihu je stejný druh květin. Ty můžeme vybrat pěti způsoby. Na západ pak můžeme vybrat květiny čtyř druhů a stejně tak na východ. Tj.

$5\cdot4\cdot4=80$ možností.
(b) Na severu a jihu jsou různé druhy. Ty můžeme vybrat

$5\cdot4$ způsoby. Na západ i jih pak můžeme vždy vybrat ze tří druhů.
Celkem

$80+180=260$ možností.

666 příkladů z kombinatoriky

Komplexní úlohy IV

Příklad 457

Příklad 458

Příklad 459

Příklad 460

Příklad 461

Příklad 462

Příklad 463

Příklad 464

Příklad 465

Příklad 466

Příklad 467

Příklad 468

Příklad 459

Příklad 470

Příklad 471

Příklad 472

Příklad 473

Příklad 474

Příklad 475

Příklad 476

Příklad 477

Příklad 478

Příklad 479

Příklad 480

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