Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:Booyabazooka

Kombinatorické myšlení

Kombinatorika trochu jinak

Kombinace s opakováním

diskuze, ke stažení v PDF: zadání

Úloha č. 1

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Následující úloha se skládá z několika podúloh. Rozdělte podúlohy do několika skupin (může to být i jen jediná skupina) tak, že všechny podúlohy v jedné skupině mají stejný výsledek. Výsledek podúloh v rámci skupiny není nutné určit a není podstatný. Hledejte důvody pro svá rozhodnutí. Skrýt.

(a) Eliška dostala za úkol koupit banány, pomeranče a broskve. Počty kusů si může zvolit sama (klidně nějaké nulové), dohromady jich ale má koupit přesně 15. Kolika způsoby to může udělat?
(b) Martin omylem dostal patnáct výtisků té samé učebnice a chce je uložit do tří šuplíků ve svém stole. Kolika způsoby může Martin učebnice mezi šuplíky rozdělit?
Pro kolik trojic nezáporných celých čísel $(a, b, c)$ platí $a+b+c = 15$ ? Trojice $(6,5,4)$ a $(5,4,6)$ považujeme za různé.
Pro kolik trojic kladných celých čísel $(x, y, z)$ platí $x+y+z = 18$ ?
(e) Jirka rozdělil čísla od 1 do 15 do tří skupin. Na svá oblíbená, svá neoblíbená a ta, na něž nemá názor. Kolik způsoby to mohl udělat?

Výsledek: (skrýt)

(a) = (b) = (c) = (d)

Výsledek

Řešení: (skrýt)

(a) $\Leftrightarrow$ (b) Eliška se rozhoduje, kolik koupí banánů, kolik pomerančů a kolik broskví. Martin se rozhoduje, kolik učebnic dá do 1. šuplíku, kolik do 2. a kolik do 3. šuplíku. V principu jde o totéž rozhodování, pouze se banán zaměnil za 1. šuplík, pomeranč za 2. šuplík a broskev za 3. šuplík.
Jednoznačnou korespondenci dostaneme, když počet učebnic v 1. šuplíku označíme písmenem $a$ , ve 2. šuplíku písmenem $b$ a ve 3. šuplíku písmenem $c$ .
Trojici $(a,b,c)$ přiřadímě trojici $(x,y,z)$ tak, že každé z čísel $a$ , $b$ , $c$ zvětšíme o $1$ . Tedy přesněji zvolíme $x=a+1$ , $y=b+1$ , $z=c+1$ , čímž zajistíme, že $x$ , $y$ , $z$ jsou kladná a jejich součet je $18$ . Naopak též každé trojici $(x,y,z)$ přiřadíme trojici $(a,b,c)$ tak, že každé čísel zmenšíme o $1$ . Tedy zcela analogicky $a=x-1$ , $b=y-1$ , $c=z-1$ , díky čemuž jsou čísla $a$ , $b$ , $c$ nezáporná a dávají součet $15$ .
(e) Jirkovo rozhodování je jiné. Když čísla rozdělí například takto:

jedná se o jiné rozdělení než

Přitom počty oblíbených a neoblíbených čísel, i čísel, na něž nemá názor, jsou v obou případech stejné. Jirka tedy může čísla rozdělit mnohem více způsoby než Martin, u kterého hraje nakonec roli jen to, kolik učebnic skončí ve kterém šuplíku.

Poznámka: Jirkovu úlohu bychom mohli i vyřešit, ale to není hlavním cílem. Jirka se u každého čísla rozhodne, zda bude jeho oblíbené, neoblíbené, nebo na něj nebude mít názor. Přiřazuje tedy číslům písmena $O$ (oblíbené), $N$ (neoblíbené) a $B$ (bez názoru). Například dříve zmíněným rozdělením by přiřadil posloupnosti písmen $(O, B, B, B, B, B, O, B, B, B, B, B, N, N),$ $(O, B, B, B, B, O, B, B, B, B, B, B, N, N).$ Takové přiřazení je vzájemně jednoznačné. Počet posloupností $15$ písmen se přitom snadno spočítá jako $3\cdot3\cdot3\dots3=3^{15}$ .

Řešení

Úloha č. 2

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

(a) Na kole štěstí lze vyhrát 50 různých sekaček na trávu. Zatočíme jím třikrát a odpovídající tři výhry si odvezeme domů. Kolika způsoby pro nás může účast u kola štěstí dopadnout? (Dva způsoby považujeme za různé, pokud jsme si domů dovezli různé sady sekaček.)
Kolika způsoby může skončit následující program? (Výstupem může být například $(5, 38, 38)$ nebo $(1, 7, 15)$ .)

$50$ závodníků vybrat trojčlenný tým?

(d) Pro kolik padesátic nezáporných celých čísel

$x_1$ ,

$x_2$ , …,

$x_{50}$ platí, že jejich součet je roven 3?

(e) Mezi padesát nemocnic je třeba rozdělit tři identické krabice s léky. Kolika způsoby to lze provést, je-li přípustné posílat více krabic do jedné nemocnice?

Výsledek: (skrýt)

(a) = (b) = (d) = (e)

Výsledek

Řešení: (skrýt)

Sekačky na kole štěstí očíslujeme čísly $1$ až $50$ . Pak tedy „vyhrajeme“ nějaká tři čísla, například $(38, 5, 38)$ . Jde nám jen o to, které sekačky si odvezeme domů (ne o to, v jakém pořadí jsme se vyhráli), takže do auta je můžeme nakládat například seřazené pěkně od nejmenšího čísla po největší. Tím například výhra $(38, 38, 5)$ bude do auta naložena stejně jako předchozí výhra $(38, 5, 38)$ . To je ale přesně ten samý proces, jaký provádí program.
(c) Výběr trojčlenného týmu závodníků se od výhry sekaček liší. V trojčlenném týmu jsou vždy tři různí závodníci, zatímco sekačky mohou být i stejné. Počet trojčlenných týmů je proto menší než počet výher u kola štěstí.
Sekačky opět očíslujeme čísly $1$ až $50$ . Počet sekaček číslo $1$ , které jsme vyhráli, označíme $x_1$ . Počet sekaček číslo $2$ , které jsme vyhráli, označíme $x_2$ , atd. Tím je každá výhra jednoznačně převedena na padesátici nezáporných čísel $x_1$ , $x_2$ , …, $x_{50}$ se součtem $3$ . Naopak též zadáním padesáti nezáporných čísel se součtem $3$ máme jednoznačně určeno, které sekačky a v jakém počtu jsme vyhráli.

(d)

$\Leftrightarrow$ (e) Počet krabic přidělených první nemocnici označíme

$x_1$ . Počet krabic přidělených druhé nemocnici označíme

$x_2$ , atd. Tím dostaneme padesátici nezáporných čísel

$x_1$ ,

$x_2$ , …,

$x_{50}$ , jejichž součet je

$3$ . Naopak i každá padesátice jednoznačně říká, kterým nemocnicím byly krabice přiděleny.

Řešení

Úloha č. 3

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

(a) Kolik existuje posloupností délky 10, v nichž je sedmkrát zastoupen čtvereček „$\square$“ a třikrát přepážka „$|$“?
(b) Kolika způsoby může skončit následující program?

$(a, b, c, d)$ platí

$a+b=c+d = 7$ ?

(d) Kolika způsoby může skončit následující program?

(e) V tašce s nafukovacími balónky je jich alespoň

$100$ od každé ze čtyř barev (modrá, červená, zelená a oranžová). Vybereme z ní sedm balónků. Kolika způsoby může výběr skončit?

Výsledek: (skrýt)

(a) = (b) = (d) = (e)

Výsledek

Řešení: (skrýt)

Výstupem programu je posloupnost délky $10$ , v níž je $7$ krát zastoupen znak $\square$ a $3$ krát zastoupen znak $|$ . Jde tedy pouze o to, zda program může skončit libovolnou takovou posloupností. K tomu potřebujeme pro danou posloupnost, např. $\square\square\square||\square\square|\square\square$ , vyrobit vhodný vstup programu. Písmenem $a$ označme počet čtverečků před 1. přepážkou (ve zde uvedeném příkladě $a=3$ ). Písmenem $b$ označme počet čtverečků mezi 1. a 2. přepážkou (zde $b=0$ ), písmenem $c$ počet čtverečků mezi 2. a 3. přepážkou (zde $c=2$ ) a konečně písmenem $d$ počet čtverečků za 3. přepážkou (zde $d=2$ ). Pro tento vstup je výstupem daná posloupnost znaků.
(c) Tato část je odlišná.
(b) $\Leftrightarrow$ (d) Výstupy obou programů lze na sebe převést. Nejdříve převedeme výstup programu z části (d) na výstup programu z části (b). Mezi skupiny barevných koleček dáme přepážky a poté všechna barevná kolečka změníme na čtverečky. Analogicky můžeme převést i výstup program z části (b) na výstup programu z části (d) (čtverečky nejdříve změníme na barevná kolečka a poté odstraníme přepážky).
Při výběru balónků zřejmě nakonec nezáleží na tom, v jakém pořadí jsme modré balónky vytáhli, ale pouze kolik jsme jich vytáhli. Jejich počet označíme $a$ . Podobně označíme počet červených $b$ , počet oranžových $c$ a počet zelených $d$ . Tím dostaneme jednoznačnou korespondenci mezi výběrem balónků a čtveřicí nezáporných celých čísel $(a,b,c,d)$ , pro kterou $a+b+c+d=7$ . Výběru si tak jednoznačně odpovídají se vstupem programu a už dříve jsme si rozmysleli, že vstup programu z části (b) si jednoznačně odpovídá s jeho výstupem.

Řešení

Úloha č. 4

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

(a) Kolika způsoby lze rozdělit 14 identických předmětů do čtyř šuplíků?
Kolik je posloupností délky 17 složených ze 14 symbolů $\square$ a tří symbolů $|$ ?
Kolik je posloupností délky 17 složených ze 14 symbolů $|$ a tří symbolů $\square$ ?
(d) Kolika způsoby lze rozdělit tři identické předměty do 14 šuplíků?
(e) Kolika způsoby lze rozdělit tři identické předměty do 15 šuplíků?

Výsledek: (skrýt)

(a) = (b) = (c) = (e)

Výsledek

Řešení: (skrýt)

Rozdělení předmětů do šuplíků zaznamenáme pomocí symbolů $\square$ (předmět) a $|$ (oddělovač). Počet $\square$ před 1. oddělovačem symbolizuje počet předmětů v 1. šuplíku. Počet $\square$ mezi 1. a 2. oddělovačem symbolizuje počet předmětů ve 2. šuplíku, atd. Rozdělení předmětů lze tedy zakódovat pomocí symbolů a naopak i z posloupnosti symbolů kóduje rozložení předmětů v šuplících.
Vzájemnou záměnou symbolů $\square$ a $|$ převedeme posloupnost z části (b) na posloupnost z části (c) a naopak.
Tato část je odlišná. Rozdělení předmětů do šuplíku budeme kódovat stejně jako v části (a). Na rozlišení $14$ šuplíků budeme potřebovat $13$ oddělovačů. Rozdělení předmětů lze tedy jednoznačně zakódovat pomocí posloupnosti $13$ symbolů $|$ a $3$ symbolů $\square$ .
Kódování rozdělení předmětů do šuplíků bude stejné jako v předchozích částech. Na rozlišení $15$ šuplíků potřebujeme $14$ oddělovačů $|$ a $3$ předměty zakódujeme pomocí $3$ symbolů $\square$ .

Řešení

Hodiny

Bonusy

Kombinace s opakováním

Úloha č. 1

Úloha č. 2

Úloha č. 3

Úloha č. 4