Drsná matematika Martin Panák, Jan Slovák Pokus o učebnici pro začínající studenty přírodních věd, informatiky apod., přibližující podstatnou část matematiky v rozsahu čtyř semestrálních přednášek. Text by měl být dokončen a vydán v roce 2013. i KAPITOLA 1 Přehršel různorodých úloh „hodnota, změna, 'poloha" - co to je a jak to uchopit? Smyslem první kapitoly této učebnice je uvést čtenáře do fascinujícího světa matematického myšlení, a to na co nejkonkrétnějších příkladech modelování reálných situací pomocí abstraktních objektů a souvislostí. Zároveň projdeme několik témat a postupů, ke kterým se postupně budeme vracet a v závěru kapitoly se budeme chvíli věnovat samotnému jazyku matematiky (se kterým do té doby budeme zacházet velmi intuitivně). O co jednodušší jsou východiska a objekty, se kterými zde budeme pracovat, 0 to složitější je pochopit do důsledku jemnosti použitých nástrojů a postupů. 1 to je důvod, proč se budeme k tématům postupně vracet. Pokud se tedy přecházení od tématu k tématu bude jevit z počátku jako chaotické, snad se to postupně spraví při návratech v pozdějších kapitolách. Začneme s tím nejjednodušším - obyčejnými čísly. 1. Čísla a funkce 1.1. Číselné obory. Všichni jsme jistě zvyklí počítat s přirozenými, celými, racionálními a reálnými čísly a máme také představy, jak jsou uspořádány do vztahů „menší-větší". Je také docela zřejmé, že mezi každými dvěmi celými čísly n a n + 1 je spousta racionálních čísel n < q < n +1. Jak jsou na tom ale čísla reálná? Potřebujeme je vůbec? I tady je patrně odpověď dobře známá: již řekové věděli, že předepíšeme-li plochu čtverce a2 = 2, pak nelze najít racionální a, které by předpisu vyhovovalo. Ověřit to můžeme za předpokladu, že známe následující vlastnost jednoznačného rozkladu přirozených čísel na prvočísla: Tvrzení. Každé přirozené čislo n lze jednoznačným způsobem vyjádřit jako součin mocnin n = pr11 • p22 • • -Pfcfc, kde všechna čísla pr,... , pk jsou dělitelná pouze sama sebou a jedničkou. Skutečně, pokud by platilo (p/q)2 = 2 pro přirozená čísla p a q, pak tedy p2 = 2q2. Na levé straně máme v rozkladu na prvočísla 2r se sudým r (případně r = 0), na pravé straně ale bude vždy mocnina dvojky lichá. To je spor s naším tvrzením a tedy předpoklad nemůže platit a žádné racionální číslo nemůže mít za svoji druhou mocninu dvojku. Vidíme tedy, že již hledání odmocnin nás nutí k rozšíření racionálních čísel na reálná. Dokonce snadno ukážeme 1.2. Nechť t a m jsou kladná celá čísla. Ukažte, že číslo \/t je buď přirozené, nebo není racionální. 1 2 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH pi.2 pi.3 Řešení. Nechť uvažovaná odmocnina není přirozená. Ukážeme, že potom není ani racionální. Protože předpokládáme, že \/í není přirozená, tak existuje prvočíslo r a přirozené s taková, že rs dělí t, rs+1t a mt. Jako v předchozím případě předpokládejme nyní, že by existovala přirozená p, q tak, že \/í = p. Vynásobením rovnice číslem q a umocněním na číslo m dostáváme t • pm = qm. Nyní však největší přirozené u takové, že ru dělí levou stranu rovnice není násobkem m, kdežto protože pravá strana je m-tou mocninou, tak by u mělo být dělitelné m, což není možné. Náš předpoklad tedy neplatí a číslo \/í nemůže být racionální, pokud není přirozené. □ Trochu více si o reálných číslech řekneme později. 1.3. Komplexní čísla. Stačí nám aspoň pro elementární počty reálná čísla? Je lehké si uvědomit, že nikoliv: Úvahu o racionalitě druhé odmocniny v minulém odstavci můžeme formulovat jako dotaz na existenci řešení rovnice x2 = 2 v oboru racionáních čísel. Ověřili jsme, že řešení nemá, v oboru reálných čísel už ale ano. Co když napíšeme obecněji x2 = b a ptáme se pořešení tecf? Tato rovnice má vždy řešení x v oboru reálných čísel, pokud je b kladné. Jestliže je b = —1, pak ale zjevně takové reálné x existovat nemůže. Podbízí se „přidat" k reálným číslům nové číslo i, tzv. imaginární jednotku a zkusit dát dohromady rozšíření číselného oboru R reálných čísel tak, aby byly splněny všechny vlastnosti, které od skalárů očekáváme. Kupodivu to skutečně jde tím nejjednodušším způsobem: jistě budeme chtít umět nové číslo i násobit reálnými čísly a budeme chtít umět přičítat i skutečná reálná čísla. Nutně proto musíme v novém číselném oboru komplexních čísel C pracovat s formálními výrazy z = a + i b. Reálnému číslu a říkáme reálná složka komplexního číla z, číslu b pak imaginární složka. Aby byly splněny vlatnosti asociativity a distributivity, zavedeme sčítání tak, že se nezávisle sčítají reálné složky a imaginární složky a násobení tak, jak by se násobily dvojčleny reálných čísel s jediným dodatečným pravidlem i2 = —1, tj. (1.1) (a + ib) + (c + id) = (a + c) + i (b + d) (1.2) (a + i b) • (c + i d) = (ac — bd) + i (bc + ad) Ověřte si pečlivě, že skutečně platí všechny vlastnosti KG1-4, O1-4 a P skalárů, jde tedy o pole (komutativní těleso) skalárů. Nulou je samozřejmě číslo 0 + i 0, jedničkou číslo 1 + i 0, které opět píšeme jako 0 a 1. 1.4. Komplexní čísla jako body v rovině. Tak jak si jistě představujeme reálná čísla jako body přímky všech reálných čísel, můžeme si dobře představit komplexní čísla z = a + i b jako body v rovně o souřadnicích (a, b). Imaginární jednotka i pak odpovídá bodu (0,1) a všimněme si, že vynásobení jakéhokoliv čísla z = a + i b imaginární jednotkou dává výsledek i • (a + i b) = —b + i a tj. v interpertaci v rovině jde o otočení bodu z o pravý úhel proti směru hodinových ručiček. Další geometrická operace, která má jednoduché vyjádření je 1. ClSLA A FUNKCE 3 symetrie podle osy reálných čísel: z = (a + i b) — (a — i b) = z. Hovoříme o číslu ž komplexně sdruženém k z. Všimněme si dále, že součin zž = (a2 + b2) + i (—ab + ba) = a2 + b2 je vždy reálné číslo a dává nám kvadrát vzdálenosti čísla z od počátku 0. Platí tedy | z |2 = zž. Komplexní čísla tvaru z = cos y>+i sin y>, kde y> je reálný parametr udávající úhel mezi reálnou přímkou a spojnicí z s počátkem, popisují právě všechny body na jednotkové kružnici v komplexní rovině. Každé nenulové číslo z pak lze právě jedním způsobem napsat jako z = |z|(cos y> + i sin y>). Tento výraz nazýváme goniometrický tvar komplexního čísla z. Standardní vzorce pro goniometrické funkce pak jsou ekvivalentní tvrzení Tvrzení (Moivrova věta). zi • z2 = |zi||z2|(cos(y>i + y>2) + i sin(y>i + <£>2), kde 2) následující rekurentní formuli (navíc předpokládáme, že každý měsíc je přesně dvanáctina roku) x„+1 = 1, 03(x„) + 36000 + 1500 + 0,03 • 3000 ( 1 + 11 + ••• + ^ ) + 1 úroky z vkladů za aktuální rok + 0,03 • 2 • 1500 = v-3-' úrok ze státního příspěvku připsaného v aktuálním roce = 1, 03(xn) +38115 Tedy n-2 xn = 38115 ^(1, 03)ž + (1,03)n-1xi + 1500, i=0 přičemž x1 = 36000 + 3000 (1 + 12 +-----h ^) = 36585, celkem 12J x5 = 38115 í(1, <03)03- M + (1,03)4 • 36585 + 1500 = 202136. 0, 03 □ 10 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH fib fib 1.2. Poznámka. Ve skutečnosti úročení probíhá podle počtu dní, které jsou peníze na účtu. Obstarejte si skutečný výpis ze stavebního spoření, zjistěte si jeho úročení a zkuste si spočítat připsané úroky za rok. Porovnejte je se skutečně připsanou sumou. Počítejte tak dlouho, dokud sumy nebudou souhlasit 1.24. Určete posloupnost {yn}™=i, která vyhovuje následuje následujícímu rekurentnímu vztahu 3 Vn+1 = ^ Vn + 1, n > 1, í/1 = 1. Řešení. yn = 2(3)n - 2. □ (1) , Ukážeme „populační model", který je příkladem na rekurentní rovnici druhého řádu: | j. | 1.25. Fibonacciho posloupnost. Na začátku jara přinesl čáp na louku dva čerstvě narozené zajíčky, samečka a samičku. Samička je schopná od dvou měsíců stáří povít každý měsíc dva malé zajíčky (samečka a samičku). Nově narození zajíci splodí potomky po jednom měsíci a pak každý další měsíc. Každá samička je březí jeden měsíc a pak opět porodí samečka a samičku. Kolik párů zajíců bude na louce po devíti měsících (pokud žádný neumře a žádný se tam „nepřistěhuje")? Řešení. Po uplynutí prvního měsíce je na louce pořád jeden pár, nicméně samička otěhotní. Po dvou měsích se narodí první potomci, takze na louce budou dva páry. Po uplynutí každého dalšího měsíce se narodí (tedy přibude) tolik zajíců, kolik otěhotnělo zaječic před měsícem, což je přesně tolik, kolik bylo před měsícem párů schopných splodit potomka, což je přesně tolik, kolik bylo párů před dvěma měsíci. Celkový počet pn zajíců po uplynutí n-tého měsíce tak je tak součtem počtů párů v předchozích dvou měsících. Pro počet párů zajíců na louce tedy dostáváme homogenní lineární rekuretní formuli (1.8) Pn+2 = Pn+1 + Pn, n =1,..., která spolu s počátečními podmínkami p1 = 1 a p2 = 1 jednoznačně určuje počty párů zajíců na louce v jednotlivých měsících. Linearita formule znamená, že všechny členy posloupnosti (Pn) jsou ve vztahu v první mocnině, rekurence je snad jasná a homogenita značí, že v předpisu chybí absolutní člen (viz dále pro nehomogenní formule). Pro hodnotu n-tého členu můžeme odvodit explicitní formuli. V hledaní formule nám pomůže pozorování, že pro jistá r je funkce rn řešením rekurentní formule bez počátečních podmínek. Tato r získáme prostě tak, že dosadíme do rekurentního vztahu: (1.9) rn+2 = rn+1 + rn a po vydělení rn dostaneme (1.10) r2 = r +1, což je tzv. charakteristická rovnice daného rekurentního vztahu. Naše rovnice má kořeny 1—^5 a 1+2^5 a tedy posloupnosti an = (i-^5)n a bn = (1+2^5)n, n > 1 vyhovují danému vztahu. Zřejmě také jejich libovolná lineární kombinace cn = san + tbn, s,t G R. čísla s a t můžeme zvolit tak, aby výsledná kombinace splňovala dané počáteční podmínky, v našem případě c1 = 1, c2 = 1. Pro jednoduchost je vhodné navíc ještě dodefinovat nultý člen posloupnosti jako 3. DIFERENČNÍ ROVNICE 11 c0 = 0 a spočítat s a t z rovnic pro c0 a c1. Zjistíme, že s = — , t = a tedy (1.11) Pn =(1 + —— . Takto zadaná posloupnost splňuje danou rekurentní formuli a navíc počáteční podmínky co =0, c1 = 1, jedná se tedy o tu jedinou posloupnost, která je těmito požadavky jednoznačně zadána. □ 3. I 1.26. Zjednodušený model chování národního produktu (1.12) ž/fc+2 — a(1 + b)yk+i + abyk = 1, kde yk je národní produkt v roce k, konstanta a je takzvaný mezní sklon ke spotřebě, což je makroekonomický ukazatel, který udává jaký zlomek peněz, které mají obyvatelé k dispozici, utratí a konstanta b popisuje jak závisí míra investic soukromého sektoru na mezním sklonu ke spotřebě. Předpokládáme dále, že velikost národního produktu je normována tak, aby na pravé straně rovnice vyšlo číslo 1. Spočítejte konkrétní hodnoty pro a = 3, b = 1, y0 = 1, y1 = 1. Řešení. Nejprve budeme hledat řešení homogenní rovnice (pravá strana nulová) ve tvaru rk. Číslo r musí být řešením charakteristické rovnice x2 — a(1 + b)x + ab = 0, tj. x2 — x + ^ = 0, která má dvojnásobný kořen 2. Všechna řešení homogenní rovnice jsou potom tvaru a(2)n + bn(1 n). Dále si všimněme, že najdeme-li nějaké řešení nehomogenní rovnice (tzv. partikulární řešení), tak pokud k němu přičteme libovolné řešení homogenní rovnice, obdržíme jiné řešení nehomogenní rovnice. Lze ukázat, že takto získáme všechna řešení nehomogenní rovnice. V našem případě (tj. pokud jsou všechny koeficienty i nehommogenní člen konstantami) je partikulárním řešením konstanta yn = c, dosazením do rovnice máme c — c + 1 c =1, tedy c = 4. Všechna řešení diferenční rovnice yk+2 — yk+1 + 4 yk = 1 jsou tedy tvaru 4 + a(1 )n + bn(2)n. Požadujeme y0 = y1 = 1 a tyto dvě rovnice dávají a = b = —3, tedy řešení naší nehomogenní rovnice je Opět, protože víme, že posloupnost zadaná touto formulí splňuje danou diferenční rovnici a zároveň dané počáteční podmínky, jedná se vskutku o tu jedinou posloupnost, která je těmito vlastnostmi charakterizována. □ V předchozím příkladu jsme použili tzv. metodu neurčitých koeficientů. Ta spočívá v tom, že na základě nehomogenního členu danéneho diferenční rovnice „uhodneme" tvar partikulárního řešení. Tvary partikulárních řešení jsou známy pro celou řadu nehomogenních členů. Např. rovnice (1.13) y„+k + a!y„+k-1 +-----+ a,k yn = Pm(n), 12 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH s reálnými kořeny charakteristické rovnice má partikulární řešení tvaru Qm(n), kde Pm(n) a Qm(n) jsou polynomy stupně m. Další možnou metodou řešení je tzv. variace konstant, kdy nejprve najdeme řešení y(n) = E cifi(n) zhomogenizované rovnice a po té uvažujeme konstanty cj jako funkce Cj(n) proměnné n a hledáme partikulární řešení dané rovnice ve tvaru y(n) = E ci(n)fj(n). Ukažme si na obrázku hodnoty fj pro i < 35 a rovnicí f (n) = 8 f (n — 1) — 4 f (n — 2) + 1, f (0) = f (1) = 1 0,95j 0,9- 0,85j 0 5 10 15 20 25 30 35 Rekurentní vtahy se mohou vyskytnout i v geometrických problémech: 1.27. Na kolik nejvýše oblastí může dělit rovinu n přímek? Řešení. Označme hledaný počet oblastí pn. Pokud v rovině nemáme dánu žádnou přímku, je celá rovina jedinou oblastí, je tedy p0 = 1. Pokud je v rovině dáno n přímek, tak přidáním n +1 přibude nejvýše (n + 1) oblastí: oblastí přibude právě tolik, kolika (původními) oblastmi bude přímka procházet (každou takovou oblast rozdělí na dvě části, jedna oblast tedy přibude). (n+1). přímka může mít nejvýše n různých průsečíků s n přímkami, které už v rovnině byly. Část přímky mezi libovolnými dvěma sousedními průsečíky prochází právě jednou oblastí, celkem může přidaná přímka procházet nejvýše n + 1 oblastmi, tedy může přibýt maximálně n + 1 oblastí, navíc v rovině bylo před přidáním (n + 1). přímky nejvýše pn oblastí (tak jsme číslo pn totiž definovali). 3. DIFERENČNÍ ROVNICE 13 Celkem dostáváme rekurentní vztah Pn+1 = Pn + (n + 1), ze kterého získáme explicitní formuli pro pn buď pomocí vzorce ?? nebo přímo: Pn = Pn-1 + n = Pn-2 + (n - 1) + n = Pn-3 + (n - 2) + (n - 1) + n = n •••=po + 1 = = 1+ n(n + 1) 2 = n2 + n + 2 = 2 □ 1.28. Na kolik nejvýše částí dělí třírozměrný prostor n rovin? Řešení. Označme hledaný počet rn. Vidíme, že r0 = 0. Podobně jako v předchozím příkladu uvažujme, že máme v prostoru n rovin, přidejme jednu další a ptejme se, kolik nejvýše částí prostoru mě přibude. Opět to bude přesně tolik, kolika původními částmi prostoru přidaná rovina prochází. Kolik to může být? Počet částí prostoru, kterými (n + 1). rovina prochází je roven počtu částí, na které je přidaná (n + 1). rovina rozdělena průsečnicemi s n rovinami, které v prostoru již byly rozmístěny. Těchto částí však může být podle předchozího příkladu nejvýše 1/2 • (n2 + n + 2), dostáváme tak rekurentní formuli n2 + n + 2 rn+1 = rn + 2-. 14 Danou rovnici opět 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH můžeme vyřešit přímo: (n — 1)2 + (n — 1)+2 n2 — n + 2 rn = rn-1 +--2- = rn-1 +--2- = (n — 1)2 — (n — 1)+2 n2 — n + 2 = rn-2 + ~-—2-— + —^~ = = rn-2 + + 21)2 — n — ^ + 1 + 1 = = n2 (n — 1)2 (n — 3)2 n (n — 1) (n — 2) = rn-3 + Y+ 2 + 2 2 2 2~ + +1 + 1 + 1 = 1 n 1 n n = - = ro + 2Ei2 — äE i + n(n + 1)(2n + 1) n(n + 1) = 1 + —--------- + n = 12 4 n3 + 6n + 5 = 6 , kde jsme použili známého vztahu i2 n(n + 1)(2n + 1) 6 který lze snadno dokázat matematickou indukcí. □ 1.29. Na kolik maximálně částí dělí rovinu k kružnic? Řešení. Pro maximální počet pk oblastí, na které dělí rovinu kružnice odvodíme rekurentní vzorec Pk+1 = Pk + 2k Všimněme si totiž, že (k + 1). kružnice protíná k předchozích maximálně v 2k průsečících (a tato situace skutečně může nastat). 3. DIFERENČNÍ ROVNICE 15 Navíc zřejmě p1 = 1. Pro počet pk tedy dostáváme k-1 Pk = Pk-1 +2(k -1) = pk2 +2(k - 2) + 2(k -1) = ••• = p1 + ^2i = 2 + (k - i=1 □ 1.30. Na kolik maximálně částí dělí trojrozměrný prostor n koulí? Řešení. Maximální počet yn částí, na které rozdělí n kružnic rovinu je yn = yn-i + 2(n - 1), yi = 2, tedy yn = n2 - n + 2. Pro maximální počet pn částí, na které potom rozdělí n koulí prostor pak dostáváme rekurentní vztah pn+1 = pn + yn, p1 = 2, tedy celkem pn = n (n2 — 3n + 8). □ 1.31. Na kolik částí dělí prostor n navzájem různých rovin, které všechny prochází jedním daným bodem? Řešení. Pro hledaný počet xn odvodíme rekurentní formuli dále x1 = 2, tedy Xn = Xn-1 + 2(n - 1), xn = n(n - 1) + 2. □ Dále si procvičme, jak řešit lineární diferenční rovnice 2.řádu s konstantními koeficienty. Posloupnost vyhovující dané rekurentní rovnici 2.řádu je dána jednoznačně, pokud zadáme navíc nějaké dva její sousední členy. Znovu si povšimněme dalšího využití komplexních čísel: pro určení explicitního vzorce pro n-tý člen posloupnosti reálných čísel můžeme potřebovat výpočty s čísly komplexními (totiž pokud má charakteristický polynom dané diferenční rovnice komplexní kořeny). 16 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH 1.32. Nalezněte explicitní vzorec pro posloupnost vyhovující následující lineární diferenční rovnici s počátečními podmínkami: X„+2 = 2x„ + n, #1 = 2, X2 = 2. Řešení. Zhomogenizovaná rovnice je xn+2 2xn . Její charakteristický polynom je x2 — 2, jeho kořeny jsou ±\/2. Řešení zhomogenizovaná rovnice je tedy tvaru a(V2)n + 6(—V2)n, pro libovolná a, b G R Partikulární řešení budeme hledat metodou neurčitých koeficientů. Nehomogenní část daná rovnice je lineární polynom n, partikulární řešení proto budeme nejprve hledat ve tvaru lineárního polynomu v proměnná n, tedy kn +1, kde k, 1 G R. Dosazením do původní rovnice dostáváme k(n + 2) + 1 = 2(kn + 1) + n. Porovnáním koeficientů u proměnná n na obou stranách rovnice dostáváme vztah k = 2k +1, tedy k = —1, porovnáním absolutních členů pak vztah 2k +1 = 21, tedy 1 = —2. Celkem partikulárním řešením je posloupnost —n — 2. Řešení daná nehomogenní diferenční rovnice druháho řádu bez počátečních podmínek jsou tedy tvaru a(\/2)n + b(—\/2)n — n — 2, a, b G R. Nyní dosazením do počátečních podmínek určíme neznámá a, b G R. Pro početní jednoduchost použijeme maláho triku: z počátečních podmínek a da-náho rekurentního vztahu vypočteme člen x0 : x0 = 1 (x2 — 0) = 1. Daný rekurentní vztah spolu s podmínkami x0 = 1 a x1 = 1 pak zřejmě splňuje tatáž posloupnost, která splňuje původní počáteční podmínky. Máme tedy následující vztahy pro a, b: x0 : a(a/2)0 + b(—a/2)0 — 2 = 1, tedy a + b = 3 x1 : a/2a — a/2b = 4, jejichž řešením dostáváme a = 6+^^, b = 6-^^2. Řešením je posloupnost xn = 6±^(V2)n + 6—i^(—,/2)" — n — 2. □ 1.33. Určete reálnou bázi prostoru řešení homogenní diferenční rovnice xn+4 xn+3 + xn+1 xn, Řešení. Charakteristický polynom daná rovnice je x4 — x3 — x +1. Hledáme-li jeho kořeny, řešíme reciprokou rovnici x4 — x3 — x + 1 = 0 Standardním postupem nejprve vydělíme rovnici výrazem x2 a potá zavedeme substituci t = x + X, tedy t2 = x2 + X? +2. Obdržíme rovnici t2 — t — 2 = 0, 3. DIFERENČNÍ ROVNICE 17 s kořeny t1 = —1, t2 = 2. Pro obě tyto hodnoty neznámé t pak řešíme zvlášť rovnici danou substitučním vztahem: x + - = —1. x Ta má dva komplexní kořeny x1 = —1 + ii/5 = cos(120°) + isin(120°) a x2 = —1 — Ía/3 = cos(120°) — i sin(120°). Pro druhou hodnotu neznámé t dostáváme rovnici x + 1 = 2 x s dvojnásobným kořenem 1. Celkem je tedy bazí hledaného vektorového prostoru posloupností, které jsou řešením dané diferenční rovnice následující čtveřice posloupností: {—2 + ^v/3}^<=1, { —1 — ^v/3}^L1,{1}^;L1 (konstantní posloupnost) a {n}JJL1. Hledáme-li však reálnou bazi, musíme nahradit dva generátory (posloupnosti) z této báze s komplexními hodnotami generátory reálnými. Protože tyto generátory jsou geometrické řady, jejichž libovolné členy jsou komplexně sdružená čísla, můžeme vzít jako vhodné generátory posloupnosti dané polovinou součtu, resp. polovinou i-násobku rozdílu, daných komplexních generátorů. Takto dostaneme následující reálnou bázi řešení: (konstantní posloupnost), {n}~=1, {cos(n • 120°)}£°=1, {sin(n • 120°)}£°=1. □ 1.34. Kolik existuje slov délky 12 složených pouze z písmen A a B, které neobsahují skupinu BBB? Řešení. Nechť an značí počet slov délky n složených pouze z písmen A, B, neobsahujících skupinu BBB. Pak pro an (n > 3) platí rekurentní vztah an = an-1 + an-2 + an-3, neboť slova délky n splňující danou podmínku musí končit buď na A, nebo na AB, nebo na ABB. Slov končících na A je právě an-1 (před posledním A může být libovolné slovo délky n — 1 splňující danou podmínku. Obdobně pro zbylé dvě skupiny. Dále snadno vyčíslíme a1 = 2, a2 = 4, a3 = 7. Postupným dopočítáním a12 = 1705. Též bychom mohli odvodit explicitní vzorec pro n-tý člen takto zadané posloupnosti, dle uvedené teorie. Charakteristický polynom dané rekurentní rovnice je x4 — 2x3 — 1 = (x — 1)(x3 — x2 — x — 1) s jedním z kořenů 1, ještě jedním reálným a dalšími dvěma komplexními kořeny, které můžeme vyjádřit pomocí vztahů 1. □ 1.35. Skóre basketbalového utkání mezi týmy Česka a Ruska vyznělo po první čtvtině 12 : 9 pro ruský tým. Kolika způsoby se mohlo vyvíjet skóre? Řešení. Označíme-li P(k,i) počet způsobů, kterými se mohlo vyvíjet skóre basketbalového utkání, které skončilo k : l, tak pro k, l < 3 platí rekurentní vztah: P(k,l) = P(fc-3,í) + P(fc-2,í) + P(fc-1,í) + P(fc,í-1) + P(fc,í-2) + P(fc,í-3). (Způsoby, kterými se mohlo vyvýjet utkání s výsledným skóre k : l rozdělíme na šest po dvou disjunktních podmnožin podle toho, které družstvo vstřelilo 18 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH koš a za kolik bodů (1, 2, či 3).) Ze symetrie úlohy zřejmě platí P(k,i) = P(í,fc). Dále pro k > 3 platí: P(fc,2) = P(fc-3,2) + P(fc-2,2) + P(fc-1,2) + P(fc,1) + P(fc,1) = P(fc-3,1) + P(fc-2,1) + P(fc-1,1) + P(fc,0) = P(fc-3,0) + P(fc-2,0) + ^-1^ což spolu s počátečními podmínkami P(0j0) = 1, P(1j0) = 1, P(2,o) = 2, P(3,0) = 4, P(1,1) = 2, P(2,1) = P(1,1) + P(0,1) + P(2,0) = 5, P(2,2) = P(0,2) + P(1,2) + P(2,1) + P(2,0) = 14, dává P(12^ = 497178513. □ Poznámka. Vidíme, že rekurentní vztah v tomto příkladu má složitější formu, než kterou jsme se zabývali v teorii a tudíž neumíme vyčíslit libovolné číslo P(kl) explicitně, nýbrž pouze postupným výpočtem od počátečních členů. 1.36. Určete explicitní vzorec pro n-tý člen jediné posloupnosti (x„}™=1 vyhovující následujícím podmínkám: xn+2 xn+1 xn, , x1 -1, x2 5. Řešení. xn = 2v/3sin(n • 60°) — 4cos(n • 60°). □ 1.37. Určete explicitní vzorec pro n-tý člen jediné posloupnosti (x„}™=1 vyhovující následujícím podmínkám: —xn+3 = 2xn+2 + 2xn+1 + xn, , x1 = 1 x2 = 1 x3 = 1. Řešení. xn = —3(—1)n — 2cos(n • 120°) — 2-^/3 sin(n • 120°). □ 1.38. Určete explicitní vzorec pro n-tý člen jediné posloupnosti {x„}^L1 vyhovující následujícím podmínkám: — xn+3 = 3xn+2 + 3xn+1 + xn, , x1 = 1 x2 = 1 x3 = 1. Řešení. xn = (—1)n(—2n2 + 8n — 7). □ 4. Pravděpodobnost Klasická pravděpodobnost Uveďme si několik jednoduchých příkladů na klasickou pravděpodobnost, kdy zkoumáme nějaký pokus, který má konečně mnoho možných výsledků („všechny případy") a nás zajímá, kdy výsledek pokusu bude náležet nějaké podmnožině možných výsledků („příznivé případy"). Hledaná pravděpodobnost je pak rovna poměru počtu příznivých případů ku počtu všech případů. Klasickou pravděpodobnost můžeme použít tam, kde předpokládáme (víme), že každý z možných výsledků má stejnou pravděpodobnost toho, že nastane (například při hodech kostkou). 4. PRAVDĚPODOBNOST 19 1.39. Jaká je pravděpodobnost, že při hodu šestibokou kostkou padne číslo větší než 4? 1.40. Všech možných výsledků je šest (tvoří množinu (1, 2, 3, 4, 5, 6}), příznivé možnosti jsou dvě ((5, 6}). Hledaná pravděpodobnost je tedy 2/6 = 1/3. 1.41. Ze skupiny osmi mužů a čtyř žen náhodně vybereme skupinu pěti lidí. Jaká je pravděpodobnost, že v ní budou alespoň tři ženy? Pravděpodobnost spočítáme jako podíl počtu příznivých případů ku počtu všech případů. Příznivé případy rozdělíme podle toho, kolik je v náhodně vybrané skupině mužů: mohou v ní být buď dva, nebo jeden muž. Skupinek o pěti lidech s jedním mužem je osm (záleží pouze na výběru muže, ženy v ní musí být všechny), skupinek se dvěma muži je potom c(8, 2)c(4, 3) = (2) (3) (vybereme dva muže z osmi a nezávisle na tom tři ženy ze čtyř, tyto dva výběry můžeme nezávisle kombinovat a podle pravidla součinu dostáváme uvedený počet skupin). Všech možných skupin o pěti lidech pak můžeme sestavit c (12, 5) = (152). Hledaná pravděpodobnost je tedy Řešení. 8+Q© □ 1.42. Do výtahu osmipatrové budovy nastoupilo 5 osob. Každá z nich vystoupí se stejnou pravděpodobností v libovolném poschodí. Jaká je pravděpodobnost, že všichni lidé vystoupí (1) v šestém poschodí, (2) ve stejném poschodí, (3) každý v jiném poschodí? Řešení. Základní prostor všech možných jevů je prostor všech možných způsobů vystoupení 5 osob z výtahu. Těch je 85. V prvním případě je jediná příznivá možnost vystoupení, hledaná pravděpodobnost je tedy 25, ve druhém případě máme osm možností, hledaná pravděpodobnost je tedy ^ a konečně ve třetím je počet příznivých případů dán pětiprvkovou variací z osmi prvků (z osmi pater vybíráme pět, ve kterých se vystoupí a dále kteří lidé vystoupí ve vybraných poschodích), celkem je hledaná pravděpodobnost ve třetím případě rovna (viz ?? a ??) 4^ = 8ll5-:Í = 0, 2050781250. □ Uveďme si příklad nevhodného použití klasické pravděpodobnosti: 1.43. Jaká je pravděpodobnost toho, že čtenář této úlohy vyhraje příští týden alespoň milión dolarů v loterii? Řešení. Základní prostor všech možný jevů je dvouprvkový: buď vyhraje nebo nevyhraje. Příznivý jev je jeden (vyhraje), hledaná pravděpodobnost je tedy 1/2. □ Poznámka. V předchozím příkladě je porušena základní 'podmínka 'použití klasické pravděpodobnosti, totiž to, že každý z možných výsledků má stejnou pravděpodobnost toho, že nastane. 20 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH 1.44. Do řady v kině o 2n místech je náhodně rozmístěno n mužů a n žen. Jaká je pravděpodobnost, že žádné dvě osoby stejného pohlaví nebudou sedět vedle sebe? Řešení. Všech možných rozmístění lidí v řadě je (2n)!, rozmístění splňujících podmínky je 2(n!)2 (máme dvě možnosti výběru pozice mužů, tedy i žen, na nich jsou pak muži i ženy rozmístěny libovolně). Výsledná pravděpodobnost je tedy 2(n!)2 p(n) = -(2nyr' P(2) = °, 33> P(5) = °,0079' p(8) = °, 00016 □ 1.45. Náhodně vybereme přirozené číslo menší než 105. Jaká je pravděpodobnost, že bude složeno pouze z cifer 0,1, 5 a zároveň bude dělitelné číslem 5? Řešení. ^ofe1. □ Ukažme si ještě pěkné použití principu inkluze a exkluze: 1.46. Sekretářka má rozeslat pět dopisů pěti různým lidem. Dopisy pro různé adresáty vkládá do obálek s adresami náhodně. Jaká je pravděpodobnost, že alespoň jeden člověk dostane dopis určený pro něj? Řešení. Spočítejme pravděpodobnost jevu opačného, tedy toho, že ani jeden člověk neobdrží správný dopis. Stavový prostor všech možných jevů odpovídá všem možným pořadím pěti prvků (obálek). Označíme-li jak obálky tak dopisy čísly od jedné do pěti, tak všechny příznivé jevy (tedy žádný dopis nepřijde do obálky se stejným číslem) odpovídají takovým pořadím pěti prvků, kdy i-tý prvek není na i-tém místě (i = 1,..., 5), tzv. pořadím bez pevného bodu. Jejich počet spočítáme pomocí principu inkluze a exkluze. Označíme-li Mj množinu permutací s pevným bodem i (permutace v Mj ale mohou mít i jiné pevné body), tak výsledný počet d permutací bez pevného bodu je roven d =5! - |M1 U • •• U M5| Počet prvků průniku |Mi1 n • • • n Mik |, k = 1,..., 5 je (5 — k)! (pořadí prvků i1,..., ik je pevně dáno, ostatních 5 —k prvků řadíme libovolně). Podle principu inkluze a exkluze je |Mi U • • • U M5I = ]T(- 1)fc+1 (f) (5 — k)! a tedy pro hledaný počet d dostáváme vztah d = 5! — ]T(- f)(n — k)! k k! k=0 v 7 fc=0 Pravděpodobnost toho, že žádný člověk neobdrží „svůj" dopis je tedy v (—D! Ľ k! fc=0 4. PRAVDĚPODOBNOST 21 a hledaná pravděpodobnost pak ^ k! 30' fc=0 □ Poznámka. Všimněme si, že odpověď na stejnou otázku, se s rostoucím počtem dopisů příliš nemění. Pro n dopisů je pravděpodobnost, že sekretářka nedá žádný do správné obálky 1 ^ k! ' e' fc=0 jak totiž uvidíme později, uvedená suma konverguje (blíží se) k hodnotě 1/e. 1.47. Další principy počítání s pravděpodobnostmi. Vraťme se k házení kostkou a zkusme popsat jevy ze základního prostoru fž vznikající při házení tak dlouho, dokud nepadne šestka, ne však více než stokrát. Pro jeden hod samostatně je základním prostorem šest čísel od jedné do šesti a jde o klasickou pravděpodobnost. Pro celé série našich hodů bude základní prostor daleko větší - bude to množina konečných posloupností čísel od jedné do šestky, které buď končí šestkou, mají nejvýše 100 členů a všechna předchozí čísla jsou menší než šest, nebo jde o 100 čísel od jedné do pěti. Jevem A může být např. podmnožina „házení končí druhým pokusem". Všechny příznivé elementární jevy pak jsou [1, 6], [2, 6], [3, 6], [4, 6], [5, 6]. Ze známé klasické pravděpodobnosti pro jednotlivé hody umíme odvodit pravděpodobnosti našich jevů v fž. Není to ale jistě klasická pravděpodobnost. Tak pro diskutovaný jev chceme popsat, s jakou pravděpodobností nepadne šestka při prvém hodu a zároveň padne při druhém. Vnucuje se řešení P(A) = 5 ' i = -5-, protože v prvém hodu padne s pravděpodobností 1 _ 6 jiné číslo než šest a druhý hod, ve kterém naopak požadujeme šestku, je zcela nezávislý na prvním. Samozřejmě toto není poměr počtu příznivých výsledků k velikosti celého stavového prostoru! Obecněji můžeme říci, že po právě 1 < k < 100 hodech pokus skončí s pravděpodobností (6• 6. Ze všech možností je tedy nejpravděpodobnější, že skončí již napoprvé. Jiný příklad, jak z házení kostkou dostat různě pravděpodobné jevyje pozorovat součty při hodu více kostkami. Uvažujme takto: při hodu jednou kostkou je každý výsledek stejně pravděpodobný s pravděpodobností 6. Při hodu dvěmi kostkami je každý předem zvolený výsledek (a, b), tj. dvojice přirozených čísel od jedné do šesti (včetně pořadí), stejně pravděpodobný s pravděpodobností 36. Pokud se budeme ptát po dvou pětkách, je tedy pravděpodobnost poloviční než u dvou různých hodnot bez uvedení pořadí. Pro jednotlivé možné součty uvedené v horním řádku nám vychází počet možností v řádku dolním: I 2 I 3 I 4 I 5 I 6 I 7 I 8 \ 9 \ 10 \ 11 \ 12 \ |1|2|3|4|5|6|5|4|3|2|1| 22 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH Podobně vyjde pravděpodobnost ^ jednotlivých výsledků hodu třemi kostkami, včetně určeného pořadí. Pokud se budeme ptát na pravděpodobnost výsledného součtu při hodu více kostkami, musíme pouze určit, kolik je možností, jak daného součtu dosáhnout a příslušné pravděpodobnosti sečíst. 1.48. Ze sáčku s pěti bílými a pěti červenými koulemi náhodně vytáhneme tři (koule do sáčku nevracíme). Jaká je pravděpodobnost, že dvě budou bílé a jedna červená? Řešení. Například rozdělíme uvažovaný jev na sjednocení tří disjunktních jevů: podle toho, kolikátou vytáhneme červenou kouli. Pravděpodobnosti, že vytáhneme koule přesně ve zvoleném pořadí jsou: 145 151 151 2 9 8' 29 2' 29 2' Celkem ^. □ 1.49. Z klobouku, ve kterém je pět bílých, pět červených a šest černých koulí, náhodně vytahujeme koule (bez vracení). Jaká je pravděpodobnost, že pátá vytažená koule bude černá? Řešení. Spočítáme dokonce obecnější úlohu. Totiž pravděpodobnost toho, že i-tá vytažená koule bude černá, je stejná pro všechna i, 1 < i < 16. Můžeme si totiž představit, že vytáhneme postupně všechny koule. Každá taková posloupnost vytažených koulí (od první vytažené koule po poslední), složená z pěti bílých, pěti červených a šesti černých koulí, má stejnou pravděpodobnost vytažení. Pravděpodobnost toho, že i-tá vytažená koule bude černá je tedy rovna podílu počtu posloupností pěti červených, pěti bílých a šesti černých koulí, kdy je na i-tém místě černá koule (těch je tolik, kolik je libovolých posloupností pěti bílých, pěti červených a pěti černých koulí, tedy P(5, 5, 5) = g,1^ ! ) a počtu všech posloupností složených z pěti bílých, pěti červených a šesti černých koulí, tedy P(6, 5, 5) = g^grgr. Tedy celkem 15 ! 3 5 ! 5 ! 5 ! = 3 6!5!5! □ 1.50. V jisté zemi mají parlament, ve kterém zasedá 200 poslanců. Dvě hlavní politické strany, které v zemi existují si při „ volbách" házejí o každý poslanecký mandát zvlášť mincí. Každá z těchto stran má přidělenu jednu stranu mince. Té straně, jejíž strana mince padne, náleží mandát, o který se právě losovalo. Jaká je pravděpodobnost, že každá ze stran získá 100 mandátů? (mince je „poctivá") Řešení. Všech možných výsledků losování (uvažovaných jako dvousetčlenné posloupnosti rubů a líců) je 2200. Pokud každá strana získá právě sto mandátů, je ve vylosované posloupnosti právě sto líců a sto rubů. Takových posloupností je 120000 (taková posloupnost je jednoznačně určená výběrem sto členů z dvě sta možných, na kterých budou např. líce). Celkem je hledaná pravděpodobnost /200N 200! V100/ = 100!-100! 2200 = 2200 □ 4. PRAVDĚPODOBNOST 23 1.3. Poznámka. Všimněme si, že v předchozím příkladu jsme mimochodem kombinatoricky dokázali nerovnost '200\ 22oo 100,1 < 2 ' resp. malým zobecněním dokonce pro libovolná k, n G N, k < n "í}<2" Následující příklad je jednoduchým modelem, který odhaduje pravděpodobnost úmrtí osoby při dopravní nehodě. 1.51. Ročně zahyne na silnicích v ČR přibližně 1200 českých občanů. Určete pravděpodobnost, že někdo z vybrané skupiny pěti set Čechů zemře v následujících deseti letech při dopravní nehodě. Předpokládejte pro zjednodušení, že každý občan má v jednom roce stejnou „šanci" zemřít při dopravní nehodě a to 1200/107. Řešení. Spočítejme nejprve pravděpodobnost, že jeden vybraný člověk v následujících deseti letech nezahyne na při dopravní nehodě. Pravděpodobnost, že nezahyne v jednom roce, je (1 — ). Pravděpodobnost, že nezahyne v následujících deseti letech, je pak (1 — )10. Pravděpodobnost, že v následujících deseti letech nezahyne nikdo z daných pěti set lidí, je opět podle pravidla součinu (jedná se o nezávislé jevy) (1 — )5000. Pravděpodobnost jevu opačného, tedy toho, že někdo z vybraných pěti set lidí zahyne, je tedy / 12 \ 5000 1 — i1 — T05j =0'4512 □ Poznámka. Model, který jsme 'použili v 'předchozím příkladu k popisu zadané situace, je pouze přibližný. Problém spočívá v podmínce, že každý občan z vyšetřovaného vzorku má stejnou pravděpodobnost toho, že v průběhu roku zahyne, kterou jsme odhadli z počtu usmrcených osob za rok. Počet tragických nehod se totiž rok od roku mění a i kdyby se neměnil, tak se mění populace. Ukažme si jednu s nepřesností příkladu na jiném způsobu řešení: zahyne-li 1200 osob za rok, tak za deset let zahyne 12000. Pravděpodobnost toho, že konkrétní člověk zahyne v průběhu deseti let tedy můžeme odhadnout i zlomkem 12000/107. Pravděpodobnost, že konkrétní osoba nezahyne v průběhu 10 let je tedy (1 — ) (to jsou první dva členy binomického rozvoje (1 — )-0). Celkem dostáváme anolagicky jako v předchozím řešení odhad pravděpodobnosti 12 \ 500 1—y1—10^; =0,4514 Vidíme, že oba odhady jsou velmi blízké. Snaha použít matematických znalostí k výhře v nejrůznějších hazardních hrách je velmi stará. Podívejme se na jednoduchý příklad. 1.52. Alešovi zbylo 2500 Kč z pořádání tábora. Aleš není žádný ňouma: 50 Kč přidal z kasičky a rozhodl se jít hrát ruletu na automaty. Aleš sází pouze na barvu. Pravděpodobnost výhry při sázce na barvu je 18/37. Začíná sázet na 10 Kč a pokud prohraje, v další sázce vsadí dvojnásobek toho, co v předchozí 24 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH (pokud na to ještě má, pokud ne, tak končí s hrou - byť by měl ještě peníze na nějakou menší sázku). Pokud nějakou sázku vyhraje, v následující sázce hraje opět o 10 Kč. Jaká je pravděpodobnost, že při tomto postupu vyhraje dalších 2550 Kč? (jakmile bude 2500 Kč v plusu, tak končí) Řešení. Nejprve spočítejme, kolikrát po sobě může Aleš prohrát. Začíná-li s 10 Kč, tak na n vsazení potřebuje n—1 2n _1 10 + 20 + • • • + 10 • 2n-1 = 10(^ 2Ž) = 10(--j-) = 10 • (2n - 1). i=0 Jak snadno nahlédneme, číslo 2550 je tvaru 10(2n — 1) a to pro n = 8. Aleš tedy může sázet osmkrát po sobě bez ohledu na výsledek sázky, na devět sázek by potřeboval již 10(29 — 1) = 5110 Kč a to v průběhu hry nikdy mít nebude (jakmile bude mít 5100 Kč, tak končí). Aby tedy jeho hra skončila neúspěchem, musel by prohrát osmkrát v řadě. Pravděpodobnost prohry při jedné sázce je 19/37, pravděpodbnost prohry v osmi po sobě následujících (nezávislých) sázkách je tedy (19/37)8. Pravděpodobnost, že vyhraje 10 Kč (při daném postupu) je tedy 1 — (19/37)8. Na to, aby vyhrál 2500 Kč, potřebuje 255 krát vyhrát po desetikoruně. Tedy opět podle pravidla součinu je pravděpodobnost výhry t—(i) 8F=- Tedy pravděpodobnost výhry je nižší, než kdyby vsadil rovnou vše na jednu barvu. □ 1.53. Samostatně si můžete vyzkoušet spočítat předchozí příklad za předpokladu, že Aleš sází stejnou metodou jako v předchozím příkladě, končí však až v okamžiku, kdy nemá žádné peníze (pokud nemá na vsazení dvojnásobku částky prohrané v předchozí sázce, ale má ještě nějaké peníze, začíná sázet znovu od 10 Kč). 1.54. Podmíněná pravděpodobnost. 1.55. Jaká je pravděpodobnost toho, že při hodu dvěma kostkami padne součet 7, víme-li, že ani na jedné z kostek nepadlo číslo 2. Řešení. Označme jev, že ani na jedné kostce nepadne dvojka jako B, jev „padne součet 7" jako A. Množinu všech možných výsledků budeme značit opět jako n. Pak P (AB) = P (A n B) = ^ = |A n B| Číslo 7 může padnout čtyřmi různými způsoby, pokud nepadne dvojka, tedy |A n B| =4, |B| = 5 • 5 = 25, tedy P (a|b) = 25 . Všimněme si, že P (A) = 6, tedy jevy A a B jsou závislé. □ 1.56. Michal má dvě poštovní schránky, jednu na gmail.com a jednu na se-znam.cz. Uživatelské jméno má stejné na obou serverech, hesla různá (ale nepamatuje si, které heslo má na kterém serveru). Při zadávání hesla při přístupu 4. PRAVDĚPODOBNOST 25 do schránky se splete s pravděpodobností 1/20 (tj. jestliže chce napsat zadat jemu známé slovo jako heslo, tak jej s pravděpodobností 95% skutečně správně na klávesnici zadá). Michal zadal na serveru seznam.cz jméno a heslo a server mu oznámil, že něco není vpořádku. Jaká je pravděpodobnost, že chtěl zadat správné heslo, ale pouze se „překlepnul" při zadávání? (Předpokládáme, že uživatelské jméno zadá vždy bez chyby.) Řešení. Označme A jev, že Michal fyzicky zadal na serveru seznam.cz špatné heslo. Tento jev je sjednocením dvou disjunktních jevů: A1: chtěl zadat správné heslo a přepsal se, A2: chtěl zadat špatné heslo (to z gmail.com) a buď se přepsal nebo ne. Hledáme tedy podmíněnou pravděpodobnost p(A1|A), ta je podle vztahu pro podmíněnou pravděpodobnost rovna: =p(A1 nA) = p(A1) = p(A1) 1K 1 ; p(A) p(A1 U A2) p(A1)+ p(A2)' potřebujeme tedy určit pravděpodobnosti p(A1) a p(A2). Jev A1 je konjunkcí (průnikem) dvou nezávislých jevů: Michal chtěl zadat správné heslo a Michal se při zadávání přepsal. Dle zadání je pravděpodobnost prvního z nich 1/2, druhého 1/20, celkem p(A1) = 2 • 20 = 40 (pravděpodobnosti násobíme, protože se jedná o nezávislé jevy). Dále je ze zadání p(A2) = 2. Celkem p(A) = p(A1) + p(A2) = 40 + 2 = 20, a můžeme vyčíslit: o(A1i A) =p(A1) = i = J_ P(A1|A)= P(A) = 20 = 21 • □ 1.57. Geometrická pravděpodobnost. Metodu geometrické pravděpodobnosti můžeme použít v případě, že daný jevový prostor sestává z nekonečně mnoha elementárních jevů, které dohromady vyplňují nějakou oblast na přímce, rovnině, prostoru (u které umíme určit její délku, obsah, objem, . . . ) a předpokládáme, že pravděpodobnost, že nastane elementární jev z určité podblasti je rovna poměru její velikosti (délce, obsahu, ...) k velikosti celého jevového prostoru. 1.58. Z Těšína vyjíždí vlaky co půl hodinu (směrem na Bohumín) a z tohoto směru přijíždějí také každé půl hodiny. Předpokládejme, že vlaky se mezi těmito dvěma stanicemi pohybují rovnoměrnou rychostí 72 km/h a jsou dlouhé 100metrů, cesta trvá 30min, vlaky se míjejí někde na trase. Hazardér Jarda si vybere jeden z těchto vlaků a během cesty z Těšína do Bohumína náhodně vystrčí hlavu z okna na pět vteřin nad kolejiště pro protější směr. Jaká je pravděpodobnost, že mu bude uražena? (předpokládáme, že jiné než zmíněné vlaky na trati nejezdí) Řešení. Vzájemná rychlost protijedoucích vlaků je 40m/s, protijedoucí vlak mine Jardovo okno za dvě a půl sekundy. Prostor všech možností je tedy úsečka (0,1800s), prostor „příznivých" možností je úsečka délky 7, 5 ležící někde uvnitř předchozí úsečky. Pravděpodobnost uražení hlavy je tedy 7, 5/1800. □ 1.59. Jednou denně někdy mezi osmou hodinou ranní a osmou hodinnou večerní vyjíždí náhodně autobus z Koločavy do Užhorodu. Jednou denně ve stejném časovém rozmezí jezdí jiný autobus náhodně opačným směrem. Cesta tam 26 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH trvá pět hodin, zpět též pět hodin. Jaká je pravděpodobnost, že se autobusy potkají, jezdí-li po stejné trase? Řešení. Prostor všech možných jevů je čtverec 12 x 12, Označíme-li doby odjezdu obou autobusů x, resp. y, pak se tyto na trase potkají právě když |x — y| < 5. Tato nerovnost vymezuje v daném čtverci oblast „příznivých jevů". Obsah zbylé části spočítáme přímo jednodušeji, neboť je sjednocením dvou pravoúhlých rovnoramenných trojúhelníků o odvěsnách 7, tedy je roven 49, obsah části odpovídající „příznivým jevům" je tedy 95, celkem je hledaná pravděpodobnost _ 95 P ~~ 144 ' □ 1.60. Mirek vyjede náhodně mezi desátou hodinou dopolední a osmou hodinou večerní z Brna do Prahy. Marek vyjede náhodně ve stejném intervalu z Prahy do Brna. Oběma trvá cesta 2h. Jaká je pravděpodobnost, že se po cestě potkají (jezdí po stejné trase). Cesta trvá oběma 2h. Řešení. Prostor všech možných jevů je čtverec 10 x 10, Mirek vyjíždějící v čase x, potká Marka vyjíždějícího v čase y právě když |x — y| < 2. Tato nerovnost vymezuje v daném čtverci oblast „příznivých jevů". Obsah zbylé části spočítáme přímo jednodušeji, neboť je sjednocením dvou pravoúhlých rovnora-menných trojúhelníků o odvěsnách 8, tedy je roven 64, obsah části odpovídající „příznivým jevům" je tedy 36, celkem je hledaná pravděpodobnost 4. PRAVDĚPODOBNOST 27 □ 1.61. Dvoumetrová tyč je náhodně rozdělena na tři díly. Určete pravděpodobnost, že alespoň jeden díl bude nejvýše 20 cm dlouhý. Řešení. Náhodné rozdělení tyče na tři díly je dáno dvěma body řezu, čísly x a y (nejprve tyč rozřízneme ve vzdálenosti x od počátku, nehýbeme s ní a dále ji rozřízneme ve vzdálenosti y od počátku). Pravděpodobnostní prostor je tedy čtverec o straně 2 m. Umístíme-li čtverec C tak, aby dvě jeho strany ležely na kartézských osách v rovině, tak podmínka, že alespoň jeden díl má být nejvýše 20 cm dlouhý nám vymezuje ve čtverci následující oblast O: O = {(x, y) G C|(x < 20) V (x > 180) V (y < 20) V (y > 180) V (|x - y|) < 20}. Jak snadno nahlédneme, zaujímá takto vymezená oblast j51) obsahu čtverce. □ 1.62. Dvoumetrová tyč je náhodně rozdělena na tři díly. Určete pravděpodobnost, že ze vzniklých dílů půjde sestavit trojúhelník. Řešení. Rozdělení tyče je dáno stejně jako v předchozím příkladě dáno body řezu x a y a jevovým prostorem je opět čtverec 2 x 2. Aby z částí bylo možno sestavit trojúhelník, musejí jejich délky splňovat tzv. trojúhelníkové nerovnosti, tedy součet délek libovolných dvou částí musí být větší než délka třetí části. Vzhledem k tomu, že součet délek je roven 2m, je tato podmínka ekvivalentní podmínce, že každá s částí musí být menší než 1m. To pomocí řezů x a y vyjádříme tak, že nesmí platit současně | x| < 1 a | y| < 1 nebo současně | x| > 1 a |y| > 1 (odpovídá podmínkám, že krajní díly tyče jsou menší než 1), navíc 28 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH |x — y| < 1 (prostřední díl musí být menší než jedna). Tyto podmínky splňuje vyšrafovaná oblast na obrázku a jak snadno nahlédneme, její obsah je 1/4. □ 1.63. Z Brna vyrazí náhodně někdy mezi polednem a čtvrtou hodinou odpolední Honza autem do Prahy a opačným směrem někdy ve stejném intervalu autem Martin. Oba si dávají půl hodiny pauzu v motorestu v polovině cesty (přístupném pro oba směry). Jaká je pravděpodobnost, že se tam potkají, jezdí-li Honza rychlostí 150 km/h, a Martin 100 km/h? (vzdálenost Brno-Praha je 200 km) Řešení. Označíme-li dobu odjezdu Martina x a dobu odjezdu Honzy y a pro menší výskyt zlomků v následujících výpočtech zvolíme za jednotku deset minut, tak stavovým prostorem bude čtverec 24 x 24. Doba příjezdu Martina do motorestu je x+6, do příjezdu Honzy (x+4). Stejně jako v předchozím příkladu to, že se v motorestu potkají je ekvivalentní tomu, že doby jejich příjezdu se neliší o více než o půl hodiny, tedy | (x + 6) — (y + 4) | < 3. Tato podmínka nám pak ve stavovém čtverci vymezuje oblast o obsahu 242 — 1 (232 + 192) (viz obr.) a hledaná pravděpodobnost je = 242 — i (232 + 192) = 131 p 242 576 , □ 5. GEOMETRIE V ROVINE 29 1.64. Mirek a Marek chodí na obědy do univerzitní menzy. Menza má otevřeno od 11h do 14h. Každý z nich stráví na obědě půl hodiny a dobu příchodu (mezi 11h a 14h) si vybírá náhodně. Jaká je pravděpodobnost, že se na obědě v daný den potkají, sedávají-li oba u stejného stolu? Řešení. Prostor všech možných jevů je čtverec 3 x 3. Označíme-li x dobu příchodu Mirka a y dobu příchodu Marka, tak tito se potkají právě když |x — y| < 1/2. Tato nerovnost vymezuje ve čtverci možných událostí oblast, jejíž obsah je roven 11/38 obsahu čtverce. Tomuto zlomku je tedy rovna i hledaná pravděpodobnost. □ 5. Geometrie v rovině 1.65. Je dána přímka p : [2,0]+t(3, 2). Určete její obecnou rovnici a nalezněte průnik s přímkou q : [—1, 2] + 3). Řešení. Souřadnice bodů na přímce jsou dány dle daného parametrického zadání jako x = 2 + 3t a y = 0 + 2t. Vyloučením parametru t ze soustavy těchto dvou rovnic dostáváme obecnou rovnici přímky p: 2x - 3y - 4 = 0. Průnik s přímkou q získáme dosazením parametrického vyjádření bodů na úsečce q, tedy x = -1 + s a y = 2 + 3s do obecné rovnice přímky p: 2(-1 + s) - 3(2+ 3s) - 4 = 0, odkud s = -12/7 a dosazením do parametrického vyjádření úsečky q dostáváme souřadnice průsečíku P: 19 22 . □ 1.66. Uvažujme rovinu R2 se standardní soustavou souřadnic. Z počátku [0, 0] je vyslán laserový paprsek ve směru (3,1). Dopadne na zrcadlovou přímku p danou parametricky jako p : [4, 3]+t(- 2,1), a poté se odrazí (úhel dopadu je shodný s úhlem odrazu). V jakém bodě dopadne odražený paprsek na přímku q, danou parametricky jako q : [7,-10]+t(-1, 6)? Řešení. Směr paprsku svírá s přímkou p úhel 45°, odražený paprsek tedy bude kolmý na dopadající, jeho směrový vektor bude (1, -3) (pozor na orientaci!; daný směrový vektor můžeme též získat například zrcadlením podle kolmého vektoru k přímce p). Paprsek dopadne v bodě [6, 2], odražený paprsek tedy bude mít rovnici [6, 2]+ t(1, -3), t > 0. 30 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH Průnik přímky dané odraženým paprskem s přímkou q je bod [4, 8], což je mimo polopřímky dané odraženým paprskem (t = —2). Odražený paprsek tedy přímku q neprotne. □ 1.67. Z bodu [—2,0] vyrazila v pravé poledne konstantní rychlostí 1ms-1 ve směru (3, 2) úsečka délky 1. Rovněž v poledne vyrazila z bodu [5, —2] druhá úsečka délky 1 ve směru (—1,1), ovšem dvojnásobnou rychlostí. Srazí se? Řešení. Přímky, po kterých se pohybují dané úsečky, můžeme popsat parametrickým vyjádřením: p : [—2, 0] + r(3, 2) q : [5, —2] + s( —1,1), Obecná rovnice přímky p je 2x — 3y + 4 = 0. Dosazením parametrického vyjádření přímky q získáme průsečík P = [1, 2]. Nyní se snažme zvolit jediný parametr t pro obě úsečky tak, aby nám odpovídající bod na přímkách p, resp. q, popisoval polohu počátku první, resp. druhé, úsečky v čase t. V čase 0 je první v bodě [—2, 0], druhá v bodě [5, —2]. Za čas t sekund urazí první t jednotek délky ve směru (3, 2) druhá pak 2t jednotek délky ve směru (—1,1). Odpovídající parametrizace jsou tedy (1.14) P : [—2,0] + JĽ(3,2) (1.15) q : [5, —2] + V2í(—1,1), (1.16) Počátek první úsečky dorazí do bodu [1, 2] v čase t1 = a/I3s, počátek druhé úsečky v čase t = 2\/2s, tedy více než o půl vteřiny dříve a tedy v době, kdy dorazí do průsečíku P počátek první úsečky, bude již druhá úsečka pryč a úsečky se tak nesrazí. □ 1.68. Viditelnost stran trojúhelníka. Je dán trojúhelník s vrcholy [5, 6], [7, 8], [5, 8]. Určete, které jeho strany je vidět z bodu [0,1]. Řešení. Uspořádáme vrcholy v kladném smyslu, tedy proti směru hodinových ručiček: [5, 6], [7, 8], [5, 8]. Pomocí příslušných determinantů určíme, je-li bod [0,1] „nalevo" či „napravo" od jednotlivých stran trojúhelníka uvažovaných jako orientované úsečky, 7 7 >0 7 5 <0 5 7 =0 Z nulovosti posledního determinantu vidíme, že body [0, 1], [5, 6] a [7, 8] leží na přímce, stranu [5, 6][7, 8] tedy nevidíme. Stranu danou vrcholy [5, 8] a [7, 8] pak narozdíl od strany [5, 6][5, 8] nevidíme. □ 1.69. Určete, které strany čtyřúhelníka s vrcholy [95, 99], [130,106], [40, 60], [130,120]. jsou viditelné z bodu [2, 0]. Řešení. Nejprve je třeba určit strany čtyřúhelníka („správné" pořadí vrcholů): [95, 99][40, 60][130,106][130,120]. Po spočítání příslušných determinantů (viz přednáška) zjistíme, že jsou vidět pouze strana [40, 60][130, 106]. □ 5. GEOMETRIE V ROVINE 31 1.70. Rovinný fotbalista vystřelí míč z bodu F = [1,0] ve směru (3,4) na bránu (úsečku) ohraničenou body A = [23, 36] a B = [26, 30]. Směřuje míč do brány? Řešení. Vzhledem k tomu, že se situace odehrává v prvním kvadrantu, stačí uvažovat směrnice vektorů FA,(3,4),FB. Tvoří-li (v tomto pořadí) buď rostoucí, nebo klesající posloupnost, míč směřuje na bránu. Tato posloupnost je 36/22, 4/3, 30/25, což je klesající posloupnost, míč tedy směřuje do brány. □ 1.71. Určete obsah čtyřúhelníka ABCD s vrcholy A = [1, 0], B = [11,13], C = [2, 5] a D = [—2, —5]. Řešení. Rozdělíme na dva trojúhelníky ABC a ACD. Jejich obsahy pak spočítáme pomocí patřičných determinantů, viz ?? S = 1 5 10 13 + 15 47 □ 1.72. Buď dán pravidelný šestiúhelník ABCDEF (vrcholy jsou označeny v kladném smyslu) se středem v bodě [1, 0] a vrcholem A = [0, 2] Určete souřadnice vrcholu C. Řešení. Souřadnice vrcholu C získáme otočením bodu A okolo středu S šestiúhelníka o 120° v kladném smyslu: /cos(120°) — sin(120°^(C _ S) + S = C sin(120°) cos(120°) 2 , 2 VT 2 _! 2 / ^ + [1,0] = [3 -V3, -1 - □ 1.73. Buď dán rovnostranný trojúhelník s vrcholy [1,0] a [0,1] ležící celý v prvním kvadrantu. Určete souřadnice jeho třetího vrcholu. Řešení. [1 + ^, i + ^] (otáčíme o 60° bod [1,0] kolem [0,1] v kladném smyslu). □ 1.74. Napište souřadnice vrcholů trojúhelníka, který vznikne otočením rovnostranného trojúhelníka jehož dva vrcholy jsou [1, 1] a [2, 3] (třetí pak v polorovině dané přímkou [1, 1][2, 3] a bodem [0, 0]) o 60° v kladném smyslu kolem bodu [0, 0]. Řešení. Třetí vrchol trojúhelníka dostaneme např. otočením o 60° jednoho z vrcholů kolem druhého (ve správném smyslu). [— fv^í, a/3 —1 ], [1 — ^V^, 1v/3+ 2j), [1 - |v/3^v/3+ 3j. □ 1.75. Určete obsah trojúhelníka A2A3A11, kde AoA1 ... A11 jsou vrcholy pravidelného dvanáctiúhelníka vepsaného do kružnice o poloměru 1. Řešení. Vrcholy dvanáctiúhelníka můžeme ztotožnit s dvanáctými odmocninami z čísla 1 v komplexní rovině. Zvolíme-li navíc Ao = 1, pak můžeme psát Ak = cos(2kn/12)+i sin(2kn/12). Pro vrcholy zkoumaného trojúhelníka máme: A2 = cos(n/3) + i sin(n/3) = 1/2 + ía/3/2, A3 = cos(n/2) + i sin(n/2) = i, 1 1 2 2 32 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH An = cos(-n/6) + i sin(-n/6) = a/3/2 - i/2. Podle vzorce pro obsah trojúhelníka je potom hledaný obsah S roven S = 1 A2 - A11 1 2 A3 - A11 = 2 V3 2 2 + 2 3 2 3 - a/3 □ 1.76.4. Určete odchylku (nebo její kosinus) úhlopříček A3A7 a A5A10 pravidelného dvanáctiúhelníka A0 A1A2 A3 A4 A5A6 A7As A9A10 A11. Řešení. Odchylka nezávisí na velikosti daného dvanáctiúhelníka. Volme dvanáctiúhelník vepsaný do kružnice o poloměru 1. Jako v předchozím příkladě určíme souřadnice jeho vrcholů a podle vzorce snadno dopočítáme, odchylka je 75°, cos = ,1 . 2a/2+\/3 Úlohu lze řešit čistě metodami syntetické geometrie: označíme ještě S střed dvanáctiúhelníka a T průsečík úhlopříček A3A7 a A5A10. Nyní |ZA7A5A10| = 45° (obvodový úhel příslušný středovému úhlu A7SA10, který je pravý), dále |ZA5A7A31 = 30° (obvodový úhel příslušný středovému úhlu A5SA3, jehož velikost je 60°). Velikost úhlu A5TA7 je pak dopňkem výše zmíněných úhlů do 180°, tedy je rovna 105°. Hledaná odchylka je tedy 75°. □ 1.77. Najděte matice A takové, že A2 = (I 7) Nápověda: jaké geometrické zobrazení v rovině zadává matice A2? Řešení. A2 je matice rotace o 60° v kladném smyslu, takže A= (í?) tedy matice rotace o 30°, resp. o 210°. □ 1.78. Rovnoběžníková rovnost. Dokažme jako ilustraci našich nástrojů tzv. „rovnoběžníkovou rovnost": Jsou-li u, v G R2, pak: 2(IMI2 + H2) = ||« + vy2 +1|« - vy2. Neboli součet druhých mocnin délek úhlopříček rovnoběžníka je roven dvojnásobku součtu druhých mocnin délek jeho stran. Řešení. Obdržíme například rozepsáním obou stran do souřadnic: u = (u1, u2), v = (v1, V2). Pak 2(||u||2 + y vy2) = 2(u2 + u2 + v2 + v2) = u + 2u1 v1 + v2 + U2 + 2u2v2 + v2 + U1 - 2u1v1 + v2 + u2 - 2u2v2 + v2 = (U1 + v1)2 + (U2 + v2)2 + (U1 - v1)2 + (U2 - v2)2 = ||u + v^2 + - v||2 □ 6. ZOBRAZENÍ A RELACE 33 1.79. Ukažte, že složením lichého počtu středových symetrií v rovině dostaneme opět středovou symetrii. Řešení. Středovou symetrii v rovině se středem S reprezentujme předpisem X — S — (X — S), neboli X — 2S — X. (Obraz bodu X ve středové symetrii podle středu S dostaneme tak, že k souřadnicím bodu S přičteme souřadnice vektoru opačného k vektoru X — S.) Postupnou aplikací tří středových symetrií se středy S, T a U tak dostáváme X — 2S — X — 2T — (2S — X) — 2U — (2T — (2S — X)) = 2(U — T + S) — X, celkem X — 2(U — T + S) — X, což je středová symetrie se středem S — T + U. □ 1.80. Sestrojte (2n + 1)-úhelník, jsou-li dány všechny středy jeho stran. Řešení. K řešení využijeme toho, že složením lichého počtu středových souměrností je opět středová souměrnost (viz předchozí příklad). Označíme-li vrcholy hledaného (2n + 1)-úhelníka po řadě A1, A2,..., A2n+1 a středy stran (od středu A1A2) postupně S1, S2,...S2n+1, tak provedeme-li středové souměrnosti po řadě podle těchto středů, tak bod A1 je zjevně pevným bodem výsledné středové symetrie, tedy jejím středem. K jeho nalezení tedy stačí provést uvedenou středovou souměrnost s libovolným bodem X roviny. Bod A1 leží pak ve středu úsečky XX', kde X' je obrazem bodu X ve zmíněné středové symetrii. Další vrcholy získáme zobrazováním bodu A1 ve středových souměrnostech podle S1,..., S2n+1. □ 6. Zobrazení a relace 1.81. Rozhodněte, zda následující relace na množině M jsou relace ekvivalence: (1) M = {f : R — R}, (f ~ g) ^ f (0) = g(0). (2) M = {f : R — R}, (f ~ g) ^ f (0) = g(1). (3) M je množina přímek v rovině, dvě přímky jsou v relaci, jestliže se neprotínají. (4) M je množina přímek v rovině, dvě přímky jsou v relaci, jestliže jsou rovnoběžné. (5) M = N, (m - n) S(m) + S(n) = 20, kde S(n) značí ciferný součet čísla n. Řešení. (1) Ano. Ověříme tři vlastnosti ekvivalence: i) Reflexivita: pro libovolnou reálnou funkci f je f (0) = f (0). ii) Symetrie: jestliže platí f(0) = g(0), pak i g(0) = f(0). iii) Tranzitivita: jestliže platí f (0) = g(0) a g(0) = h(0), pak platí i f (0) = h(0). (2) Ne. Definovaná relace není reflexivní, např pro funkci sin máme sin(0) = sin(1) (3) Ne. Relace opět není reflexivní (každá přímka protíná sama sebe) (4) Ano. Třídy ekvivalence pak tvoří množinu neorientovaných směrů v rovině. (5) Ne. Relace není reflexivní. S(1) + S(1) = 2. □ 34 1. přehršel různorodých úloh Relace a zobrazení mezi konečnými množinami dávají vzniknout celé řadě kombinatorických otázek: 1.82. Počet injektivních zobrazení mezi množinami Určete počet injektivních zobrazení množiny {1, 2, 3 } do množiny {1, 2,3,4 } Řešení. Libovolné injektivní zobrazení mezi uvažovanými množinami je dáno výběrem (uspořádané) trojice z množiny {1, 2, 3,4} (prvky ve vybrané trojici budou po řadě obrazy čísel 1, 2, 3) a obráceně každé injektivní zobrazení nám zadává takovou trojici. Je tedy hledaných injektivních zobrazení stejně jako možností výběru uspořádaných trojic ze čtyř prvků, tedy v(3,4) = 4 • 3 • 2 = 24. □ 1.83. Určete počet surjektivních zobrazení množiny {1, 2, 3,4} na množinu {1, 2, 3} Řešení. Počet zjistíme obecným principem „inkluze a exkluze". Od počtu všech zobrazení odečteme ta, která nejsou surjektivní, t.j. ta, jejichž obor hodnot je buď jednoprvkovou nebo dvouprvkovou množinou. Všech zobrazení je V(3,4) = 34, zobrazení, jejichž oborem hodnot je jednoprvková množina, jsou tři. Počet zobrazení jejichž oborem hodnot je dvouprvková množina je (2)(24 — 2) ((3) způsoby můžeme vybrat definiční obor a máme-li již dva prvky fixovány, máme 24 — 2 možností, jak na ně zobrazit čtyři prvky). Celkem je tedy počet hledaných surjektivních zobrazení (1.17) 34 — (2)(24 — 2) — 3 = 36- □ 1.84. Hasseův diagram uspořádání. Hasseův diagram daného uspořádání ~ na n-prvkové množině M je diagram s n vrcholy (každý vrchol odpovídá právě jednomu prvku množiny), přičemž dva vrchly (prvky) a, b jsou spojeny (víceméně svislou) čarou (tak, že a je „dole" a b „nahoře"), právě když b pokrývá a, tj. a ~ b a neexistuje c G M tak, že a ~ c a c ~ b. 1.85. Určete počet relací uspořádání na čtyřprvkové množině. Řešení. Postupně projdeme všechny možné Hasseovy diagramy uspořádání na nějaké čtyřprvkové množině M a spočítáme, kolik různých uspořádání (tj. podmnožin množiny M x M) má daný Hasseův diagram, viz obr.: i" r 1 Celkem tedy 219 uspořádání. 1.86. Určete počet relací ekvivalence na množině {1, 2, 3,4}. □ 6. ZOBRAZENÍ A RELACE 35 Řešení. Ekvivalence můžeme počítat podle toho, kolik prvků mají jejich třídy rozkladu. Pro počty prvků tříd rozkladu ekvivalencí na čtyřprvkové množině jsou tyto možnosti: Počty prvků ve třídách rozkladu počet ekvivalencí daného typu 1,1,1,1 1 2,1,1 (2) 2,2 |(2) 3,1 (4) 4 1 Celkem tedy máme 15 různých ekvivalencí. □ 1.87. Kolík existuje relací na n-prvkové množině? Řešení. Relace je libovolná podmnožina kartézského součinu množiny se sebou, který má n2 prvků, je tedy počet všech relací 2n . □ 1.88. Kolik reflexivních relací na n-prvkové množině? Řešení. Relace na množině M je reflexivní, právě když je diagonální relace AM = {(a, a)|a G M} její podmnožinou. U zbylých n2 — n uspořádaných dvojic v kartézském součinu M x M máme nezávislou volbu, jestli daná dvojice v dané relaci bude či ne. Celkem máme různých reflexivních relací na n-prvkové množině. □ 1.89. Kolik existuje symetrických relací na n-prvkové množině? Řešení. Relace na množině M je symetrická právě když je její průnik s každou množinou {(a, b), (b, a)}, a = b, a, b G M buď celá daná dvojprvková množina. Takových množin je q) a pokud kromě průniků s těmito množinami ještě určíme průnik dané relace s diagonální relací AM = {(a, a)|a G M} je tímto daná relace jednoznačně určena. Celkem můžeme provést (!^) • n nezávislých voleb mezi dvěma alternativami (každá množina typu {(a, b), (b, a)|a, b G M, a = b} buď je podmnožinou dané relace, nebo ani jeden z jejich prvků v dané relaci neleží; každá dvojice (a, a), a G M, potom také buď v relaci leží nebo ne), celkem máme 2(n) + n symetrických relací na n-prvkové množině. □ 1.90. Kolik existuje antisymetrických relací na n-prvkové množině? Řešení. Relace na množině M je antisymetrická právě když její průnik s každou množinou {(a, b), (b, a)} a = b, a, b G M není dvojprvkový (jsou tedy tři možnosti jak průnik vypadá, buď je to množina {(a, b)}, nebo {(b, a)}, nebo je průnik prázdný). Průnik s diagonální relací pak může být libovolný. Určením těchto všech průniků je relace jednoznačně určena. Celkem máme 3(n)2n antisymetrických relací na n-prvkové množině. □ 1.91. Určete počet relací uspořádání na tříprvkové množině. Řešení. 19. □ 36 1. PŘEHRŠEL RŮZNORODÝCH ÚLOH 1.92. Určete počet relací uspořádání na množině {1, 2, 3,4} takových, že prvky 1 a 2 jsou nesrovnatelné (tedy neplatí 1 ~ 2 ani 2 ~ 1, kde ~ je označení uvažované relace uspořádání). Řešení. 87. □ Literatura [1] Marie Budíková, Štěpán Mikoláš, Pavel Osecký, Teorie pravděpodobnosti a matematická statistika (sbírka příkladů), Masarykova univerzita, 3. vydání, 2004, 117 stran, ISBN 80-210-3313-4. [2] Marie Budíková, Štěpán Mikoláš, Pavel Osecký, Popisná statistika, Masarykova univerzita, 3. vydání, 2002, 48 stran, ISBN 80-210-1831-3. [3] Marie Budíková, Tomáš Lerch, Štěpán Mikoláš, Základní statistické metody, Masarykova univerzita, 2005, 170 stran, ISBN 80-210-3886-1. [4] Zuzana Došlá, Jaromír Kuben, Diferenciální počet funkcí jedné proměnné, MU Brno, 2003, 215 s., ISBN 80-210-3121-2. [5] Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. [6] William J. Gilbert, W. Keith Nicholson, Modern algebra with applications, 2nd ed. John Wiley and Sons (Pure and applied mathematics) ISBN 0-471-41451-4 [7] Pavel Horák, Úvod do lineární algebry, MU Brno, skripta. [8] Ivana Horová, Jiří Zelinka, Numerické metody, MU Brno, 2. rozšířené vydání, 2004, 294 s., ISBN 80-210-3317-7. [9] Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. [10] Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Univerzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/~lmotm275/skripta/). [11] Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. [12] František Šik, Lineární algebra zaměřená na numerickou analýzu, MU, 1998, 176 s. ISBN 80-210-1996-2. [13] Jan Slovák, Lineární algebra. učební texty, Masarykova univerzita, elektronicky dostupné na www.math.muni.cz/~slovak [14] Pavol Zlatoš, Lineárna algebra a geometria, skripta MFF Univerzity komenského v Bratislavě. [15] Karel Zvára, Josef Štěpán, Pravděpodobnost a matematická statistika, Matfyzpress, Universita Karlova, 2006, 230 s. 37