1. DU, řešení Cvičení 1.1 Mezi městy A a B vede 5 cest, mezi městy B a C vedou 3 cesty. Kolik existuje navzájem různých cest z A do C přes B? Řešení: Z města A do města B můžeme zvolit cestu pěti způsoby, nezávisle na tom z města B do města C můžeme dojít třemi způsoby. Díky nezávislosti těchto voleb můžeme použít pravidlo součinu, tedy 5 • 3 = 15. Existuje 15 navzájem různých cest z A do C přes B. Cvičení 1.2 Kolika způsoby lze na šachovnici vybrat jedno bílé a jedno černé políčko? Řešení: Standardní šachovnice má 64 políček, polovinu bílých, polovinu černých. Máme tedy 32 možností k výběru bílého políčka, stejně tak máme 32 možností k výběru černého políčka. Tyto výběry jsou na sobě nezávislé, proto použijeme pravidlo součinu a dostáváme 32 • 32 = 1024. Na šachovnici můžeme vybrat jedno bílé a jedno černé políčko 1024 způsoby. Cvičení 1.3 Kolika způsoby lze ze 32 karet vybrat krále a dámu? Řešení: V sadě 32 karet máme čtyři barvy (například ve francouzských kartách srdce, káry, piky a kříže), v každé barvě existuje jeden král a jedna dáma. Máme tedy 4 krále a 4 dámy. Krále mohu z balíčku karet vybrat čtyřmi způsoby, nezávisle na výběru krále mohu vybrat čtyřmi způsoby i dámu. Díky nezávislosti výběrů použijeme pravidlo součinu, tedy 4 • 4 = 16. Krále a dámu můžeme z 32 karet vybrat 16 způsoby. Cvičení 1.4 Kolika způsoby můžeme vybrat jednu souhlásku a jednu samohlásku z písmen daných slov? (a) LAVICE (b) KOLEJ Řešení: Nejprve se podívejme na slovo LAVICE. V tomto slově se nachází tři souhlásky a tři samohlásky. Souhlásku tedy můžeme vybrat třemi způsoby, 32 stejně tak i samohlásku. Výběry souhlásky a samohlásky jsou na sobě nezávislé, pomocí pravidla součinu tedy získáváme 3-3 = 9. Obdobně nalezneme řešení i u slova KOLEJ. V něm máme tři souhlásky a dvě samohlásky, dohromady 3-2 = 6. Jednu souhlásku a jednu samohlásku můžeme vybrat ze slova lavice 9 způsoby a ze slova kolej 6 způsoby. Cvičení 1.5 Na tenisovém turnaji, kde hrál každý hráč s každým právě jednou, se odehrálo 91 zápasů. Kolik se ho zúčastnilo hráčů? Řešení: Zadání nám říká, že organizátoři tenisového turnaje ze všech zúčastněných hráčů vytvořili 91 dvojic tak, že každý hráč hrál s každým hráčem právě jednou. Zřejmě nebylo rozlišováno mezi dvojicemi Berdych-Veselý a Veselý-Berdych, tedy ve vybraných dvojicích nezáleželo na pořadí hráčů. Po převedení do matematického jazyka pořadatelé vytvořili z určitého počtu hráčů 91 dvouprvkových kombinací. G) " « z' ___ = Ol 2!(x-2)! x(x-l) = 2-91 x2 - x - 182 = 0 Kořeny této kvadratické rovnice jsou čísla —13 a 14. Rozhodně se turnaje nezúčastnilo —13 hráčů, jediným správným výsledkem je proto 14. Tenisového turnaje se zúčastnilo 14 hráčů. Cvičení 1.6 Kolik hráčů se zúčastnilo šachového turnaje, jestliže každý hráč hrál s každým právě jednou a bylo odehráno 21 partií? Řešení: Toto cvičení je analogií cvičení předchozího. Vybíráme k sobě dvojice hráčů a samozřejmě nerozlišujeme dvojice Kasparov-Kramnik a Kramnik-Kasparov. Všichni účastníci šachového turnaje se tedy dají rozdělit do 21 dvojic, v nichž nezáleží na pořadí hráčů, tedy lze z jejich počtu vytvořit 21 dvouprvkových kombinací. G) - 21 *! = 21 2!(a;-2)! x(x-l) = 2-21 x2 - x - 42 = 0 Kořeny dané kvadratické rovnice jsou čísla —6 a 7. Záporný počet hráčů nedává smysl, výsledkem je proto číslo 7. Šachového turnaje se zúčastnilo 7 hráčů. 33 Cvičení 1.7 Máme 28 kostek domina. Každá kostka má dvě políčka, na každém políčku je O až 6 teček a kostky domina jsou navzájem různé). (a) Kolik kostek domina má součet teček v obou polovinách 7 nebo 11? (b) Kolika způsoby můžeme z 28 kostek domina vybrat dvě tak, abychom je mohli přiložit k sobě? Řešení: Je dobré si uvědomit, že v naší sadě kostek domina neexistují dvě různé kostky s políčky 5-3 a 3-5, taková kostka je pouze jedna (tyto kostky by byly ve skutečnosti stejné). Řešme nyní jednotlivé varianty: (a) Součet 7 na políčkách dominové kostky můžeme získat pouze třemi kombinacemi čísel: 1 + 6; 2 + 5; 3 + 4. Součet 11 nalezneme jedině na kostce 5 + 6. Součet teček na dominové kostce je 7 nebo 11 u 4 kostek. (b) Představme si situaci, kdy můžeme kostky přiložit k sobě (kostky mají na jedné straně stejný počet teček). Označme si počty teček na jedné kostce a-b (na jedné polovině a teček, na druhé b teček). K takové kostce můžeme jistě přiložit kostku b-c. Kolik existuje takových dvojic kostek? Nejprve předpokládejme, že čísla a, b, c jsou po dvou různá. Za číslo a můžeme dosadit 7 různých hodnot (0,1,... ,6), za číslo b už pouze 6 hodnot (aby bylo různé od a), číslo c volíme ze zbylých hodnot. Tyto volby jsou navzájem nezávislé, po využití pravidla součinu tedy zjistíme, že takových dvojic kostek můžeme nalézt 7-6-5 = 210. Při výpočtu jsme ale rozlišovali dvojice kostek a-b b-c a c-b b-a, výsledek tedy musíme vydělit dvěma a získáváme 105 dvojic. Může nastat i situace, kdy nebudou hodnoty a, 6, c po dvou různé? Ano, můžeme vytvořit dvojici z kostek a-b b-b. Pro určení počtu těchto dvojic opět využijeme pravidlo součinu, přičemž za číslo a mohu volit ze 7 hodnot, číslo b pak z 6 hodnot: 7 • 6 = 42. Popsali jsme dvě odlišné situace, které mohou nastat, počet všech dvojic k sobě patřících kostek domina je tedy součtem výsledných počtů v jednotlivých situacích. 105 + 42 = 147 Dvě kostky, které lze přiložit k sobě, můžeme vybrat 147 způsoby. Cvičení 1.8 V balíčku 32 různých karet je 16 karet červených (srdce a káry) a 16 černých (piky a kříže). Kolika způsoby můžeme z balíčku vybrat pětici karet tak, aby mezi nimi bylo červených karet více než černých? Řešení: Vybíráme-li pětici karet, nezáleží nám na pořadí, ve kterém jsme jednotlivé karty vybrali (klidně jsme mohli všechny karty vybrat najednou), jedná se o pětiprvkové kombinace z 32 karet. Pokud má být červených karet více než černých, mohou nastat následující situace: 5 červených; 4 červené a 1 černá; 3 červené a 2 černé. Jsou to tři odlišné situace, vyřešíme tedy každou z nich 34 samostatně a následně využijeme pravidlo součtu. V první situaci vybíráme 5 karet z celkového počtu 16 červených karet, tedy pětiprvkovou kombinaci z 16 prvků (g6). V druhé situaci vybíráme 4 karty z 16 červených karet a (nezávisle na výběru červených karet) 1 kartu z 16 černých, tedy (x46) • (1]6). Analogicky získáme počet možných výběrů 3 červených a 2 černých karet. Dohromady dostáváme + Q6) • (\6) + • (™) = 100688. pětici karet můžeme vybrat 100 688 způsoby. Cvičení 1.9 Kolika způsoby lze rozdělit zlatou, stříbrnou a bronzovou medaili mezi 19 závodníků? Řešení: Můžeme začít zlatou medailí: kolika způsoby lze vybrat závodníka, kterému ji udělíme? Zřejmě máme 19 možností. Pro stříbrnou medaili už máme možností pouze 18 (nositel zlaté medaile nemůže být i nositelem stříbrné) a pro bronzovou nám zbývá 17 možných závodníků. Jednotlivé výběry na sobě byly nezávislé, využijeme tedy pravidlo součinu a získáváme 19 • 18 • 17 = 5 814. Medaile lze mezi 19 závodníků rozdělit 5 814 způsoby. Cvičení 1.10 Kolika způsoby lze z 25 členů společnosti vybrat předsedu, místopředsedu, tajemníka a pokladníka? Řešení: Postup je analogický předchozímu cvičení. Nejdříve vybereme předsedu, na toto místo máme 25 kandidátů. Následně zvolíme místopředsedu, počet kandidátů je ovšem 24, protože pro zachování demokracie smí každý člen společnosti zastávat nejvýše jednu funkci. Pro výběr tajemníka zbývá 23 možností a pokladníka volíme z 22 členů. Jednotlivé volby jsou na sobě nezávislé, výsledek tedy získáme s pomocí pravidla součinu 25 ■ 24 • 23 • 22 = 303 600. do daných funkcí můžeme zvolit členy 303 600 způsoby. Cvičení 1.11 Kolika způsoby lze srovnat do poličky 20 různých knih? (Knihy zaberou beze zbytku celou poličku.) Řešení: Knihy v poličce přesouváme, hledáme počet jejich různých pořadí, matematicky řečeno, hledáme počet všech jejich permutací. 20! = 2 432 902 008176 640 000. Knihy lze do poličky srovnat 2 432 902 008176 640 000 způsoby. Cvičení 1.12 V rovině je dáno několik přímek, z nichž žádné dvě nejsou rovnoběžné a žádné tři se neprotínají v jediném bodě. Kolik přímek je dáno, pokud tak vznikne 55 různých průsečíků? Řešení: Jestliže žádné dvě přímky nejsou rovnoběžné a žádné tři přímky se neprotínají v jediném bodě, pak se každé dvě přímky protínají v jednom bodě, tvoří 35 jeden průsečík. Jinak řečeno, existuje tolik průsečíků, kolik existuje dvojic přímek. Převedeme-li tvrzení do kombinatorického jazyka, ze všech přímek lze vytvořit 55 dvouprvkových kombinací. G) x\ 2\{x-2)\ x(x — 1) x2 - x - 110 Kořeny této rovnice jsou čísla —10 a 11. Nemá smysl uvažovat —10 přímek, máme tedy jediné řešení. v rovině je dáno 11 přímek. Cvičení 1.13 Kolik různých tritonových popěvků lze vytvořit z osmi tónů? Řešení: Zřejmě tóny popěvku musí být po dvou různé, jinak bychom nemohli hovořit o třítónovém popěvku. První tón popěvku můžeme vybrat osmi způsoby, pro druhý tón zbylo už pouze sedm možností a poslední tón volíme z šesti zbývajících tónů. Volby tónů (nezáleží nám na libozvučnosti) jsou na sobě nezávislé, proto použijeme pravidlo součinu a dostáváme 8 • 7 • 6 = 336. Z osmi tónů lze vytvořit 336 tritonových popěvků. Cvičení 1.14 Kolika způsoby lze na šachovnici 8x8 rozmístit věž, koně, krále a dámu? Řešení: Na šachovnici je 64 políček, na které figurky postupně rozmístíme. Na jednom políčku smí stát nejvýše jedna figurka. Věž můžeme umístit na kterékoli políčko, máme tedy 64 možností. Následně umístíme koně na nějaké volné políčko, těch je 63, pro krále nám zbývá 62 možností umístění a pro dámu 61. Jednotlivá umístění jsou na sobě nezávislá, pomocí pravidla součinu tedy získáváme 64 • 63 • 62 • 61 = 15 249 024. Figurky lze na šachovnici rozmístit 15 249 024 způsoby. Cvičení 1.15 Kolika způsoby lze ze třídy o 30 žácích vybrat trojici nástěn-kář, šatnář a pokladník? (Každé dítě má jen jednu „funkci".) Řešení: Volme postupně žáky do funkcí. Nástěnkáře můžeme vybírat z 30 žáků, šat-náře z 29 žáků (jeden žák už je nástěnkář) a pokladníka z 28 žáků. Výběry jsou na sobě nezávislé, dohromady tedy 30 • 29 • 28 = 24 360. Trojici žáků můžeme vybrat 24 360 způsoby. = 55 = 55 = 2-55 = 0 36 Cvičení 1.16 Kolika způsoby lze sestavit tritonovy akord z osmi různých tónů? Řešení: V třítónovém akordu neexistuje pořadí jednotlivých tónů, všechny se hrají zároveň, zajímá nás pouze kombinace tří tónů. (3) = 56 tritonovy akord z osmi různých tónů lze sestavit 56 způsoby. Cvičení 1.17 Kolika způsoby lze v krabičce uspořádat 12 pastelek? Řešení: V krabičce měníme pořadí pastelek, vytváříme jejich různé permutace. 12! = 479001600 Pastelky lze uspořádat 479 001600 způsoby. Cvičení 1.18 Kolika způsoby si můžete v ruce do vějíře seřadit 8 karet, které Vám byly rozdány? Řešení: Stejně jako v předchozím příkladě máme určit počet různých pořadí 8 karet, počet jejich permutací. 8! = 40320 Karty lze seřadit 40 320 způsoby. Cvičení 1.19 Kolik existuje devítimístných telefonních čísel, v nichž se nevyskytuje nula a žádná cifra se neopakuje? Řešení: Nesmí-li se mezi ciframi vyskytovat nula, můžeme použít 9 různých cifer (1,2,..., 9). Jelikož se žádná cifra neopakuje, jsme nuceni využít všech devět povolených cifer a hledáme pouze jejich různá pořadí (permutace). 9! = 362 880 Existuje 362 880 čísel splňujících zadání. Cvičení 1.20 Kolika způsoby lze na šachovnici rozestavit čtyři stejné pěšáky? Řešení: Pěšáky nemůžeme rozlišit, proto nám nezáleží na pořadí vybraných políček jako ve cvičení 1.14, ale vybíráme najednou čtveřici políček šachovnice. (644) = 635376 Čtyři stejné pěšáky lze rozestavit 635 376 způsoby. 37 Cvičení 1.21 Kolika způsoby lze ze třídy o 30 žácích vybrat 6 žáků pro volejbalový turnaj? (Na výkonnosti nezáleží.) Řešení: Zapomeňme na hodiny tělocviku, kdy nám na pořadí výběru hráčů záleželo. V této situaci jde pouze o to, zda daný žák vybraný byl, vybíráme tedy kombinace 6 žáků z 30. (36°) =593 775 žáky na turnaj lze vybrat 593 775 způsoby. Cvičení 1.22 Kolika způsoby lze vybrat 8 karet z 32? Řešení: Danou úlohu je možné pojmout různými způsoby. Prvním z nich je takový, že záleží na pořadí tahu karet, například pokud karty rozdáváme osmi hráčům. Pak bychom hledali počet všech osmiprvkových variací z 32 prvků. 32 • 31 • 30 • • • • 25 = 424097856 000 Nezáleží-li na pořadí výběru karet, hledáme počet osmiprvkových kombinací z 32. (382) = 10 518 300 Karty lze vybrat 424 097 856 000 způsoby, pokud záleží na pořadí výběru, nebo 10 518 300 způsoby, když na pořadí výběru nezáleží. Cvičení 1.23 Určete, kolik různých „slov" vznikne záměnou pořadí písmen slov: (a) POPOCATEPETL (b) ABRAKADABRA (c) ACAPULCO (d) ACONCAGUA Řešení: Záměnou pořadí písmen zřejmě získáváme jejich různé permutace. Musíme si však dát pozor, že ne každou záměnou získáme nové „slovo" - zaměníme-li například ve variantě (a) první a třetí písmeno, slovo zůstane stejné. Počet všech permutací písmen musíme tedy vydělit počtem permutací stejných písmen (to je vzorec pro určení počtu permutací s opakováním). (a) Určeme si četnost každého písmene ve slově POPOCATEPETL: 3xP, 2x0, lxC, lxA, 2xT, 2xE a lxL. Počet písmen ve slově je 12, jejich počet permutací dělíme počty permutací jednotlivých písmen. 3!*2!*2!*2! — ^ 979 200• záměnou pořadí písmen vznikne 9 979 200 různých „slov". 38 (b) Určeme si četnost každého písmene ve slově ABRAKADABRA: 5xA, 2xB, 2xR, lxK a lxD. Počet písmen ve slově je 11, jejich počet permutací dělíme počty permutací jednotlivých písmen. m = 83160. záměnou pořadí písmen vznikne 83160 různých „slov". (c) Určeme si četnost každého písmene ve slově ACAPULCO: 2xA, 2xC, lxP, lxU, lxL a 1x0. Počet písmen ve slově je 8, jejich počet permutací dělíme počty permutací jednotlivých písmen. 2^r = 10080. záměnou pořadí písmen vznikne 10 080 různých „slov". (d) Určeme si četnost každého písmene ve slově ACONCAGUA: 3xA, 2xC, 1x0, lxN, lxG a lxU. Počet písmen ve slově je 9, jejich počet permutací dělíme počty permutací jednotlivých písmen. ^ = 30240. záměnou pořadí písmen vznikne 30 240 různých „slov". Cvičení 1.24 Necht jsou dána písmena a, b, c, d, e, f, g. (a) Kolik „slov" o pěti písmenech se z nich dá sestavit? (b) Kolik lze takových „slov" sestavit, pokud se písmena nesmí opakovat? Řešení: (a) Jednotlivá písmena se ve „slovech" mohou vyskytovat vícekrát, proto pro volbu každého z pěti písmen máme 7 možností, volby písmen jsou na sobě nezávislé (jedná se o variace s opakováním). 7-7-7-7-7 = 75 = 16807 z písmen lze sestavit 16 807 „slov". (b) Jestliže se písmena nesmí opakovat, můžeme první písmeno zvolit 7 způsoby, druhé písmeno 6 způsoby (jedno písmeno už je zakázané) a tak dále, přičemž jednotlivé volby jsou na sobě nezávislé (variace bez opakování) . 7-6-5-4-3 = 2520 z písmen lze sestavit 2 520 „slov" bez opakování písmen. Cvičení 1.25 Kolika způsoby lze darovat 5 různých knížek třem různým lidem, máme-li alespoň S kusy každé knížky a dostane-li každý člověk jednu knihu? Řešení: Postavme si tři lidi do řady a postupně jim dávejme knížky - pro každého máme pět možností výběru a volby knih jsou na sobě nezávislé, tedy 53 = 125. Knížky lze darovat 125 způsoby. 39 Cvičení 1.26 Kolika způsoby si může 15 dětí ve výtvarném kroužku vybrat, které ze tří zvířátek budou malovat? (Každý bude malovat jedno zvířátko, mohou všichni malovat to stejné.) Řešení: Každé dítě má tři možnosti výběru, přičemž výběry jednotlivých dětí jsou na sobě nezávislé, proto existuje 315 = 14 348 907 výběrů. děti si mohou vybrat zvířátka 14 348 907 způsoby. Cvičení 1.27 Kolik různých trojic čísel může padnout při hodu třemi stejnými kostkami? Řešení: Jednou z možností řešení daného cvičení je systematické vypsání všech možných kombinací. Na úlohu se však můžeme dívat i jako na kombinace s opakováním, neznáme-li vzorec, můžeme si jej jednoduše odvodit. Je třeba si uvědomit, že kostky jsou stejné. Přiřazujme k jednotlivým počtům ok kostky, tedy přiřazujme kostky do pomyslných přihrádek. Přepážek mezi těmito přihrádkami je pět (nerozlišitelných), kostky jsou tři. Nechrne mezi sebou permutovat těchto 8 prvků, získáme gngj = 56. může padnout 56 různých trojic čísel. Cvičení 1.28 Kolika způsoby lze najednou vybrat 8 karet z 32 karet čtyř barev, pokud nám záleží pouze na barvě karty, nikoliv na její hodnotě? Řešení: Hledáme kombinace osmi karet čtyř možných barev s možností opakování barev, přičemž karet každé barvy máme dostatečné množství. Vzorec pro výpočet lze odvodit stejně jako v předchozím cvičení, do čtyř přihrádek symbolizujících různé barvy (3 stejné přepážky) přiřazujeme jednotlivé karty. 8!-3! — 100 Karty lze vybrat 165 způsoby. Cvičení 1.29 Kolika způsoby lze ze sáčku, v němž je 5 kuliček zelených, 4 modré, 3 červené a 7 žlutých vybrat trojici kuliček? Řešení: Kuličky jednotlivých barev od sebe nelze rozlišit, hledáme tedy kombinace tří kuliček, u nichž rozlišujeme pouze jejich barvu (může být taženo více kuliček stejné barvy, od každé barvy máme dostatečné množství kuliček). Úlohu lze vyřešit buďto výčtem všech možností, nebo podobně jako v předchozím cvičení vložme každou z trojice kuliček do přihrádky symbolizující její barvu (mezi přihrádkami jsou 3 stejné přepážky) a nechrne mezi sebou permutovat přepážky a kuličky. 6! — on 3!-3! — ^u Trojici kuliček lze vybrat 20 způsoby. 40 2. DU, řešení Cvičení 2.1 Vypočtěte: (a) 8! (b) (t) (c) (g) Řešení: Dosazením získáváme (a) 40 320; (b) 111 930; (c) 677 040. Cvičení 2.2 Ve třídě je 13 chlapců a 15 dívek. Kolika způsoby z nich lze vytvořit šestičlenné družstvo takové, aby v něm bylo alespoň tolik dívek, jako chlapců? Řešení: Má-li být v družstvu alespoň tolik dívek, kolik chlapců, máme čtyři možnosti skladby s ohledem na pohlaví - 3 dívky a 3 chlapci, 4 dívky a 2 chlapci, 5 dívek a 1 chlapec, nebo 6 dívek. Pro každou z těchto možností vypočítáme počet možných voleb, výsledné počty poté sečteme. V prvním případě vybíráme trojici z 15 dívek a nezávisle na tomto výběru trojici ze 13 chlapců, možností výběru je (g5) • (g3). Stejným způsobem určíme počet možných družstev i pro zbylé případy a jednotlivé počty sečteme. (?) • (?) + (?) • (?) + (?) • (?) + (?) = 280644 Družstvo lze vytvořit 280 644 způsoby. Cvičení 2.3 Kolika způsoby lze na šachovnici rozestavit 8 věží tak, aby se navzájem neohrožovaly? Řešení: Dle pravidel šachů věž ohrožuje figurky stojící ve stejném sloupci nebo řádku. Vždy, když vybereme políčko pro jednu věž, „zakážeme" všechna políčka v tomtéž řádku i sloupci. Po umístění sedmé věže nám zůstane pouze jedno volné „nezakázané" políčko pro poslední věž. Každé další možné umístění 8 věží je některou permutací řádků (nebo sloupců) šachovnice, kterých existuje 8! = 40320. věže můžeme umístit 40 320 způsoby. Cvičení 2.4 Kolika způsoby lze 26 znakům přiřadit 26 různých zvuků? Uvedie odhad. 41 Řešení: Zafixujme si pořadí zvuků a k nim hledejme různá pořadí znaků. Jejich počet je 26! = 4,03-1026. Znaky lze ke zvukům přiřadit přibližně 4,03 • 1026 způsoby. 42 Cvičení 2.5 Kolika způsoby lze 26 znakům přiřadit 26 různých zvuků, víme-li, kterých 6 znaků patří samohláskám? Uveďte odhad. (a) Víme konkrétně který znak patří které samohlásce. (b) Víme, kterých 6 znaků patří samohláskám, nevíme však, který znak patří které samohlásce. Řešení: (a) Znaky patřící samohláskám jsou dané, zbývá nám pouze spočítat počet přiřazení znaků souhláskám. Zafixujme si pořadí 20 souhlásek a hledejme k nim různá pořadí znaků patřícím souhláskám. 20! = 2,43 • 1018 Znaky lze ke zvukům přiřadit přibližně 2,43 ■ 1018 způsoby. (b) Zafixujme si pořadí 6 samohlásek a k nim hledejme různá pořadí znaků patřících samohláskám (různých pořadí je 6!). Stejně tak určeme nezávisle na pořadí samohlásek počet přiřazení zbylých 20 znaků a zvuků. 6!-20! = l,75-1021 Znaky lze ke zvukům přiřadit přibližně 1,75 ■ 1021 způsoby. Cvičení 2.6 Kolika způsoby lze 26 znakům přiřadit 26 různých zvuků, známe-li znaky pro 4 z 6 samohlásek (víme, který znak patří které samohlásce) a pro 13 z 20 souhlásek (víme, který znak patří které souhlásce)? Řešení: Zbývá nám přiřadit znaky k 7 souhláskám a 2 samohláskám, dohromady k 9 zvukům, to uděláme podobně jako v předchozích cvičeních. 9! = 362 880 Znaky lze ke zvukům přiřadit 362 880 způsoby. Cvičení 2.7 Sedm dívek tančí v kruhu. Kolika různými způsoby mohou být v kruhu seřazeny? Řešení: Nejdříve určíme počet různých pořadí dívek v řadě, těch je 7!. Rozdíl mezi řadou a kruhem je takový, že u kruhu nelze určit začátek - každou ze 7! řad máme tedy v počtu kruhů započítanou sedmkrát. Proto získáváme 7! : 7 = 720 různých pořadí v kruhu. dívky mohou být seřazeny 720 způsoby. Cvičení 2.8 Kolik různých náhrdelníků je možno sestavit ze 7 různých korálků? Řešení: Úloha je velmi podobná předchozí úloze, jediným rozdílem je, že náhrdelník můžeme i přetočit (to u dívek nebylo možné, tančily by hlavou dolů). Dva různé náhrdelníky lišící se pouze o přetočení považujeme za jeden, proto různých náhrdelníků bude poloviční počet kruhů dívek z předchozího příkladu. fy =360 Lze sestavit 360 různých náhrdelníků. 43 Cvičení 2.9 Porovnejte: 152! + 151! a 150! + 153! Řešení: 152! + 151! 150! + 153! 150!(152 • 151 + 151) 150!(1 + 153 • 152 • 151) 150! -23104 < 150! -3 511657 Cvičení 2.10 Seřaďte dle velikosti následující kombinační čísla: (*) (\572) (V (ir) (c) ffl Řešení: (a) fi?) (b) fi?) = (\572)+© (C) (135) = (l52-135) = ( 17 ) /152\ _ /152\ ^ fl53^ KYJ ) ~ U35J ^ U7 ) Cvičení 2.11 Vypočtěte: (435) Řešení: (435) = 3T§! = = 15 • 22 • 43 = 14190 Cvičení 2.12 Vypočtěte: (JJ) Řešení: (es) = bsSi = Z2^T5 = 3 • 71 • 70 • 69 = 1028 790 Cvičení 2.13 Sečtěte: g) + g) + g) + g) + Q Řešení: (3) + (3) + (3) + (3) + (D = 3TŠ! + 3TIÍ + 3T2l + 3T3T + ŠTi! = = i + f + ¥ + W + W = 1+4+10+20+35 = 70 Cvičení 2.14 Sečtěte: g) + g) + Q + g) + g) Řešení: (5) + (5) + (5) + (5) + (5) = 5RJ! + ŠTÍT + + 5T3T + 5FÍ! = = i+ f + ¥ + W + = 1 + 6 + 21 + 56 + 126 = 210 44 Cvičení 2.15 Vyjádřete jedním kombinačním číslem a vyčíslete: (*) O + 0 o>) (?) + (?) (c) (?) + (?) Řešení: (a) ffl + ffl = (?) + ffl = (?) = 210 00 (?) + (?) = (?) + (?) = (?) = 220 (c) (?) + (?) = (?) = ! 716 Cvičení 2.16 Vypočtěte: S\, (42), (g) Řešení: 8! = 40320 (42) = ^ = 42-441342039 = 7-41 • 10 • 39 = 111930 (65) = ^ = 65-644^3 62 = 65 • 8 • 21 • 62 = 677040 Cvičení 2.17 Zjednodušte: ^ - %++3^ -Řešení: = n2 + 3n + 2 - (n + 2) - (n2 + n) = n Cvičení 2.18 Dokažte: nl + (n- l)\n2 = (n + 1)! Řešení: Upravujme postupně levou stranu n! + (n - l)!n2 = n! + n!n = n!(l + n) = (n + 1)! Cvičení 2.19 Sečtěte: ^ - 2^§ + ^ Řešení: ^-2^ + J^y = (n + 2)(n + l)-2(n + l)n + n(n-l) = = n2 + 3n + 2 - 2n2 - 2n + n2 - n = 2 Cvičení 2.20 Najděte všechna n € N, pro něž ptóí": O (:::)- 45 Řešení: (n-l)! + (n-2)! _A (n-3)!-2! (n-4)!-2! (n-l)(n-2) (n-2)(n-3) 2 2 (n-l)(n-2) + (n-2)(n-3) =8 re2 - 3n + 2 + n2 - 5n + 6 =8 2n2 - 8n =0 2n(n - 4) =0 V kombinačním čísle se nesmí vyskytovat záporná čísla, proto nemá rovnice pro n = 0 smysl a jediným řešením je n = 4. Cvičení 2.21 Zjednodušte: - - Řešení: ^lj|-S-Ní = (P+l)P-(P + 5)-(P-5)(p-6) = = p2+p-p-5-p2 + llp-30 = lip-35 46 3. DU, řešení Cvičení 3.1 Rozviňte podle binomické věty: (| — i)s Řešení: Připomeňme rovnosti i2 = —1; i3 = —i; z4 = 1; i5 = i. (M)V-C)(ž)V+(^^ Cvičení 3.2 Rozviňte podle binomické věty: (—i + |)7 Řešení: Řešíme analogicky předchozímu cvičení, zadání můžeme upravit na (| — i) Cvičení 3.3 Užitím binomické věty dokažte, že výraz 40n — 8n — 5n + 1 pro každé n dělitelný číslem 28. Řešení: 28 28 28 28 28 28 28 28 40n - 8n - 5n + 1 8n(5n - 1) - (5n - 1) (5n - l)(8n - 1) ((4 + l)n-l)((7+l)"-l) (4« + 4"-1 + ... + 4 + 1 _ i)(7« + r1'1 + • • • + 7 + 1 - 1) (4» + 4"-1 + ... + 4)(7« + -1----+ 7) 4(4n"1 + 4n"2 • ■ • + l)7(7n"1 + 7n"2 + • • • + 1) 28(4n_1 + 4n"2 • • ■ + l)(7n-1 + 7n_2 + ••• + !) 47 Cvičení 3.4 Užitím binomické věty dokažte, že výraz 42n — 7™ — 6n + 1 je pro každé n dělitelné číslem 30. Řešení: 30 30 30 30 30 30 30 30 42" _ 7" _ 6n + 1 7n(6n - 1) - (6n - 1) (6n — l)(7n - 1) ((5 + l)"-l)((6 + l)' -n—1 1) n-1 (5n + 5n_1 + • • • + 5 + 1 - l)(6n + 6n_1 + • • • + 6 + 1 - 1) (5n + 5n-1 + --- + 5)(6n + 6' bib71'1 + 5 30(5 n-1 n-1 n—1 _|_ gn—2 +1)6(6; .. + l)(6n-i + 6n"* + ••• + !) + • ■ • + 6) i""2 + • • • + 1) ra-2 Cvičení 3.5 Zdůvodněte(vlastními slovy), proč platí následující kombinatorické identity: (*) (Z) = L-k) w G) = K)+(V) ^2"=(s) + (í) + (5)+...+(b:1) + o p*; o = (s) - (?) + G) - - + (-í)"-1^) + (-i)-CD Řešení: (a) Každý řádek Pascalova trojúhelníku je symetrický. Po rozepsání kombinačního čísla na pravé straně získáváme _raj_ _ n! _ (n\ (n-fc)!(n-(n-fc))! — (n-fe)!fc! — \k) (b) Právě popsaným způsobem tvoříme v Pascalově trojúhelníku každý další řádek. Dokažme si platnost rovnosti: (n—l\,(n-l\ _ _(n—] U-l^l k ) — (fc-l)!(ra-l (n-1)' (n-1)! (fc-l))M fc!(n-l-Jfc)! — (fc-l)!(n-fe)!^fe!(n-fe-l)! (n-1)! _ (ra-l)!fc+(n-l)!(ra-fc) _ (n-l)\(k+n-k) _ n\ _ (n\ ~ k\{n-k)\ ~ k\(n-k)\ ~ k\(n-k)\ ~ \k) (c) Přepíšeme-li 2n = (1 + l)n, získáváme po rozvinutí podle binomické věty pravou stranu zadané rovnosti. (d*) Přepíšeme-li 0 = 0n = (1 —l)n, získáváme po rozvinutí podle binomické věty pravou stranu zadané rovnosti. Cvičení 3.6 Dokažte, že platí: (a) l + 2 + --- + m= (b) l-2 + 2-3 + 3-4+-+m-(m+l) = m(m+l)(m+2) Pokud vás nenapadne jiné řešení, dokažte alespoň matematickou indukcí. 48 Řešení: (a) Lze konstatovat, že pravou stranu rovnosti získáme dosazením do vzorce pro součet prvních n členů aritmetické posloupnosti. Proveďme důkaz platnosti vzorce: Nechť m je sudé číslo. Pak lze všechny sčítance rozdělit do dvou sloupců o stejném počtu řádků následovně: 1 m 2 m- 1 3 m-2 m m 2 2+L Řádků je y, v každém z nich je součet roven m + 1, sečtením řádků získáváme !»Í!»±íl. Nechť m je liché číslo. Abychom mohli užít stejnou konstrukci, jakou jsme použili u sudých čísel, odeberme číslo m. V řádku vedle 1 tedy bude m — l a součet každého řádku bude m. Počet řádků je ídy^, jejich součet vyjádříme jako (m~1)m +m = ĽÉĽLtU Tím je důkaz dokončen. (b) Druhou variantu dokážeme matematickou indukcí. Ověřme prom = l:L = l- 2 = 2P=^ = 2 Předpokládejme, že rovnost platí pro m — 1 a z předpokladu dokažme platnost pro m: L = l- 2 + 2- 3 + 3- 4H-----\-{m—ľ)-m + m-(m + ľ) = ("^M"*1) + + m • (m + 1) = m(m+1Km-1+3 = m(m+l)(m+2) _ p Cvičení 3.7 Kolika způsoby můžeme přeskládat písmena slova (a) TIKTAK (b) TARTAR tak, aby nikdy nestála vedle sebe stejná písmena? Řešení: (a) Využijeme princip inkluze a exkluze: od celkového počtu přeskládání písmen odečteme ta přeskládání, v nichž stojí vedle sebe jedna dvojice písmen (T, respektive K) a přičteme přeskládání, v nichž jsou vedle sebe dvojice T i K. Celkový počet přeskládání určíme jako permutaci s opakováním: • Má-li být vedle sebe dvojice písmen T, můžeme si tuto dvojici „slepit" a považovat ji za jeden znak, počet všech takových přeskládání je || (stejný počet získáme pro dvojici písmen K, výraz proto vynásobíme dvěma). Mají-li být vedle sebe písmena T i písmena K, opět dvojice stejných písmen „slepíme" a považujeme zajeden znak, počet takových přeskládání určíme jako permutaci čtyř různých prvků. J>]__2-51-1-41 — 84 2!-2! z ^-t-^. — d písmena slova TIKTAK lze přeskládat 84 způsoby. 49 (b) Opět využijeme princip inkluze a exkluze: od celkového počtu přesklá-dání písmen odečteme ta přeskládání, v nichž stojí vedie sebe jedna dvojice písmen (dvojice T, dvojice A, nebo dvojice R), přičteme přeskládání, v nichž stojí vedle sebe dvě dvojice písmen (dvojice T a A, dvojice A a R, nebo dvojice T a R) a odečteme přeskládání, v nichž stojí vedle sebe všechny tři dvojice písmen. Počet všech přeskládání písmen slova TARTAR je počet všech permutací s opakovaním 2, ®j 2!. Bude-li jedna dvojice stejných písmen „slepena" a považována zajedno písmeno, bude počet přeskládání . Toto bude platit pro dvojici písmen T, dvojici písmen A i dvojici písmen R, proto lomený výraz vynásobíme třemi. Následně určeme počet přeskládání písmen, v nichž budou stát vedle sebe (budou „slepené") dvě dvojice písmen. Pokud budeme každou ze spojených dvojic považovat za jeden znak, získáme ||, přičemž tento výraz opět vynásobíme třemi, protože mohou být tři různé dvojice „slepených" písmen: TA, AR, TR. Nakonec uvažujme počet přeskládání, v nichž každou ze tří dvojic stejných písmen „slepíme". Dostáváme tak tři různé nové znaky, počet jejich permutací je 3!. _6!__o . _5!_ , o . 4! _ o| _ on 2!-2!-2! ° 2!-2! ^ ° 2! o. — ou písmena slova TARTAR lze přeskládat 30 způsoby. Cvičení 3.8 Určete součet všech pěticiferných čísel, která lze složit z číslic 1, 2, 3, 4, 5 tak, že každou číslici použijeme právě jednou. Řešení: Určeme nejdříve počet těchto čísel. Protože se mezi ciframi nevyskytuje 0, můžeme je mezi sebou jednoduše permutovat a získáme tak 5! = 120 pěticiferných čísel. Podíváme-li se na ně blíže, zjistíme, že na místě jednotek se vyskytují jednotlivé cifry stejně často, konkrétně se zde vyskytuje každá z cifer 1,2,... 5 čtyřiadvacetkrát. Stejně tomu bude i na místě desítek, stovek a dalších. Součet cifer na každém z míst (jednotky, desítky,...) je 24 - (1 + 2 + 3 + 4 + 5) = 360. Chceme-li určit součet všech daných pěticiferných čísel, sečteme si součty jednotek, desítek a tak dále vždy vynásobený příslušnou hodnotou. 1 • 360 + 10 • 360 + 100 • 360 + 1000 • 360 + 10000 • 360 = 3999 960 Součet pěticiferných čísel je 3 999 960. Cvičení 3.9 Kolik existuje deseticiferných čísel, v nichž se číslice neopakují? Řešení: V zadaných číslech se zřejmě musí vyskytovat každá cifra 0,1,... 9 právě jednou. Protože mají být vzniklá čísla deseticiferná, nesmí se na prvním místě objevit nula. Určeme tedy počet čísel jako počet všech permutací deseti cifer (10!) bez těch permutací, které mají jako první cifru nulu (9!). 10!-9! = 3265 920 Existuje 3 265 920 požadovaných čísel. 50 Cvičení 3.10 Kolik existuje deseticiferných čísel, jejich ciferný součet je dělitelný třemi? Řešení: Přeformulujme zadanou podmínku - ciferný součet čísla je dělitelný třemi právě tehdy, když je dané číslo dělitelné třemi. Máme tedy určit počet všech deseticiferných čísel dělitelných třemi. Všech deseticiferných čísel existuje 9 • 109 (první cifra nesmí být nula, máme pro ni devět možností, pro každou další cifru existuje deset možností). Z těchto čísel je každé třetí dělitelné třemi, tedy třetina všech deseticiferných čísel je dělitelná třemi. (9 • 109) : 3 = 3 • 109 Existuje 3 ■ 109 deseticiferných čísel s ciferným součtem dělitelným třemi. Cvičení 3.11 Kolik celých čísel od 0 do 999 není dělitelno ani 5, ani 7? Řešení: Z dané množiny 1000 čísel je zřejmě pětina čísel dělitelná 5 (1000 : 5 = 200) a sedmina čísel dělitelná 7 (1000 : 7 = 142). Je třeba si uvědomit, že 0 je dělitelná každým přirozeným číslem. Nesmíme také zapomenout na čísla, která jsou dělitelná 5 i 7, tedy jejich nejmenším společným násobkem, číslem 35 (1 000 : 35 = 28). Nyní využijeme principu inkluze a exkluze: od celkového počtu čísel odečteme ta, která jsou dělitelná jedním z čísel 5 a 7 a přičteme čísla dělitelná zároveň čísly 5 i 7. 1000 - 200 - 142 + 28 = 686 čísel nedělitelných 5 ani 7 je 686. Cvičení 3.12 Kolik různých čtyřciferných čísel lze sestavit z cifer čísla 123 153? Řešení: Rozdělme si výsledná čísla do tří skupin a v každé určeme jejich počet: (a) Čísla, ve kterých se každá cifra vyskytuje pouze jednou. Zřejmě nemáme jinou možnost volby cifer než 1, 2, 3 a 5. Počet čísel vytvořených z těchto cifer bude počet jejich permutací 4! = 24. (b) Čísla, ve kterých se jedna cifra vyskytuje dvakrát. Máme dvě možnosti výběru cifry, která se bude vykytovat dvakrát (1, 3), k ní vybíráme ze tří zbylých různých cifer další dvě ((jj)) a všechny čtyři vybrané cifry mezi sebou necháme permutovat (|[). Dohromady dostáváme 2 • (j) • §j = 72 čísel. (c) čísla, ve kterých se dvě cifry vyskytují dvakrát. Dvakrát můžeme podle zadání využít pouze cifry 1 a 3. Necháme-li je mezi sebou permutovat, získáme = 6. Zřejmě musí každé požadované číslo patřit do právě jedné ze tří skupin, výsledek tedy získáme sečtením dílčích počtů čísel v každé ze skupin. 24 + 72 + 6 = 102 Lze sestavit 102 čtyřciferných čísel. 51 Cvičení 3.13 Kolik pěticiferných čísel lze sestavit z cifer čísla 12 312 343, po zaduj eme-li, aby tři číslice 3 nenásledovaly za sebou? Řešení: Uvažujme stejně jako v předchozí úloze rozdělení výsledných čísel do disjunktních množin, spočítejme počet čísel v každé z množin a případně odečtěme čísla nevyhovující. (a) Čísla obsahující jednu číslici dvakrát. Máme tři možnosti výběru číslice vyskytující se dvakrát, zbylé číslice jsou pak dány. Nechrne všechny vybrané číslice permutovat a získáme 3 • || = 180 čísel. (b) Čísla obsahující dvě číslice dvakrát. Vybíráme dvě ze tří možných číslic, které se budou vyskytovat dvakrát (g)), k nim potřebujeme vybrat pátou číslici (2 možnosti) a všechny číslice necháme permutovat. ©•2-^1 = 180 (c) Čísla obsahující jednu číslici třikrát a zbylé číslice jednou. Třikrát se může vyskytovat pouze číslice 3, k ní vybereme další dvě čísla ze tří možných (g)) a čísla necháme permutovat: g) • §} = 60. Mezi 60 čísly jsou ale i čísla ze zadání zakázaná, například číslo 13 332. Počet zakázaných čísel získáme tak, že k sobě číslice 3 „slepíme" a považujeme je za jeden znak, ke kterému musíme vybrat dvě další číslice ze tří možných a všechny znaky necháme permutovat, tedy g) • 3! = 18. Vyhovujících čísel je 60 - 18 = 42. (d) čísla obsahující jednu číslici třikrát a jednu číslici dvakrát. Třikrát se může vyskytovat pouze číslice 3, k ní vybereme jednu ze dvou možných dvojic jiné číslice (1, 2) a necháme permutovat: 2 ■ — 20. Opět se zde vyskytují i nevyhovující čísla, jejichž počet získáme stejně jako v předchozí variantě 2 • || — 6. Vyhovujících čísel je 20 — 6 = 14. Zřejmě musí každé požadované číslo patřit do právě jedné ze čtyř skupin, stačí tedy sečíst 180 + 180 + 42 + 14 = 416. Lze sestavit 416 pěticiferných čísel. Cvičení 3.14 (*) Kolika způsoby lze přeskládat cifry čísla 1 234 114 546 tak, aby tři stejné cifry nenásledovaly za sebou? Řešení: Využijeme princip inkluze a exkluze. Od celkového počtu přeskládání cifer odečteme taková přeskládání, ve kterých jedna trojice stejných cifer následuje za sebou (1 nebo 4), a přičteme ta přeskládání, kde následují za sebou dvě trojice stejných cifer (1 i 4). Počet všech přeskládání získáme jako počet všech permutací s opakováním = 100 800. Chceme-li mít v přeskládání jednu trojici stejných cifer za sebou, musíme určit kterou (2 způsoby), danou trojici pak „slepíme" do jednoho znaku a necháme s ostatními permutovat: 2 • || = 13 440. Podobně pokud mají za sebou následovat obě trojice stejných cifer, můžeme každou trojici nahradit jedním znakem a nechat s ostatními permutovat, těchto čísel je 6! = 720. Výsledek určíme pomocí výše popsaného principu inkluze a exkluze. 52 100 800 - 13 440 + 720 = 88 080 Cifry lze přeskládat 88 080 způsoby. Cvičení 3.15 Kolika způsoby lze z přirozených čísel od 1 do 30 vybrat tři čísla tak, aby jejich součet byl sudý? Řešení: Mezi čísly od 1 do 30 je 15 čísel sudých a 15 čísel lichých. Chceme-li vybrat tři čísla tak, aby byl jejich součet sudý, musí být buď všechna sudá ((35)), nebo jedno sudé a dvě lichá ((115) • (25))- (135) + (\5)-(125)= 2 030 čísla lze vybrat 2 030 způsoby. 53 4. DU, řešení Cvičení 4.1 Kolika způsoby můžeme 4 barvami obarvit 10 kuliček? (a) Kuličky jsou rozlišitelné. (b) Kuličky nejsou rozlišitelné. Řešení: (a) Protože jsou kuličky různé (liší se například velikostí), rozhodujeme se pro každou kuličku zvlášť, kterou ze čtyř barev (možností) ji obarvíme. Obarvení jednotlivých kuliček na sobě nezávisí, použijeme tedy pravidlo součinu. 410 = 1048576 Kuličky lze obarvit 1048 576 způsoby. (b) Pro nerozlišitelné kuličky určíme množství různých obarvení jako počet kombinací s opakováním. Jinak řečeno, kuličky rozdělujeme do 4 přihrádek podle jejich barvy (mezi přihrádkami jsou 3 přepážky). Počet různých obarvení je tedy počet permutací s opakováním mezi 10 stejnými kuličkami a 3 přihrádkami). 13! _ 9Qfi 10!3! — zou Kuličky lze obarvit 286 způsoby. Cvičení 4.2 Kolik devítimístných čísel obsahuje právě dvě stejné číslice a žádnou nulu? Řešení: Nejprve vybereme číslici, která se bude v čísle vyskytovat dvakrát (9 způsobů). Dále určíme dvě místa ve výsledném čísle, kam tuto číslici umístíme ((2) způsobů) a na dalších sedm míst postupně vybíráme ze zbylých osmi číslic - na první místo máme 8 kandidátů, na další 7 a tak dále. 9- g) -8! = 13063680 Zadaných devítimístných čísel existuje 13 063 680. Cvičení 4.3 Kolika způsoby lze mezi 4 děti rozdělit 15 stejných hrušek tak, aby každé dítě dostalo alespoň 2 hrušky? Řešení: Jelikož není řečeno jinak, všechny hrušky zřejmě vyhovují kritériím EU a proto jsou naprosto rovnocenné (nerozlišitelné). Nejprve rozdáme každému dítěti 2 hrušky a k dalšímu rozdělování nám jich zbude 7. Nyní můžeme 54 zbylých 7 hrušek rozdělovat do přihrádek se jmény jednotlivých dětí: mezi přihrádkami jsou 3 nerozlišitelné přepážky, zajímá nás tedy počet permutací 3 přepážek a 7 hrušek. £77 = 120 Hrušky lze rozdělit 120 způsoby. Cvičení 4.4 Koika způsoby lze rozdělit 18 stejných jablek mezi 5 dětí tak, aby každé dítě dostalo alespoň 3 jablka? Řešení: Nad úlohou uvažujeme stejně jako v předchozím cvičení. Po rozdání 3 jablek každému dítěti nám zbudou k rozdělování 3 jablka. 4!-3! ~~ 00 Jablka lze rozdělit 35 způsoby. Cvičení 4.5 Určete počet přirozených čísel od 1 do 840, která nejsou dělitelná ani jedním z čísel 6, 10, 14- Řešení: Využijeme princip inkluze a exkluze podobně jako ve cvičení 3.11. Od počtu všech čísel (840) odečteme počty čísel, která jsou dělitelná jedním z čísel 6 (840 : 6 = 140), 10 (840 : 10 = 84) a 14 (840 : 14 = 60). Následně přičteme počty čísel, která jsou dělitelná jednotlivými dvojicemi čísel zároveň, tedy jejich nejmenším společným násobkem. Pro čísla 6 a 10 získáváme nejmenší společný násobek 30, čísel dělitelných 30 je 840 : 30 = 28. Podobně nejmenší společný násobek čísel 6 a 14 je 42, 840 : 42 — 20. Poslední dvojice čísel 10 a 14 má nejmenší společný násobek 70, 840 : 70 = 12. Konečně odečteme počet všech čísel, která jsou dělitelná čísly 6, 10 i 14, tedy jejich nejmenším společným násobkem 210, taková čísla jsou zřejmě 4. 840 - 140 - 84 - 60 + 28 + 20 + 12 - 4 = 612 Zadaných čísel existuje 612. Cvičení 4.6 V oddělení pracuje několik osob, z nichž každá zná alespoň jeden z těchto jazyků: ruština, španělština, italština. Rusky mluví 7 osob, španělsky 7 osob, italsky 7 osob, rusky a španělsky 4 osoby, španělsky a italsky 4 osoby, rusky a italsky 3 osoby, všechny tři uvedené jazyky ovládá jedna osoba. Určete, kolik osob (a) v oddělení pracuje; (b) mluví pouze rusky; (c) mluví pouze španělsky. Řešení: Označme R množinu všech osob mluvících rusky, S množinu všech osob mluvících španělsky a I množinu všech osob mluvících italsky. Úlohu je možné řešit přes Vennovy diagramy, my ji budeme řešit pomocí principu inkluze a exkluze. 55 (a) Počet všech zaměstnanců oddělení je sjednocením množin R, S a I. Dle pravidla inkluze a exkluze získáme celkový počet zaměstnanců sečtením osob mluvících rusky, španělsky nebo italsky, odečtením osob mluvících dvěma z daných jazyků a přičtením osob mluvících všemi třemi jazyky. \R\jSui\ = \R\ + \s\ + \i\-\Rns\-\Rni\-\sni\ + \Rnsm\ = = 7 + 7 + 7-4-3-4 + 1 = 11 V oddělení pracuje 11 osob. (b) Od osob mluvících rusky musíme dle principu inkluze a exkluze odečíst osoby mluvící rusky a španělsky, případně rusky a italsky, a přičíst osoby mluvící rusky, španělsky i italsky. \R\ - \R n s\ - \R n i\ + \r n s n i\ = 7 - 4 - 3 +1 = i Jedna osoba mluví pouze rusky. (c) Počítáme podobně jako předchozí variantu. \s\ - \s n r\ - \s n i\ + \s n R n i\ = 7 - 4 - 4 +1 = o Nikdo nemluví pouze španělsky. Cvičení 4.7 Na třídní schůzce informoval učitel rodiče takto: „Naše třída má 30 žáků. Mohou chodit do 4 zájmových kroužků, z nichž každý probíhá jednou týdně. Pondělní kroužek navštěvuje 19 žáků, úterní 13, středeční 18 a čtvrteční 11. Žádný žák nenavštěvuje více než dva kroužky a žádné dva kroužky nemají více než 5 společných žáků." Určete, zda učitel mohl mluvit pravdu. Svou odpověď zdůvodněte. Řešení: Protože žádný žák nenavštěvuje více než dva kroužky, můžeme počet žáků pomocí inkluze a exkluze spočítat následovně: od součtu žáků v jednotlivých kroužcích odečteme počet žáků navštěvujících nějakou z kombinací dvou kroužků (například žáků navštěvujících pondělní a čtvrteční kroužek). Součet žáků v jednotlivých kroužcích je 19 + 13 + 18 + 11 = 61. Každou kombinaci dvou kroužků navštěvuje nejvýše 5 žáků, uvažujme tedy, že každou kombinaci navštěvuje právě 5 žáků. V tom případě budeme od součtu žáků v jednotlivých kroužcích odečítat 5 • (2) = 30 žáků a dojdeme k výsledku, že třída má 31 žáků. Protože jsme odečítali nejvyšší možný počet žáků, není možné, aby bylo ve třídě méně než 31 žáků. Učitel se pravděpodobně spletl, nemluvil pravdu. Cvičení 4.8 Kolik „slov" je možno sestavit z písmen slova (a) SEMESTR (b) TERAKOTA tak, aby žádná dvě stejná písmena nestála vedle sebe ? Řešení: Úlohu vyřešíme stejně jako ve cvičení 3.7 pomocí principu inkluze a exkluze. Od všech přeskládání písmen vždy odečteme taková přeskládání, kdy vedle sebe stojí jedna dvojice stejných písmen (v obou variantách můžeme dvojici stejných písmen vybrat dvěma způsoby) a přičteme přeskládání, ve kterých vedle sebe stojí dvě dvojice stejných písmen. 56 (a) ^-2-f}+ 5! = 660 Z písmen slova SEMESTR lze sestavit 660 „slov". (b) -2-1 + 6! = 5760 Z písmen slova TERAKOTA lze sestavit 5 760 „slov". Cvičení 4.9 Máme 5 obálek s adresami a 5 dopisů (pro 5 různých lidí). Kolika způsoby můžeme vložit dopisy do obálek tak, aby žádný dopis nebyl ve správné obálce? Řešení: Využijeme principu inkluze a exkluze. Od počtu všech možných vložení dopisů do obálek (5!) odečteme počet vložení dopisů do obálek, v nichž je jeden dopis ve správné obálce (vybereme z pěti dopisů jeden co má být ve správné obálce a zbylé necháme permutovat (^) -4!). Dále přičteme počet vložení dopisů do obálek, v nichž jsou dva dopisy ve správné obálce ((2) • 3!), odečteme vložení se třemi dopisy ve správných obálkách ((3) -2!), přičteme vložení se čtyřmi dopisy ve správných obálkách ((jj) • 1!) a odečteme jedinou možnost jak vložit všechny dopisy do správných obálek. 5!-(D-4!+(2)-3!-(3)-2! + (4)-l!-l = 44 Dopisy můžeme vložit do obálek 44 způsoby. Cvičení 4.10 Kolika způsoby mohou páry na plese vytvořit dvojice muž-žena tak, aby žádní partneři netančili spolu? (a) Na ples přišly 3 partnerské páry. (b) Na ples přišly 4 partnerské páry. (c)* Na ples přišlo n partnerských párů. Řešení: (a) Úloha je analogie předchozího cvičení. Pro 3 páry (Novákovi, Blažkovi a Tomanovi) máme dvě možnosti vytvoření párů: paní N. tančí s panem B., paní B. tančí s panem T. a paní T. tančí s panem N, nebo paní N. tančí s panem T., paní B. tančí s panem N. a paní T. tančí s panem B. Pokud bychom počítali principem inkluze a exkluze (zafixujeme si pány a řadíme k nim dámy), odečetli bychom od počtu všech přiřazení dam počet takových přiřazení, kde je jeden manželský pár pohromadě, přičetli přiřazení, kde tančí dva manželské páry spolu a odečetli jediné možné přiřazení, kdy tančí všechny ženy se svým doprovodem. 3!-g)-2! + g)-l = 2 Dvojice mohou vytvořit 2 způsoby. (b) Pomocí inkluze a exkluze řešíme stejně jako v předchozí variantě. 4!-(}).3! + e).2!-g) + l = 9 Dvojice mohou vytvořit 9 způsoby. 57 (c)* Stejně jako v předchozích variantách bychom postupovali i pro více párů, můžeme tedy zobecnit: n! - ft) („-1)! + £)(n- 2)! - ■ ■ + (-1)"® = ELo(-l)n(2)(n-k)\ Dvojice mohou vytvořit Yľk=o(~^)n{k)(n ~ způsoby. Cvičení 4.11 Kolik existuje pořadí písmen a, b, d, e, i, k, m, n, r, ů, z takových, že po vynechání některých písmen vznikne některé ze slov (a) mrak, důraz (b) * bar, den, razie (c) * arzen, drak, dům, důraz Řešení: (a) Začněme určením počtu pořadí písmen, ze kterých nám po vhodném proškrtání vznikne jedno ze slov MRAK, DŮRAZ, nejprve se zaměřme na slovo MRAK. V každém z uspořádání daných 11 písmen se vyskytují písmena M, R, A, K v jednom ze 4! různých vzájemných pořadí. My však požadujeme právě to pořadí, ze kterého po vyškrtání všech písmen mimo M, R, A, K vznikne slovo MRAK. Proto je počet všech uspořádání 11 písmen z nichž po vyškrtání vznikne slovo MRAK Stejně tak počet uspořádání všech písmen, ze kterých vznikne po vhodném vynechání slovo DŮRAZ, je Kdybychom tato dvě čísla sečetli, započítali bychom dvakrát ta uspořádání, ve kterých se vyskytují obě slova MRAK i DŮRAZ. Tato uspořádání musíme nyní odečíst. Aby po vhodném vyškrtání vzniklo z daného pořadí slovo MRAK a po jiném vyškrtání slovo DŮRAZ, musí mít písmena M, R, A, K, D, Ů, Z vhodná pořadí, například MDŮRAZK, nebo DMŮRAKZ. Uvažujme, že by existovalo jenom jedno vhodné pořadí písmen M, R, A, K, D, Ů, Z. Pak by počet vyhovujících uspořádání všech 11 písmen byl Jelikož ale existuje více vhodných uspořádání 7 zmíněných písmen, zlomek vynásobit jejich počtem. Zřejmě musí písmena R, A stát vedle sebe v tomto pořadí. Před nimi musí stát písmena M, D, Ů, a to v 3 možných pořadích (MDŮ, DMŮ, DŮM). Za písmeny R, A stojí písmena K, Z v libovolném ze dvou pořadí. Celkem tedy získáváme ^ + ^f-^-3-2 = 1948 320. Existuje 1 948 320 požadovaných pořadí písmen. (b)* Určeme si, z kolika pořadí nám vznikne slovo BAR, slovo DEN a slovo RAZIE a tyto hodnoty sečtěme. Musíme si ale dát pozor, abychom nějaká pořadí nezapočítali dvakrát, proto dle principu inkluze a exkluze odečteme pořadí generující po vhodném vyškrtání hned dvě ze tří slov (BAR a DEN, RAZIE A DEN, BAR a RAZIE) a opět přičteme ta pořadí, ze kterých nám mohou vzniknout všechny tři slova. V každém přeskládání písmen se vyskytují písmena B, A, R v jednom z jejich 3! možných pořadí, přičemž my požadujeme právě jedno z pořadí. Počet vyhovujících přeskládání proto získáme ^p. Analogicky pro slovo DEN máme přeskládání a pro slovo RAZIE tt1 přeskládání. 58 Slova BAR a DEN získame z pořadí tak, že si zafixujeme všechna jejich písmena (^p) a následně ještě uvážíme, jak můžeme jednotlivá zafixovaná písmena mezi sebou permutovat. Jistě musí být zachováno pořadí písmen B, A, R, i pořadí písmen D, E, N, písmena těchto dvou slov se však mohou vmíchat do sebe (BADENR), zlomek proto musíme vynásobit výrazem J^. Podobně uvažujme pro slova DEN a RAZIE. Po zafixování všech písmen ze slov dostáváme ^ pořadí. Je jisté, že N musí být na posledním ze sedmi míst, pro D potom vybíráme jedno z 5 míst před písmenem E. Celkem dostáváme ' 5. Konečně dvojice slov BAR a RAZIE nemohou být nikdy generovány stejným pořadím kvůli vzájemné poloze R a A. Ze stejného důvodu neexistuje pořadí generující všechna tři slova. 111 + 111 + lil _ lil . _6L _ lil . 5 - i n 272 240 3! + 3! + 5! 6! 3!3! 7! ZfHJ Existuje 10 272 240 požadovaných pořadí písmen. (c)* Postupujeme stejně jako v předchozích variantách. Počty pořadí pro slova nebo jejich kombinace jsou: ARZEN: ^ DRAK: DŮM: $ DŮRAZ: ^ ARZEN a DRAK: 0 ARZEN a DŮM: $ ■ ARZEN a DŮRAZ:' 0 DRAK a DŮM: ^ • ^ (D musí být na prvním místě) DRAK a DŮRAZ: • 2 (můžeme prohodit pouze Z a K) DŮM a DŮRAZ: ^ ■ § (DŮ musí být na začátku) ARZEN, DRAK a DŮM: 0 ARZEN, DRAK a DŮRAZ: 0 ARZEN, DŮM a DŮRAZ: 0 DRAK, DŮM a DŮRAZ: ^ • 5 • 2 (musí začínat DŮ, hledáme místo pro M, můžeme přehazovat K a Z) ARZEN, DRAK, DŮM a DŮRAZ: 0 11! , 11! , 11! , 11! _ 11! _8!__11! _5]__11! oli! 4! ,11! r o _ 7SQfiO/in 5! "i" 4! "i" 3! "r" 5! 8! '4!3! 6! ' 3!2! 6! 6! ' 3! 7! 'd'z — ' oao Existuje 7896 240 požadovaných pořadí písmen. Cvičení 4.12 Kolika způsoby lze umístit 8 hracích kamenů na šachovnici 4x4 tak, aby v právě jednom řádku nebo v právě jednom sloupci byly 4 kameny? Řešení: Zvolme si řádek a umístěme do něj 4 kameny. Zbylé kameny musíme umístit tak, aby nevytvořily celý řádek nebo sloupec. Od všech možností umístění ((^2)) odečteme ta umístění, ve kterých kameny vytvoří celý nový řádek (vybíráme pouze řádek ze 3 možných), a umístění, ve kterých vyplní sloupec (vybereme jeden ze 4 sloupců a doplníme jej třemi kameny, pro poslední kamen vybereme jakékoli ze zbylých volných míst). Kdybychom na začátku místo řádku vybrali sloupec, došli bychom ke stejnému výsledku, proto výsledek ještě vynásobíme dvěma. 2-4- ((\2) -3-4-9) = 3648 Kameny lze umístit 3 648 způsoby. 59 Cvičení 4.13 Kolik kompozic daného přirozeného čísla n na právě k sčítanců můžete vytvořit? (a) n = 3, k = 5 (b) n = 15,k = 7 (c) n = 12, k = 7 (d) n = 12, k = 3 Řešení: Počet všech kompozic čísla n na právě k sčítanců určíme ze vzorce = (£})■ (a) Zřejmě nelze číslo rozložit na více sčítanců, než je jeho hodnota (uvažujeme pouze sčítance z oboru přirozených čísel). K(3,5) = 0 (b) K(15,7) = (x64) = 3003 (c) K(12,7) = (161)=462 (d) K(12,3) = (121)=55 Cvičení 4.14 Kolik rozkladu daného přirozeného čísla n na pravěk sčítanců můžete vytvořit? (a) n = 3, k = 5 (b) n = 15,fc = 4 (c) n = 12, k = 4 (d) n = 12, k = 3 Řešení: Počet rozkladů čísla n na právě k sčítanců určíme z rekurentního vzorce k p(n, k) = ^2p(n - k, i);p(n, 1) = p(n, n) = 1. »=i (a) Podobně jako v předchozím cvičení nelze číslo rozložit na více sčítanců, než je jeho hodnota, proto p(3, 5) = 0. (b) p(15,4) =p(ll,l)+p(ll,2)+p(ll,3)+p(ll,4) = 1 + 5 + 10 + 11 = 27 (c) p(12,4) = p(8,1) + p(8,2) + p(8,3) + p(8,4) = 1 + 4 + 5 + 5 = 15 (d) p(12,3) = p(9,1) + p(9,2) + p(9,3) = 1 + 4 + 7 = 12 60 5. DU, řešení Cvičení 5.1 Na večírku se sešlo několik přátel. Každý si při prípitku připil s každým a ozvalo se 28 cinknutí. Kolik přátel se sešlo na večírku? Řešení: Jestliže si každý připil s každým, lze z daného počtu hostů vytvořit 28 dvoučlenných kombinací. n(n — 1) = 56 n = 8 Na večírku se sešlo 8 přátel. Cvičení 5.2 Kolik různých čísel dělitelných třemi menších než 10 000 lze sestavit z číslic 0,2,3,4,6 takových, že se v nich číslice neopakují? Přeformulujme si zadané podmínky: má-li být číslo dělitelné třemi, musí být jeho ciferný součet dělitelný třemi. Je-li číslo menší než 10000, musí být nejvýše čtyřciferné. Sestavujme postupně jednociferná až čtyřciferná čísla vyhovující podmínkám a určujme jejich počet. Jednociferná čísla jsou zřejmě 2. Dvouciferná čísla musí mít ciferný součet buď tři (tomu vyhovuje jediné číslo 30), šest (čísla 24, 42 a 60), nebo devět (čísla 36, 63). Dohromady existuje vyhovujících dvouciferných čísel 6. Trojciferná čísla nedokážeme sestavit tak, aby měla ciferný součet tři. Uvažujme tedy ciferný součet šest (čísla vytvořená z cifer 0, 2, 4, která existují 4), devět (čísla vytvořená z cifer 0, 3, 6, která existují 4, nebo z cifer 2, 3, 4, těch je 6) a dvanáct (čísla vytvořená z cifer 2, 4, 6, je jich 6). Dohromady jsme nalezli 20 tří ciferných vyhovujících čísel. čtyřciferná čísla mohou mít ciferný součet devět (čísla z cifer 0, 2, 3, 4, kterých je 18), dvanáct (čísla z cifer 0, 2, 4, 6, kterých je také 18) a patnáct (čísla z cifer 2, 3, 4, 6, těch existuje 24). Čtyřciferných vyhovujících čísel jsme nalezli 60. Celkový počet získáme jako součet dílčích počtů, tedy 2 + 6 + 20 + 60 = 88. Lze sestavit 88 čísel vyhovujících podmínkám. 28 (n-2)!-2! 28 Řešení: 61 Cvičení 5.3 Vymyslete slovní úlohu tak, aby výsledek byl (a) 3!2!2!2! Řešení: (a) Určete počet všech permutací písmen slova POPOCATEPETL. (b) Kolika způsoby si mohu v restauraci vybrat obědy na pondělí, úterý a středu, je-li v nabídce 12 různých jídel a chci-li jíst každý den něco jiného? Cvičení 5.4 Kolika způsoby můžeme mezi tři děti rozdělit 9 stejných jablek? Kolika způsoby můžeme těchto 9 jablek rozdělit mezi tři děti spravedlivě? Řešení: Jelikož není řečeno jinak, jablka jsou všechna stejná a nelze je od sebe rozlišit. Druhá otázka je triviální, zřejmě existuje jediné takové rozdělení - každému dítěti dáme tři jablka. Pro zodpovězení první otázky přiřazujeme jablka do tří přihrádek (mezi nimiž jsou dvě nerozlišitelné přepážky) symbolizujících jednotlivé děti. 9!-2! ~~ 00 Jablka můžeme rozdělit 55 způsoby, spravedlivě 1 způsobem. Cvičení 5.5 Kolika způsoby lze mezi tři děti rozdělit 15 stejných jablek a 9 stejných hrušek? Kolika způsoby to lze provést spravedlivě? Řešení: Úloha je velmi podobná předchozímu cvičení, ovoce stejného druhu je opět nerozlišitelné a spravedlivé rozdělení existuje pouze jedno (každému dítěti 5 jablek a 3 hrušky). Rozdělování hrušek a jablek děláme nezávisle na sobě, u každého druhu ovoce přitom zopakujeme úvahu z předchozího cvičení. 17! 11! _ jaqq 15!-2! 9!-2! — ' ^ou Ovoce můžeme rozdělit 7480 způsoby, spravedlivě 1 způsobem. Cvičení 5.6 Kolika způsoby můžeme mezi čtyři studenty rozdělit 7 různých matematických sbírek? Řešení: U každé sbírky máme 4 možnosti darování. Darování jednotlivých sbírek je na sobě nezávislé, proto stačí použít pravidlo součinu. 4 . 4 . 4 . 4 . 4 . 4 . 4 = 47 = 16 384 Sbírky můžeme rozdělit 16 384 způsoby. Cvičení 5.7 Kolika způsoby může dát 5 chlapců 6 dívkám valentýnky, jestliže se chlapci mezi sebou nedomlouvali a každý z nich dá valentýnku právě jedné dívce ? 62 Řešení: Podobně jako v předchozí úloze se každý z chlapců nezávisle na ostatních rozhoduje pro jednu z 6 dívek, užijeme opět pravidlo součinu. 6-6-6-6-6 = 65 = 7776 Valentýnky mohou rozdat 7 776 způsoby. Cvičení 5.8 Kolika způsoby lze ze třídy, v níž je 10 hochů a 20 dívek, vybrat trojici tak, aby v ní byl alespoň jeden hoch? Řešení: V trojici může být jeden hoch a dvě dívky • (22°)), dva hoši a jedna dívka (ffi ' (i°))> nebo mohou být všichni tři hoši ((130)). (1ľ)-(22°) + (120)-(T) + (13°)= 2 920 Trojici lze vybrat 2 920 způsoby. Cvičení 5.9 Kolika způsoby můžeme obarvit pěti barvami dvanáct stejných kuliček? Řešení: Kuličky vkládáme do pěti přihrádek různých barev, permutujeme tedy 12 nerozlišitelných kuliček a 4 nerozlišitelné oddělovače přihrádek. Ä = 1820 Kuličky lze obarvit 1 820 způsoby. Cvičení 5.10 Vyřešte v oboru Z rovnice: fa) 2{x~1)l + {x~2)- - fia: - 16 \aJ Z(x-2)l + (x-4)! _ 0X 10 n,) (x+1)! - (x+4)! - n (°/ (x-1)! (x+3)! _ U fr) ?{x-3)1 C*-2?1 - n (°J Zj^y. - is=4j! - u M) 9Í£±2)! (s+1)! _ n W Z(x-1)\ (x-2)! _ U Řešení: (a) „(x-1)! (x-2)! 27-+ 7-7tt = 6a;-16 (a;-2)! (x —4)! 2(x - 1) + (x - 2)(x - 3) = 6a;-16 2a; - 2 + x2 - 5x + 6 = 6a; - 16 x2 -9a; + 20 = 0 (x-4)(x-5) = 0 Kořeny dané rovnice jsou čísla 4 a 5. Ze zadání plyne podmínka x > 4, obě čísla jsou tedy řešením. 63 (b) (x + 1)! (a;+ 4)! (x-l)\ (x+ 3)1 (x + l)x - (x + 4) = O x2 + x - x - 4 = O (x-2)(x + 2) = O Kořeny dané rovnice jsou čísla —2 a 2. Ze zadání však plyne podmínka x > 1, řešením je tedy pouze číslo 2. (c) (x-3)1 (x-2)! (x-5)! (x-4)! 2(x-3)(x-4) - (x-2)(x-3) = 0 2x2 -14x + 24-x2 + 5x-6 = 0 x2 - 9x + 18 = 0 (x-3)(x-6) = 0 Kořeny dané rovnice jsou čísla 3 a 6. Ze zadání však plyne podmínka x > 5, řešením je tedy pouze číslo 6. (d) n(x + 2)! + (x-1)! (x-2)! 2(x + 2)(x + l)x-(x + l)x(x-l) = 0 (x + l)x(2x + 4- X + 1) = 0 (x + l)x(x + 5) = 0 Kořeny dané rovnice jsou čísla —5, —1 a 0. Ze zadání však plyne podmínka x > 2, úloha tak nemá žádné řešení. Cvičení 5.11 Kolika způsoby můžeme nalepit na dopis známky za 18 Kč, máme-li k dispozici známky za 2, 4 a 10 Kč (v libovolném potřebném množství)? Vypište všechny možnosti. Řešení: Úlohu vyřešíme vypsáním všech možností do tabulky. 2 Kč 9 7 5 4 3 2 1 4 Kč 12 3 14 2 10 Kč 1 1 1 Známky můžeme nalepit 8 způsoby. 64 Cvičení 5.12 Na kolik oblastí rozdelí rovinu n přímek v obecné poloze (tzn. žádné dvě nejsou rovnoběžné a žádné tři se neprotínají v temže bodě) ? Řešení: Promysleme si počty oblastí pro několik prvních n a následně odvoďme rekurentní vztah pro počet oblastí v závislosti na počtu přímek. Označme si on počet oblastí pro n přímek v obecné poloze. n = 1 . • oi = 2 n = 2 . • o2 = 4 n = 3 . • o3 = 7 n = 4 . . o4 = 11 n = 5 . • o5 = 16 Je vidět, že přidáním každé další přímky se počet oblastí zvýší o aktuální počet přímek, proto platí následující vztah: on = on-i + n Rovina bude rozdělena na on = on_i + n oblastí. Cvičení 5.13 Dokažte (např. matematickou indukcí): (a) 1 + 3 + 5 + • • • + (2n - 1) = n2 (b) 2 + 4 + 6 + ■ • • + (2n) = n2 + n (c) 3 + 5 + 7 + • • • + (2n - 1) = n2 - 1 (d) 3 + 5 + 7 + • • • + (2n + 1) = n2 + 2n (e) 1 + 4 + 7 + • • • + (3n - 2) = 3n2 - n Řešení: V prvním kroku vždy ověříme platnost pro n = 1, poté budeme předpokládat platnost pro n — 1 a z předpokladu dokážeme platnost pro n. (a) 1. Dosadíme postupně do levé a pravé strany n = 1: L = 1;P = 1;L = P 2. Předpokládejme platnost pro n — 1 a dokažme pro n: 1+3+- • -+(2n-3)+(2n-l) = 1+3+- • -+(2(ra-l)-l)+(2n-l) = = (n - l)2 + (2n - 1) = n2 - 2n + 1 + 2n - 1 = n2 (b) 1. Dosadíme postupně do levé a pravé strany n = 1: L = 2;P = 2;L = P 2. Předpokládejme platnost pro n — 1 a dokažme pro n: 2 + 4 + • • • + (2n - 2) + 2n = 2 + 4 + • • • + 2(n - 1) + 2n = = (n - l)2 + (n - 1) + 2n = n2 - 2n + 1 + n - 1 + 2n = n2 + n (c) Jedná se o jinak zapsanou variantu (a), důkaz již byl proveden. 65 (d) 1. Dosadíme postupně do levé a pravé strany n = 1: L = 3;P = 1 + 2 = 3;L = P 2. Předpokládejme platnost pro n — 1 a dokážme pro n: 3+5+- • -+(2n-l)+(2n+l) = 3+5+- • -+(2(n-l)+l)+(2n+l) = = (n-l)2+2(n-l)+(2n+l) = n2-2n+l+2n-2+2n+l = n2+2n (e) 1. Dosadíme postupně do levé a pravé strany n = 1: L = 1;P = 3-1 = 2;L^P Je vidět, že rovnost neplatí ani pro n = 1, dál nemusíme dokazovat. Cvičení 5.14 Sečtěte: (a) S = n + (n + 3) + (n + 6) H-----h 4n (b) S = (-31) + (-27) + (-23) + • • ■ + 29 + 33 (c) S = n + (n + 2) + (n + 4) H-----h 3n fdj 5 = (-8) + (-5) + (-2) + l+4 + --- + (3n + l) (e) S = (-5) + (-3) + (-l) + l + 3 + 5 + --- + (2n + 5) + (2n + 7) Řešení: Ve všech variantách se jedná o aritmetické posloupnosti. Pomocí diference a prvního členu určíme počet členů dané posloupnosti a sečteme pomocí vztahu _ n(ai + an) bn- 2 (a) S = n + (n + 3) + (n + 6) H-----h 4n ai = n čta; = ai + (x — \)d d = 3 4n = n + 3(x - 1) ax — An x — n + 1 an+i = 4n (n + l)(n + 4n) _ 5n(n + 1) íľ> — -"ľ- — -"ľ- 2 2 (b) S = (-31) + (-27) + (-23) + • • • + 29 + 33 ai = —31 ax = a\ + (x — l)d d = 4 33 = -31 + 4(x - 1) ax = 33 x = 17 oi7 = 33 s = 17(-31 + 33) = 1? 66 (c) S = n + (n + 2) + (n + 4) H-----h 3ra ai = n a-r = ai + (a; — l)d d = 2 3n = n + 2(x - 1) aa; = 3n x = n + 1 ftn+i = 3n g=(n + l)(n + 3n)=2n(n + 1) (d) 5 = (-8) + (-5) + (-2) + l+4 + --- + (3n + l) ai = —8 a^; = ai + (x — l)d d = 3 3n + 1 = -8 + 3(x - 1) ax = 3ji + 1 x = n + A = 3n + 1 c_ (n + 4)(-8 + 3n + l) _ (n + 4)(3n-7) O — -T"- - -~~- 2 2 (e) S = (-5) + (-3) + (-l) + l + 3 + 5 + --- + (2n + 5) + (2n + 7) ai = —5 ax = a\ + (x — l)d d = 2 2n + 7 = -5 + 2{x - 1) = 2n + 7 a; = n + 7 an+7 = 2n + 7 5=(n + 7)(-5 + 2n + 7)=(n + 7)(n + 1) Cvičení 5.15 Sečtěte (každou variantu rozložte na dvě aritmetické posloupnosti): (a) S = l-2 + 3-A + --- + (-l)n+1n (b) 5 = 1- 2 + 4- 4 + 7- 6 + 10 - 8 • • • + (3n - 2) + (-l)2n+12n Řešení: Obě dané posloupnosti můžeme rozdělit na dvě posloupnosti, každou z nich sečteme zvlášť a nakonec sečteme oba součty. Opět se budeme opírat o vzorec z předchozí úlohy. (a) Posloupnost si rozdělíme do dvou posloupností tak, že v jedné posloupnosti budou všechny kladné členy a ve druhé všechny záporné. Abychom mohli určit poslední členy obou posloupností, musíme rozlišit případ, kdy bude n liché, respektive sudé. Pro lichá n získáváme posloupnosti 51 = 1 + 3 + 5-1-----\-n 52 = -2-4-6-...-(n-l), 67 přičemž první z posloupností má 2]yl členů, druhá má í^ členů. Určeme součty posloupností. o _ (n+l)(l+n) _ n2+2n+l o _ (n-l)(-2-n+l) _ -n2+l c _ n+1 "^l — 4 — 4 ^2 — 4 — 4 >-> — ~2~ Pro sudé n získáváme posloupnosti 51 = l + 3 + 5 + --- + (n-l) 52 = -2-4-6- ... -n, přičemž první z posloupností má ^ členů, druhá má | členů. Určeme součty posloupností. C _ n(l+n-l) _ n2 a _ n(-2-n) _ -n2-2n c _ n <->l — 4 — "f