Domácí úkol z kombinatoriky, 2. prosince 2024 Přestože tento domácí úkol nebudete odevzdávat, měli byste si jej ve vlastním zájmu sepsat. Nezapomeňte vždy zapsat i úvahu, kterou jste k výsledku došli, způsobem, kterým byste svůj postup vysvětlili spolužákovi. Vzorové řešení zadaných úloh bude uveřejněno v interaktivní osnově v pátek 6. prosince 2024, abyste si svůj domácí úkol mohli sami opravit. 1. Ve čtvercové síti je povoleno jít dolů, doprava a diagonálně vpravo dolů (viz náčrtek). Označme an, kde nGZ,ii>0, počet cest z daného startovního bodu do cílového bodu, který je o dvě délky strany čtverce níže a o n délek strany čtverce vpravo (náčrtek popisuje situaci pro n = 9). Nalezněte rekurentní vztah pro výpočet členů posloupnosti {an}^l0 pomocí předchozích členů. Vypočtěte a13. 2. Rekurentní posloupnost {&n}^Li Je dána svými počátečními hodnotami bi = 1, &2 = 0, &3 = 4, a rekurentním vztahem bn+3 = 2&n+2 + bn+i — 2bn platným pro každé přirozené číslo n. Nalezněte explicitní vyjádření členu bn této posloupnosti, tj. vyjádření, ve kterém nebudou vystupovat jiné členy této posloupnosti (jedinou proměnnou bude n). 3. Ve hře Sportka se táhne z osudí, ve kterém je 49 míčků označených přirozenými čísly 1 až 49. Tah spočívá v tom, že se z osudí náhodně vylosuje 6 míčků (poté se losuje ještě jeden míček pro určení tzv. dodatkového čísla, které však v této úloze neuvažujeme). Určete, s jakou pravděpodobností bude v příštím tahu mezi vylosovanými šesti míčky alespoň jeden míček s číslem z množiny {10,11,..., 19}, alespoň jeden míček s číslem z množiny {20, 21,..., 29} a alespoň jeden míček s číslem z množiny {30, 31,..., 39}. Vzorové řešení 1. Ze startovního bodu musíme vyjít jedním ze tří způsobů. Vyjdeme-li vpravo, dostaneme se do bodu, odkud můžeme pokračovat právě an_i různými cestami. Vyjdeme-li dolů, dostaneme se do bodu, ze kterého je cílový bod vzdálen o jednu délky strany čtverce níže a o n délek strany čtverce vpravo. Při pokračování cesty musíme tedy právě jednou jít buď dolů anebo jít diagonálně vpravo dolů, všechny ostatní kroky už budou vpravo. Šipek dolů je n + 1, šipek vpravo dolů je n. Protože každá z těchto cest je jednoznačně určena tím, kterou z těchto 2n + 1 šipek použijeme, je počet cest, kterými můžeme pokračovat, roven 2n + 1. Vyjdeme-li diagonálně vpravo dolů, dostaneme se do bodu, ze kterého je cílový bod vzdálen o jednu délky strany čtverce níže a o n — 1 délek strany čtverce vpravo. Podobně jako v předchozím případě odvodíme, že počet cest, kterými můžeme pokračovat, je roven 2n — 1. Z tohoto rozboru plyne rekurentní vztah an = an_\ + An. Je zřejmé, že a0 = 1. Užitím rekurentního vztahu postupně dostaneme = a0 4 -A- 1 = 5, a2 = ai -i -A- 2 = 13, a3 = a2 -i -A- 3 = 25, = a3 4 -A- 4 = 41, a5 = aA-\ -A- 5 = 61, a6 = a5 4 -A- 6 = 85, ďj = a6 -i -A- 7 = 113, a8 = a7 -i -A- 8 = 145, Clg = a8 -i -A- 9 = 181, a10 = a9 -i -A- 10 = = 221, an = dio + 4 • 11 = 265 0.12 = an + 4 • 12 = 313 «13 = ai2 + 4 • 13 = 365 Hledané a±s = 365. Poznámka: Z rekurentního vztahu lze v tomto případě snadno získat explicitní vyjádření postupným dosazováním an = An + 4(n - 1) + 4(n - 2) H-----h 8 + 4 + 1. Tuto rovnost lze získat také takto: napíšeme získané rekurentní rovnosti od a,i po an a0 + 4- 1, ai + 4-2, a2 + 4 • 3, a3 + 4 • 4, an-2 + 4 • (n - 1), an_i + 4 • n. a po jejich sečtení odečteme od obou stran součet a\ + a2 + • • • + an-i a dosadíme za a\. Sečtením členů aritmetické posloupnosti pak dostaneme an = 2n{n + 1) + 1 = 2n2 + 2n + 1. Proto je možné vypočítat hledané a 13 také dosazením do tohoto explicitního vyjádření: 013 = 2 • 13 • 14 + 1 = 365. 2. Protože jde o lineární rekurentní formuli třetího řádu s konstantními koeficienty, tvoří posloupnosti, které ji vyhovují, vektorový prostor dimenze 3. Charakteristický polynom je polynom, jehož kořeny jsou kvo-ficienty g / 0 geometrických posloupností vyhovujících této formuli. Protože podmínka qn+3 = 2qn+2 + qn+1 — 2qn je splněna pro každé přirozené číslo n, právě když q3 = 2q2 + q — 2, je charakteristický polynom x3 — 2x2 — x + 2. Přestože jde o polynom stupně 3, kořeny tohoto polynomu najdeme snadno, například uhádnutím některého z kořenů, anebo rozkladem x3 — 2x2—x+2 = (x — 2){x2 — 1) = (x — 2){x— l)(x+l). Tento polynom tedy má jednoduché kořeny —1, 1, 2. Proto je daná posloupnost lineární kombinací posloupností {(—l)n}^1? {1™}^^ a {2n}^=l. Existují tedy čísla u,v,w G C taková, že pro každé n E N platí bn = u- (-l)n + v + w -2n. Čísla u, v, w dostaneme porovnáním hodnot počátečních členů 1 = bi = —u + v + 2w, 0 = b2=u + v + Aw, 4 = 63 = —u + v + 8w. a\ = a2 = a3 = 04 = O-n-1 = drl Řešením této soustavy lineárních rovnic je u = —1, v = —1, w = |. Tím jsme dostali explicitní vyjádření bn. Pro libovolné n G N tedy platí bn = -(-l)n - 1 + \ ■ T = r-1 - 1 - (-l)n. 3. Výsledkem tahu sportky je jistá šestiprvková podmnožina množiny {1,2,..., 49}, přičemž každá z těchto podmnožin má stejnou pravděpodobnost, že bude vylosována. Množina M všech tahů je tedy množina všech šestiprvkových podmnožin této množiny. Nechť N je podmnožina množiny M právě těch tahů, které splňují podmínku úlohy. Pak hledaná pravděpodobnost je rovna j^j. Zřejmě \M\ = (f). Počet prvků množiny N určíme pomocí principu inkluze a exkluze. Pro každé i = 1,2,3 označme Mj podmnožinu množiny M, jejímiž prvky jsou právě ty šestiprvkové podmnožiny množiny {1, 2,... ,49}, ve kterých není žádný prvek z množiny {10«, 10« + 1,..., 10« + 9}. Pak N = M\(M1UM2UM3). Snadno zjistíme, že |Mi| = |M2| = \M3\ = (369). Podobně |Mi fl M2| = |Mi n m3| = |M2 n m3| = (269), |Mi n M2 n m3| = ffl. Princip inkluze a exkluze proto dává \M1UM2UM3\ = ^)-3.^)+3.^)-a). Hledaná pravděpodobnost je proto liVl (469)- 3-(369)+ 3-(269)-C69) |M| (49) Kalkulačkou nebo na počítači lze spočítat, že \N\ _ 5593875 _ 266375 ^_ ^no/ \M\ 13983816 665896 ^u/0.