Příklady matematických důkazů Zkoušejte hledat řešení (důkazy) pro následující příklady. Řešte je pokud možno po pořadí, nejprve po týdnu zveřejním první půlku řešení, pak teprve druhou.. . Mnoho zdaru! Příklad 1. Co je špatného na následujícím "důkaze"? Ukážeme, že platí 2 = -2: Umocněním na druhou vzejde 22 = 4 = (-2)2, což je platná rovnost, a proto i původní vztah 2 = -2 je platný. Řešení. Špatné je, že byl použit obrácený postup kroků ­ od neznámého závěru tvrzení zpět ke známým faktům, důkaz však musí jít vždy od známého k závěrům. 2 Příklad 2. Co je špatného na následujícím "důkaze"? Nechť a, b jsou celá čísla. Vyjdeme z předpokladu a = b a ukážeme, že a = -b. (Tj. po dosazení a = b = 2 opět vyjde 2 = -2.) Umocněním výchozího předpokladu a = b získáme a2 = b2, neboli 0 = a2 - b2 = (a + b)(a-b). Pak je i 0(a-b) = 0 = (a+b)(a-b) a dále po zkrácení 0 = a+b, tedy a = -b. Řešení. Nyní je postup kroků správný, ale chybné je krácení výrazem (a - b), neboť a - b = 0 a nulou se nesmí krátit. 2 Příklad 3. Dokažte indukcí podle k 0, že číslo (26k - 1) je dělitelné sedmi. Řešení. Budeme postupovat indukcí podle parametru k 0. * Pro k = 0 platí, že 20 - 1 = 0 je dělitelné sedmi. * Nechť nyní tvrzení platí pro nějaké k. Podívejme se, o kolik se změní hodnota výrazu (26k - 1) při zvětšení k o jedna: 26(k+1) - 1 - 26k - 1 = 26 26k - 26k = 26k (26 - 1) = 26k 63 Důležitým faktem nyní je, že číslo 63 je dělitelné sedmi. To ale znamená, že pokud (26k - 1) bylo dělitelné sedmi podle indukčního předpokladu, bude sedmi dělitelné i 26(k+1) - 1. Formálně tento indukční krok zapíšeme následovně: Nechť dle indukčního předpokladu 26k - 1 = 7, kde je nějaké přirozené číslo. Pak 26(k+1) - 1 = 26 26k - 1 = (26 - 1) 26k + 26k - 1 = 63 26k + 7 = 1 = 7 9 26k + , takže i tento výraz je dělitelný sedmi. 2 Příklad 4. Každá n-prvková množina má právě 2n podmnožin (včetně prázdné). Formálně 2X = 2|X| . Řešení. Matematickou indukcí podle n: * Pro n = 0 tvrzení platí, neboť prázdná množina má jedinou podmnožinu, opět prázdnou. * Nechť nyní tvrzení platí pro n 0. Vezmeme libovolnou množinu X o n + 1 > 0 prvcích. Zvolme prvek a X a označme X = X \ {a}, |X| = n. Potom všech podmnožin P X je podle indukčního předpokladu 2n. Pro prvek a navíc máme nezávislý výběr ze dvou možností: buď a dáme do podmnožiny P, nebo nedáme. Celkem je tak 2 2n = 2n+1 možností volby podmnožiny P X, cbd. Důkaz je hotov podle principu matematické indukce. 2 Příklad 5. Počet všech permutací n-prvkové množiny je n!, pro každé n 0. Řešení. Indukcí podle n: Tvrzení platí pro n = 0, protože žádné prvky lze uspořádat jen jedním způsobem (stejně tak jeden prvek). Mějme nyní n 0 a množinu P o n + 1 prvcích, předpokládejme pro jednoduchost P = {1, 2, . . . , n + 1}. Zvolme první prvek p P naší permutace jedním z n + 1 způsobů. Chtělo by se přímo říct, že potom už je volba zbytku permutace P \{p} nezávislá na volbě prvního p, ale to formálně není pravda. Aby tomu tak skutečně bylo, musíme si zbylé prvky P \{p} nejprve "přečíslovat" na {1, 2, . . . , n}, což počet voleb neovlivní. Pak už však zbytek plyne jasně ­ n-prvková množina {1, 2, . . . , n} má podle indukčního předpokladu n! permutací, proto P má celkem (n+1)n! = (n + 1)! permutací. To je přesně to, co chceme. 2 2 Návod pro následující ­ metoda dvojího počítání: Nechť každý případ nějakého (složeného) výběru lze dále rozlišit (zjemnit) na stejný počet zjemněných možností. Dále nechť získaný zjemněný výběr má celkem m různých možností (které jsme schopni spočítat). Potom počet všech možností původního výběru je dán podílem m/. Příklad 6. Počet všech k-prvkových variací z n-prvkové množiny je n! (n-k)!, pro každé n k 0. Řešení. Metodou dvojího počítání: Budeme se dvěma způsoby dívat na výběr permutací n-prvkové množiny. Jak již víme, lze tyto permutace vybrat n! různými způsoby. Na druhou stranu lze vzít některou k-prvkovou variaci, její prvky dát na začátek permutace v jejich pořadí a zbylých n - k prvků seřadit za nimi jedním z (n-k)! různých způsobů. Z různých variací tímto postupem zřejmě získáme různé výsledné permutace, a přitom každou permutaci lze získat z variace vybírající jejích prvních k prvků. Označíme-li x neznámý počet všech k-prvkových variací z n-prvkové množiny, lze výše popsaným postupem vytvořit právě x (n - k)! všech různých permutací n-prvkové množiny. Proto platí x (n - k)! = n! , x = n! (n - k)! . 2 Příklad 7. Počet všech k-prvkových kombinací z n-prvkové množiny je n k , pro každé n k 0. Řešení. Metodou dvojího počítání: Nyní budeme dvojím způsobem počítat všechny k-prvkové variace z nprvkové množiny. Na jednu stranu už víme, že jich je n! (n-k)! , na druhou stranu můžeme z jedné k-prvkové kombinace vygenerovat celkem k! různých variací uspořádáním prvků této kombinace. Označíme-li tedy x neznámý počet všech k-prvkových kombinací z n-prvkové množiny, dostaneme obdobně jako v předchozím důkaze x k! = n! (n - k)! , x = n! k! (n - k)! = n k . 2 3 Příklad 8. Dokažte platnost následujícího vztahu pro všechna přirozená n 1: n i=1 (2i - 1) 3i = (n - 1) 3n+1 + 3 (Matematickou indukcí.) Řešení. . . . Indukční krok (n - 1)3n+1 + 3 + (2(n + 1) - 1)3n+1 = (n - 1)3n+1 + (2n + 1)3n+1 + 3 = n3n+2 + 3 2 Návod pro následující ­ Dirichletův princip: Rozmístíme-li + 1 (nebo více) objektů do přihrádek, v některé přihrádce musí být aspoň dva objekty. Příklad 9. Mezi čtyřmi přirozenými čísly vždy najdeme dvě, jejichž rozdíl je dělitelný číslem 3. Řešení. Nechť přihrádkami jsou zbytkové třídy při dělení číslem 3. Máme tedy pro naše 4 čísla tři přihrádky značené 0, 1, 2. Podle Dirichletova principu do některé z přihrádek padnou dvě z čísel x, y, ale pak x - y dává zbytek 0 při dělení 3, tudíž jsme našli požadovanou dvojici. 2 Příklad 10. Na letním táboře 29 dětí stráví celkem 16 dní a 15 nocí. Každou noc jsou dva z táborníků na hlídce. Dokažte, že některé z dětí musí jít na hlídku za celý tábor aspoň dvakrát. Řešení. To je velice snadné počítání: Je-li celkem třeba 15 nočních hlídek, potřebujeme 15 2 = 30 táborníků na jejich pokrytí, pokud se žádný nemá opakovat. To však tak nejde, když je na táboře pouze 29 < 30 dětí. 2 Příklad 11. 8 kamarádů jelo na 9 dní dovolené. Každý den některá (jedna) trojice z nich šla na výlet. Dokažte, že někteří dva z nich ani jednou nebyli spolu na výletě. Řešení. Rozebírání možností by asi k ničemu nevedlo. . . Důkaz počítáním je však opět snadný: Jedna trojice má celkem 3 dvojice, proto po 9 dnech se mohlo vystřídat nejvýše 93 dvojic ve výletních trojicích, ale 9 3 = 27 < 8 2 = 28, jedna dvojice nám zde schází. 2 4