Hledání chyb

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

Úloha č. 1

Následuje pět různých řešení té samé úlohy. Rozhodněte, je-li nějaké z nich správně a určete, v čem přesně jsou ostatní řešení špatně (např. která možnost je započítaná víckrát).

Úloha. Kolika způsoby lze rozdělit šest studentů do dvojic?

Řešení 1: Z šestice studentů vybereme dvojici. To lze $\binom{6}{2}$ způsoby. Ze zbylých čtyřech studentů vybereme další dvojici jedním z $\binom{4}{2}$ způsobů. Třetí dvojice je tím určena jednoznačně. To je celkem $\binom{6}{2} \cdot \binom{4}{2} = 90$ možností.

Řešení 2: Zkoušením zjistíme, že čtveřici studentů lze do dvojic rozdělit třemi způsoby. Nejprve tedy vybereme čtveřici studentů jedním ze $\binom{6}{4}$ způsobů a v rámci této čtveřice určíme rozdělení do dvojic jedním ze tří způsobů. Třetí dvojice je pak určena jednoznačně. Celkem je možností $\binom{6}{4}\cdot 3 = 45$ .

Řešení 3: Z šestice studentů vybereme trojici. To lze $\binom{6}{3} = 20$ způsoby. Ta nám určí trojici zbývajících studentů. Pak máme $3 \cdot 3$ možností, jak spárovat studenty z první trojice s těmi z trojice druhé. Výsledek je $20 \cdot 9 = 180$ .

Řešení 4: Studenty označíme písmeny A, B, C, D, E a F. Student A může být ve dvojici s kýmkoliv jiným, má tedy pět možností. Po určení první dvojice zbývají čtyři studenti. Vezmeme jednoho z nich a na výběr k němu do dvojice máme ze tří zbylých studentů. Do třetí dvojice dáme zbylé dva studenty. Možností je tedy $3 \cdot 5 = 15$ .

Řešení 5: Studenty seřadíme do řady jedním ze $6!$ způsobů. Do dvojic pak dáme prvního s druhým, třetího s čtvrtým a pátého s šestým. Každé rozdělení do dvojic získáme tímto více způsoby. Například dvojice $(1,2)$ , $(3,4)$ a $(5,6)$ získáme i z každé šestice, v níž tyto dvojice změní pořadí. (např. $(34)(12)(56)$ , $(12)(56)(34)$ , …). Dvojice jsou tři a tedy počet jejich pořadí je $3! = 6$ . Každé rozdělení do trojic jsme takto započetli šestkrát, takže dohromady je možností $6!/6 = 120$ .

Výsledek: (skrýt)

Správně je čtvrté řešení.

Výsledek

Řešení: (skrýt)

Ukážeme si, v čem jsou řešení 1,2,3,5 špatně. Ve všech řešeních budou studenti označeni A, B, C, D, E a F.

Uvažme rozdělení do dvojic (A,B), (C,D), (E, F). Toto rozdělení je v tomto výpočtu zahrnuto vícekrát. Pokud například nejprve vybereme dvojici (A,B) a pak dvojici (C,D), dospějeme k úplně stejnému rozdělení do dvojic jako tehdy, vybereme-li nejprve (E, F) a pak (A, B). Celkem tak toto rozdělení započítáme jednou za každé pořadí trojic (A,B), (C,D), (E, F), tedy $3! = 6$ -krát. Stejně tak započítáme šestkrát i každé jiné. Správný výsledek je $90/6 =15$ .
Uvažme rozdělení do dvojic (A,B), (C,D), (E, F). Započítáme jej v případě, kdy jakožto onu čtveřici vybereme (A, B, C, D) i tehdy kdy vybereme čtveřici (C, D, E, F), nebo čtveřici (E, F, A, B). Celkem toto rozdělení, jakož i každé jiné započítáme třikrát. Výsledek má být $45/3 = 15$ .
Předně na spárování trojic není $3\cdot 3 = 9$ možností, nýbrž $3!$ (například postupným výběrem). Nicméně ani pak není postup ani výsledek (120) v pořádku. V každé dvojici totiž máme jednoho studenta z vybrané trojice a jednoho z nevybrané. Například rozdělení (A,B), (C,D), (E, F) lze dosáhnout vybráním trojice (A, C, E) i vybráním trojic (B, D, F) či třeba (A, C, F).
Počet takových trojic je $2 \cdot 2 \cdot 2 = 8$ , neboť si třikrát vybíráme, koho z dvojice zařadíme do vybrané trojice. Toto rozdělení a stejně i každé jiné je tedy započteno 8-krát. Výsledek má být $120/8 = 15$ .
Například rozdělení do dvojic (A,B), (C,D), (E, F) je stále započteno vícekrát. Třeba z pořadí (BA)(CD)(EF), či (AB)(DC)(FE) atd. Takových pořadí je $2 \cdot 2 \cdot 2 = 8$ . Výsledek je tedy potřeba vydělit ještě osmi, a vyjde tak znovu 15.

Řešení

Úloha č. 2

Kolika způsoby lze 12 studentů rozdělit do tří čtyřčlenných týmů?

Výsledek: (skrýt)

$\binom{11}{3}\binom{7}{3} = \binom{12}{8}\binom{8}{4} / 3! = 5775$ .

Výsledek

Řešení: (skrýt)

Nabídneme dvě různá řešení, první bude založené na čtvrtém řešení předchozí úlohy a druhé na opraveném řešení prvním.

1) Jednoho studenta dáme stranou a jedním z $\binom{11}{3}$ způsoby mu vybereme spoluhráče. Ze zbývajících osmi opět dáme jednoho stranou a jedním ze $\binom{7}{3}$ mu vybereme spoluhráče. Třetí tým je tím určen, a výsledek tak je $\binom{11}{3}\binom{7}{3} = 5775$ .

2) Vybereme první tým jedním z $\binom{12}{4}$ způsobů a následně druhý tým jedním ze $\binom{8}{4}$ způsobů. Nyní jsme ovšem každé rozdělení do týmů započítali vícekrát, vždy jednou za každé pořadí, v němž jsme týmy vybrali. Každou trojici týmů jsme vybrali $3! = 6$ způsoby, a výsledek tak je $\binom{12}{8}\binom{8}{4} / 3! = 5775$

Řešení

Hodiny

Bonusy

Hledání chyb

Úloha č. 1

Úloha č. 2