Diskrétní matematika - cvičení 9. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Určete počet způsobů, jak lze na šachovnici (8x8 polí) postavit bílou a černou věž tak, aby se neohrožovaly (nebyly ve stejném řádku ani sloupci). Příklad _1 Určete počet způsobů, jak lze bílou a černou věž tak, aby se řádku ani sloupci). na šachovnici (8x8 polí) postavit 1 (nebyly ve stejném 1 Řešení Pravidlo součtu: AiU--UAk = Ai H-----h A Príklad _1 Určete počet způsobů, jak lze bílou a černou věž tak, aby se řádku ani sloupci). na šachovnici (8x8 polí) postavit 1 (nebyly ve stejném 1 Řešení Pravidlo součtu: \Ai U • • • U Ak\ = \Aľ\ H-----h \A> Rozdělme rozestavení podle zadání v závislosti na pozici bílé věže: ta může stát na libovolném ze 64 polí, takže k = 64 a pro každý index / je A; množina rozestavení podle zadání, ve kterých je bílá věž na /-tém poli. Zjevně jsou tyto možnosti disjunktní. Kolik je takových rozestavení? Príklad _1 Určete počet způsobů, jak lze bílou a černou věž tak, aby se řádku ani sloupci). na šachovnici (8x8 polí) postavit 1 (nebyly ve stejném 1 Řešení Pravidlo součtu: \Ai U • • • U Ak\ = \Aľ\ H-----h \A> Rozdělme rozestavení podle zadání v závislosti na pozici bílé věže: ta může stát na libovolném ze 64 polí, takže k = 64 a pro každý index / je A; množina rozestavení podle zadání, ve kterých je bílá věž na /-tém poli. Zjevně jsou tyto možnosti disjunktní. Kolik je takových rozestavení? Černá věž může být na libovolném ze zbývajících 7 řádků a libovolném ze zbývajících 7 sloupců, takže \A;\ =7-7, nezávisle na /: Ai U • • • U A54I = 49 H-----h 49 = 64 • 49. 64 x Pravidlo součtu: \Ai U • • • U Ak\ = \Aľ\ H-----h \A> Pravidlo součinu: \A x B\ = |>A| • |6|, tj. pokud činíme dvě nezávislé volby, je počet možností roven součinu. Viděli jsme, že stačí aby počet druhých voleb nezávisel na první volbě, Pravidlo součtu: \Ai U • • • U Ak\ = \Aľ\ H-----h \A> Pravidlo součinu: \A x B\ = |/4| • |6|, tj. pokud činíme dvě nezávislé volby, je počet možností roven součinu. Viděli jsme, že stačí aby počet druhých voleb nezávisel na první volbě, klasicky např. pro permutace: počet všech pořadí utvořených z r?-prvkové množiny rozdělíme podle toho, který prvek je na prvním místě: na druhém místě pak volíme z n — 1 možností (závisle na první možnosti, ale počet možností je nezávislý), atd. Dostaneme samozřejmě n\. Během schůze má vystoupit 8 řečníků. Stanovte počet všech pořadí, v nichž dva předem určení řečníci nevystupují ihned po sobě. Během schůze má vystoupit 8 řečníků. Stanovte počet všech pořadí, v nichž dva předem určení řečníci nevystupují ihned po sobě. Řešení Pravidlo doplňku: pro B C A platí A \ B = A - B Během schůze má vystoupit 8 řečníků. Stanovte počet všech pořadí, v nichž dva předem určení řečníci nevystupují ihned po sobě. Řešení Pravidlo doplňku: pro B C A platí \A \ B\ = \A\ - \B V našem případě spočítáme ta pořadí, ve kterých naopak vystupují dva daní řečníci po sobě, nazvěme je X a Y, můžou tedy v programu být buď v pořadí XY nebo YX. Pro každou z těchto dvou možností z nich udělejme jednoho "dvojřečníka", takže počet takových pořadí bude 2-7!. Protože počet všech pořadí je 8!, hledaný počet je 8! — 2 • 7! = 6 • 7!. Kombinační čísla: Označme (£) počet /c-prvkových podmnožin n-prvkové množiny. Zjevně je počet všch podmnožin r?-prvkové množiny, a těch je 2n, protože lze nezávisle u každého prvku volit, zda do podmnožiny patří, či nikoliv. Kombinační čísla: Označme (£) počet /c-prvkových podmnožin n-prvkové množiny. Zjevně je počet všch podmnožin r?-prvkové množiny, a těch je 2n, protože lze nezávisle u každého prvku volit, zda do podmnožiny patří, či nikoliv. Kombinační čísla: Označme (£) počet /c-prvkových podmnožin n-prvkové množiny. Zjevně je počet všch podmnožin r?-prvkové množiny, a těch je 2n, protože lze nezávisle u každého prvku volit, zda do podmnožiny patří, či nikoliv. Protože • k\ je počet pořadí k prvků z r?-prvkové množiny a ten je roven n • (r? — 1).....(r? — k + 1) = , dostáváme formulku r? n! k\ • (n - /c)! Kombinační čísla: Označme (£) počet /c-prvkových podmnožin n-prvkové množiny. Zjevně je počet všch podmnožin r?-prvkové množiny, a těch je 2n, protože lze nezávisle u každého prvku volit, zda do podmnožiny patří, či nikoliv. Protože • k\ je počet pořadí k prvků z r?-prvkové množiny a ten je roven n • (r? — 1).....(r? — k + 1) = , dostáváme formulku r? n! k\ • (n - /c)! n n-k Kolika způsoby může sportovec umístit 10 různých pohárů do 5 polic, jestliže se na každou polici vejde všech 10 pohárů? Kolika způsoby může sportovec umístit 10 různých pohárů do 5 polic, jestliže se na každou polici vejde všech 10 pohárů? Řešení Označíme-li poháry 0 až 9, můžeme umístění sdělit tak, že budeme postupně svrchu dolů a v rámci poliček zleva doprava říkat čísla pohárů a konce poliček, označme je třeba znakem |. Výsledkem tak může být například: 24||8657|9|103. Zjevně počet umístění je roven počtu takových posloupností, skládajících se z číslic 0 až 9 (každá jednou) a čtyř znaků |. Kolik jich je? Príklad Kolika způsoby může sportovec umístit 10 různých pohárů do 5 polic, jestliže se na každou polici vejde všech 10 pohárů? Řešení Označíme-li poháry 0 až 9, můžeme umístění sdělit tak, že budeme postupně svrchu dolů a v rámci poliček zleva doprava říkat čísla pohárů a konce poliček, označme je třeba znakem |. Výsledkem tak může být například: 24||8657|9|103. Zjevně počet umístění je roven počtu takových posloupností, skládajících se z číslic 0 až 9 (každá jednou) a čtyř znaků |. Kolik jich je? Vyberme prvně místa, kde se vyskytují znaky |, tj. vybereme 4 místa ze 14. Počet takových výběrů je Nezávisle na výběru čtyř pozic pro znak | je počet posloupností roven počtu všech pořadí čísel 0 až 9, tj. 10!. Výsledný počet tak je (^4) • 10! = 141 4! s1 Pro libovolné pevné n £ N určete počet všech řešení rovnice xi+ x2-\-----h xk = n v množině nezáporných celých čísel (kladných celých čísel). Príklad Pro libovolné pevné n 6 N určete počet všech řešení rovnice xi+ x2-\-----h xk = n v množině nezáporných celých čísel (kladných celých čísel) Řešení Příklad je analogií předchozího, kde nerozlišujeme jednotlivé poháry a jde jen o jejich počet, budeme tedy řešení zapisovat ve tvaru posloupností xi x skládajících se z n znaků • a k — 1 znaků |. Opět prvně vybereme k — 1 míst, kam umístíme znaky |, zbytek je pak už ale jednoznačně daný, takže výsledkem je {n\kJi1) — Příklad Pro libovolné pevné n 6 N určete počet všech řešení rovnice xi + X2 H-----h xk = n v množině nezáporných celých čísel (kladných celých čísel). Pro kladná celá čísla převedem úlohu na předchozí - pišme x/ = 1 + y; a nyní jsou y\ nezáporná celá čísla a řešíme rovnici (1 + yi) + (1 + Y2) + • • • + (1 + y/c) = n yi + Y2 H-----h y/c = n - /c a z předchozího víme, že počet řešení je (^~^^t1/c_1) = Určete počet všech řešení soustavy nerovnic 0 < xi < X2 < • • • < Xk < n v množině nezáporných celých čísel (to samé pro ostré nerovnosti). i Príklad Určete počet všech řešení soustavy nerovnic 0 < xi < X2 < • • • < Xk < n v množině nezáporných celých čísel (to samé pro ostré nerovnosti) Řešení Označíme-li rozdíly yi — x\ — 0, y2 = X2 — xi, y/c =x/c-x/c_i,y/c+i = n-xk, 0 yi xi y2 X2 X/c-1 y/c X/c y/c+i pak se jedná o nezáporná celá čísla se součtem n a víme, že yH-----1- y/c+i = n ma řešení. Určete počet všech řešení soustavy nerovnic 0 < xi < X2 < • • • < Xk < n v množině nezáporných celých čísel (to samé pro ostré nerovnosti) Řešení Pro ostré nerovnice dají rozdíly kladná celá čísla a počet řešení tedy je (n~k1)- (Přímo: jde jen o /c-prvkovou podmnožinu množiny {1,... ,n - 1}.) Príklad Na kolik nejvýše oblastí může dělit rovinu n přímek? ■ Na kolik nejvýše oblastí může dělit rovinu n přímek? Řešení Označme tento počet pn, zjevně po = 1. Co se stane přidáním r?-té přímky? Ta protne některé oblasti a každou tak rozdělí na dvě části, počet oblastí pn je tedy oproti pn-i vyšší právě o počet oblastí, které r?-tá přímka protne. Jednotlivé oblasti přímka protne v intervalu, dělícími body jsou pak právě průsečíky s ostatními přímkami. Protože těch je n — 1, je intervalů n a nejvyšší počet oblastí je pak roven (lze jej snadno dosáhnout) Pn = Pn-i + n = • • • Jednotlivé oblasti přímka protne v intervalu, dělícími body jsou pak právě průsečíky s ostatními přímkami. Protože těch je n — 1, je intervalů n a nejvyšší počet oblastí je pak roven (lze jej snadno dosáhnout) pn = p„_i + n = pn-2 + {n - 1) + n = po + 1 + • • • + (n - 1) + n , n-(n + l) + _ 2- Kolika způsoby mohla skončit tabulka první fotbalové ligy (v potaz bereme pouze pořadí), víme-li o ní pouze, že alespoň jeden z týmů z dvojice Ostrava, Olomouc je v tabulce za týmem Brna (ligu hraje 16 mužstev). Príklad Kolika způsoby mohla skončit tabulka první fotbalové ligy (v potaz bereme pouze pořadí), víme-li o ní pouze, že alespoň jeden z týmů z dvojice Ostrava, Olomouc je v tabulce za týmem Brna (ligu hraje 16 mužstev). Řešení Rozdělíme úlohu na několik snazších ■ 9 počet vzájemných pořadí trojice zmíněných týmů - z šesti možných pořadí jsou povoleny právě 4 9 počet vzájemných pořadí zbylých třinácti týmů - nejsou žádná omezení, je jich tedy 13! 9 počet způsobů, jak vybraná dvě vzájemná pořadí (tří a třinácti týmů) dát dohromady - k tomu stačí vybrat, na kterých třech pozicích se umístili zmíněné týmy, to lze způsoby Výsledný počet tak je 4 • 13! • = ^ Určete počet čtyřciferných čísel sestavených z právě dvou cifer. Určete počet čísel menších než 10 tisíc, které mají symetrický ciferný zápis. Určete počet čtyřciferných čísel sestavených z právě dvou cifer. Určete počet čísel menších než 10 tisíc, které mají symetrický ciferný zápis. Opět úlohu rozdělíme na několik jednodušších: • možnosti na vybrání dvou číslic, které se v čísle vyskytují: • (2), ve kterých se nevyskytuje 0 a • g), ve kterých se vyskytuje 0 • počet čísel tvořených vybranými dvěma číslicemi: v prvním případě 24 — 2 (na každé ze čtyř pozic dvě možnosti, minus dvě čísla tvořená pouze jednou ze dvou číslic) a ve druhém případě 23 — 1 (na prvním místě nemůže být nula a je na něj tedy jen jedna možnost) Výsledný počet tak je g) • (24 - 2) + g) • (23 - 1). Príklad Určete počet čtyřciferných čísel sestavených z právě dvou cifer. Určete počet čísel menších než 10 tisíc, které mají symetrický ciferný zápis. Určete počet čtyřciferných čísel sestavených z právě dvou cifer. Určete počet čísel menších než 10 tisíc, které mají symetrický ciferný zápis. Ve druhém případě budou mít čísla jeden z tvarů ABBA, ABA, AA, A, kde zjevně A je libovolná číslice s výjimkou 0 a B je zcela libovolná číslice (může být i stejná jako A). Počet takových čísel tedy je: 9-10 + 9-10 + 9 + 9. Kolika způsoby lze rozdělit 9 děvčat a 6 chlapců do dvou skupin tak, aby každá skupina obsahovala alespoň dva chlapce? Kolika způsoby lze rozdělit 9 masitých a 6 vegetariánských sendvičů do dvou skupin tak, aby každá skupina obsahovala alespoň dva vegetariánské? Kolika způsoby lze rozdělit 9 děvčat a 6 chlapců do dvou skupin tak, aby každá skupina obsahovala alespoň dva chlapce? Kolika způsoby lze rozdělit 9 masitých a 6 vegetariánských sendvičů do dvou skupin tak, aby každá skupina obsahovala alespoň dva vegetariánské? Řešení Budeme vybírat členy první skupiny: děvčat můžeme vzít libovolný počet a možností je 2 =,0J + U+-+\9/' chlapců můžeme vzít pouze počet 2 až 4 a možností je Řešení Budeme vybírat členy první skupiny: děvčat můžeme vzít libovolný počet a možností je + 9 ' chlapců můžeme vzít pouze počet 2 až 4 a možností je 1) + (s) + C Počet rozdělení je tak Budeme vybírat členy první skupiny: masitých sendviču můžeme vzít libovolný počet a možností je 10 = 1 + H-----hl, vegerariánských sendvičů můžeme vzít pouze počet 2 až 4 a možností je 3 = 1 + 1 + 1. Počet rozdělení je tak 10-3. Kolika způsoby je možné koupit 12 balíčků kávy, mají-li v prodejně kávu pěti druhů? Dále tuto úlohu řešte s následujícími modifikacemi: O od každé kávy je třeba koupit aspoň 2 balíčky; O od každé kávy má být koupen sudý počet balíčků; O jedné z káv (např. arabské) jsou k dispozici pouze 3 balíčky. Kolika způsoby je možné koupit 12 balíčků kávy, mají-li v prodejně kávu pěti druhů? Dále tuto úlohu řešte s následujícími modifikacemi: O od každé kávy je třeba koupit aspoň 2 balíčky; O od každé kávy má být koupen sudý počet balíčků; O jedné z káv (např. arabské) jsou k dispozici pouze 3 balíčky. Řešení Ukážeme, že se jedná o koeficient u x ve výrazu (1 + x + x2 + • • • )5, pojďme tedy tento koeficient popsat. Řešení Ukážeme, že se jedná o koeficient u x12 ve výrazu (1 + x + x2 + • • • )5, pojďme tedy tento koeficient popsat. Zjevně po roznásobení vyjdou výrazy tvaru xa • xb • xc • xd • xe = jx^+^+c+d+e 5 kde každý činitel pochází z jedné závorky (1 + x + x2 + • • •), exponenty a, b, c, d, e tedy mohou být libovolná nezáporná celá čísla. Dostaneme tak x12, kdykoliv bude a + b+ c + d + e = 12, vždy s koeficientem 1, takže výsledný koeficient bude kde počet jedniček je roven počtu pětic (a, b, c, c/, e) nezáporných celých čísel se součtem 12. Řešení Koeficient u x12 ve výrazu (1 + x + x2 + • • • )5 je tedy počet pětic (a, b, c, c/, e) nezáporných celých čísel se součtem 12. To je zřejmě počet nákupů ze zadání. Když sečteme geometrickou řadu v závorce, hledaný počet je koeficient u x12 v 1 -x (1-x) 5 ' Úlohu lze vyřešit elementárně - počet možných nákupů n balení, a tedy koeficient u xn, je (n~^4), takže (i - xy 0 + 4\ fl + 4 4 + 4 x + • • • = oo n=0 n+ 4 x n Tento a podobné vzorečky budeme využívat od příště. Řešení Pojďme nyní na jednotlivé modifikace: • od každé kávy aspoň 2 balíčky: chceme a > 2, b > 2 atd., takže analogicky se jedná o koeficient u x12 ve výrazu = X 10 — X (l-x)< • od každé kávy sudý počet balíčků: chceme 2 | a, 2 | b atd., takže analogicky se jedná o koeficient u x12 ve výrazu (l+x2+x4 + ...)5 = (1-X2)5- od jedné z káv jsou k dispozici pouze 3 balíčky: chceme a < 3, takže analogicky se jedná o koeficient u x ve výrazu (1 + x + x2 + x3) • (1 + x + x2 + • • • )4 = 1 + x + x2 + x- 00,0 Od příště se budeme zabývat metodami, které umožní podobné příklady dopočítat do konce. Připomeňte si součet geometrické řady, zejména již použitý vzorec: 1 + x + x2 H----= oo 1 W = —. ^ 1 -x Í7=0 Připomeňte si binomickou větu: k\ (k\ ík\ o ík\ /, /k 0 HiJx+Wx2+'''+Wx'=SUJx"=(1+x) Tyto dvě věty zobecníme a budeme jejich zobecnění používat ke kombinatorickým výpočtům.