Předmluva Následující materiál představuje osnovu k semináři Metody řešení matematických úloh 2. Text je organizován přibližně podle průběhu semináře, přičemž některé náměty se samozřejmě prolínají. Řešíme vybrané úlohy školského charakteru, jež dovolují zajímavou diskuzi nad problémem, různorodá řešení, netriviální zobecnění apod. Snažíme se neřešit izolované úlohy, ale spíš témata a souvislosti. Jednou z hlavních motivací je maximální zúročení dosaženého vzdělání v oboru. Podobný přístup je vyžadován po každém, kdo usiluje o zápočet! Vděčnými zdroji často bývají popularizační publikace určené širší veřejnosti, jako např. [Pe, Sm, Stí, St2], ke kterým se však snažíme doplnit poznámky, které obvykle širší veřejnosti unikají. Osvědčené odbornější knihy jsou např. [A, HKS, L, LP, Po, SPB] apod. Vybíráme taky úlohy ze školních seminářů a soutěží, jako např. [MO, MKS, V]. Organizace tohoto materiálu je provizorní a během semestru se může měnit; sledujte změny v aktualizacích. Brno, 21. září 2016 Vojtěch Žádník 2 Obsah I Příklady 5 1 Míchání karet a skládání permutací.......................... 5 1.1 Formulace problému.............................. 5 1.2 Pokusy a postřehy............................... 6 1.3 Reformulace problému............................. 7 1.4 Řešení problému................................ 7 1.5 Poznámky.................................... 9 2 Přelévání vody a lineární diofantické rovnice..................... 9 2.1 Úvod....................................... 9 2.2 Rovnice se dvěma neznámými......................... 10 2.3 Rovnice s libovolným počtem neznámých.................. 12 2.4 Modifikace a poznámky............................ 13 3 Pythagorejské trojice a nelineární diofantické rovnice................ 15 3.1 Pythagorejské trojice.............................. 15 3.2 Příbuzné rovnice................................ 18 3.3 Poznámky.................................... 19 4 Záhon zelí a konečné součty.............................. 19 4.1 Zahradnické počty............................... 20 4.2 Součet posloupnosti čtverců.......................... 20 4.3 Instantní zobecnění............................... 23 4.4 Další počitatelné příklady........................... 23 4.5 Problematické příklady ............................ 25 5 Achilles, želva a nekonečné součty........................... 26 5.1 Achilles a želva................................. 26 5.2 Další nekonečné součty............................. 27 5.3 Poznámky.................................... 29 6 Kvadratura mnohoúhelníku a integrální počty.................... 30 6.1 Kvadratura mnohoúhelníku.......................... 30 6.2 Kvadratura paraboly.............................. 31 6.3 Poznámky.................................... 36 7 Dělení roviny a další rekurentní vztahy........................ 36 4 Obsah 7.1 Dělení roviny.................................. 37 7.2 Další rekurentní vztahy............................ 38 7.3 Poznámky.................................... 41 8 Dláždění roviny a další diofantické rovnice...................... 42 8.1 Nutná podmínka................................ 42 8.2 Lokální řešení.................................. 43 8.3 Globální řešení................................. 44 8.4 Poznámky.................................... 46 9 Periodické vzory a diskrétní grupy transformací................... 46 9.1 Frízové vzory.................................. 47 9.2 Poznámky.................................... 50 10 Trisekce úhlu a kořeny polynomů........................... 50 10.1 Algebra..................................... 50 10.2 Poznámky.................................... 51 II Zázemí a další příklady 53 11 Matematická indukce.................................. 53 11.1 Prostá matematická indukce.......................... 53 11.2 Silná matematická indukce .......................... 54 11.3 Poznámky a modifikace............................ 54 12 Dělitelnost........................................ 55 12.1 Věta o dělení se zbytkem ........................... 55 12.2 Eukleidův algoritmus a důsledky....................... 55 12.3 Kongruence................................... 55 12.4 Eulerova funkce a Eulerova věta ....................... 56 13 Kořeny polynomů aneb algebraické rovnice...................... 56 14 Diferenciální a integrální počty............................ 57 14.1 Limita, spojitost, derivace........................... 57 14.2 Riemannův a Newtonův integrál....................... 58 15 Diferenční a sumační počty.............................. 62 15.1 Diferenční počty................................ 62 15.2 Sumační počty................................. 64 15.3 Rekurentní vztahy aneb diferenční rovnice.................. 66 15.4 Poznámky.................................... 67 16 Nekonečné součty aneb řady.............................. 68 16.1 Vybrané poznatky............................... 68 16.2 Další poznatky................................. 70 17 Eukleidovské konstrukce................................ 70 17.1 Sestrojitelné veličiny.............................. 70 17.2 Kvadratura rovinných útvarů......................... 72 17.3 Slavné problémy starověku .......................... 74 18 Shodnosti v rovině................................... 76 Literatura 79 Seznam obrázků 81 Rejstřík 83 KAPITOLA I Příklady 1 Míchání karet a skládání permutací Některé karetní triky se dají vysvětlit, příp. vymýšlet s pomocí docela jednoduché, ale zajímavé matematiky. V této části rozebíráme řešení jednoho specifického problému spojeného s mícháním karet, jak je popsán v [Stí, kap. 11]. Všechny následující empirické údaje a grafy jsou dílem Š. Křehlíka. 1.1 Formulace problému Opakujeme-li míchání balíčku s N kartami aspoň AH-krát, pak výsledné pořadí karet musí být — podle Dirichletova principu — stejné jako některé z předchozích. Pokud mícháme pokaždé stejně a navíc pokud možno jednoduše, tak lze docela snadno a přesně zjistit, kdy znovu obdržíme původní pořadí karet. V následujícím se soustředíme na tzv. faro čili tkalcovské míchání: Balíček se sudým počtem karet se rozdělí na dvě stejné hromádky, z nichž se karty na střídačku poskládají do nové hromádky, a tento postup se nadále opakuje. Rozlišují se dva případy tkalcovského míchání podle toho, z které půlky rozděleného balíčku začínáme. Pořadí 123456 šesti karet se po jednom vnějším, resp. vnitřním tkalcovském míchání změní na 142536, resp. 415263. Při vnějším míchání zůstává vždy první a poslední karta na stejném místě a ostatní karty jsou míchány jakoby vnitřně. Studovat vnější míchání s N kartami je tedy totéž jako studovat vnitřní míchání s N — 2 kartami. Ve zbytku této části diskutujeme pouze vnější míchání — hledáme řešení následující úlohy: Úloha 1. Určete nějaké L tak, aby balíček s N kartami byl po L-krát opakovaném vnějším tkalcovském míchání opět uspořádán v původním pořadí. 6 I Příklady 1.2 Pokusy a postřehy Pokud začneme experimentovat s malými balíčky, zjistíme docela rychle, že výsledek se těžko odhaduje a ještě hůř zdůvodňuje. Začneme s přehledem několika odpovědí, ve kterých se následně pokusíme vyznat. Hodnota L uvedená v tabulce je nejmenší možná: N 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 L 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 N 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 L 36 12 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 Na obr. 1 pro představu znázorňujeme prvních 25 výsledků graficky (vodorovně N, svisle L). ♦ ■ Obrázek 1: na vodorovné ose N, na svislé ose L Na první pohled je patrný poměrně velký rozptyl hodnot, který se se vzrůstajícím N nadále zvětšuje. Naší pozornost zejména přitahují podezřele nízké hodnoty L odpovídající ./V = 2, 4, 8,16,32,..., což možná není náhoda. Pokud podrobněji zkoumáme, jak se mění pořadí karet po každém míchání, pak zjistíme následující: První a poslední karta z balíčku zůstávají při vnějším míchání na místě. Ostatní karty se objevují na různých místech a tvoří cykly různých délek. Např. • pro n = 6 najdeme jediný cyklus délky 4, • pro n = 8 dva cykly délky 3, jmenovitě (2, 5, 3) a (4, 6, 7), • pro n = 10 jeden cyklus délky 6 a jeden délky 2, jmenovitě (2, 6, 8, 9, 5, 3) a (4, 7), • pro n = 12 jediný cyklus délky 10, • atp. Hledané L je pak nejmenším společným násobkem délek těchto cyklů. V následujícím zkusíme odpovídající permutace popsat obecně. 1 Míchání karet a skládání permutací 7 1.3 Reformulace problému Pro obecné N určíme permutaci, která odpovídá jednomu vnějšímu tkalcovskému míchání balíčku s N kartami; tuto permutaci označíme P. Z definice vnějšího tkalcovského míchání plyne, že tato (jS> permutace funguje následovně: P(k) = 2k-l mod(iV-l), kde k G {1,..., N}. Opakování míchání nyní odpovídá skládání permutací. Přímým dosazením pozorujeme, že P2(k) = 4k-3 P3(k) =8k-7 P4(k) = 16Jfc — 15 > mod(iV-l). Tato pozorování potřebujeme zobecnit. Pomocí matematické indukce snadno dokážeme, že pro libovolné n e N platí <@J) Pn(k) = 2n(k-Í) + Í mod(N-í). (1) Ptáme se po kolika mícháních jsou karty v původním pořadí, neboli, pro které L je PL = id. Přitom PL = id právě tehdy, když PL(k) = k pro všechna k G {1,..., N}, což je vzhledem k (1) ekvivalentní s podmínkou 2L(k-í) + í = k mod(iV-l). Tato kongruence platí pro všechna k právě tehdy, když 2L = 1 mod(iV-l). (2) Celý odstavec tak můžeme uzavřít následující sympatickou ekvivalencí, jež charakterizuje řešení úlohy 1: Věta. Balíček s N kartami je po L-krát opakovaném vnějším tkalcovském míchání uspořádán v původním pořadí právě tehdy, když platí (2). 1.4 Řešení problému Díky uvedené reformulaci problému nyní najdeme jeho řešení. Protože N je zde vždycky sudé, jsou čísla 2aJV-l nesoudělná. Tudíž podle Eulerovy věty víme, že L = ip(N-l) je zaručeně řešením předchozí rovnice (ip je tzv. Eulerova funkce, viz odst. 12.4). Odtud mimochodem plyne, že L < N — 1, což je celkem slušný odhad, a to zejména ve srovnání s úvodním N\. Jak z praktických, tak i z teoretických důvodů nás samozřejmě zajímá nejmenší možné řešení. Nejprve si všimneme jednoduché nutné podmínky: Věta. Pokud je balíček s N kartami po L-krát opakovaném vnějším tkalcovském míchání uspořádán v původním pořadí a L je nejmenší číslo s touto vlastností, potom L dělí ip(N — 1). 8 I Příklady Důkaz. Vzhledem k charakterizaci ve Větě 1.3 stačí ukázat, že pokud L je řešením kongruence (2) a přitom L nedělí ip(N — 1), potom L není nejmenší možné. To je velmi snadné cvičení... □ <@j) Opačná implikace obecně neplatí a otázkou zůstává, který dělitel čísla ip(N — 1) odpovídá právě minimálnímu řešení úlohy. Pro srovnání doplníme část úvodní tabulky právě o hodnoty ip(N-í): N 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 L 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 f 1 2 4 6 6 10 12 8 16 18 12 22 20 18 28 30 20 24 N 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 L 36 12 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 f 36 24 40 42 24 46 42 24 Stejně tak doplníme předchozí grafické znázornění, viz obr. 2. 50 45 40 35 30 25 20 15 10 S o 10 15 20 25 30 35 40 45 50 55 Obrázek 2: na vodorovné ose N, na svislé L (čtverečky), resp. (p (trojúhelníčky) Vidíme, že minimální řešení někdy je a jindy není vlastním dělitelem hodnoty ip(N — 1). Vyznat se v tomhle obecně vypadá jako mnohem složitější problém: Úloha jj2. Určete nejmenší možné L tak, aby balíček s N kartami byl po L-krát opakovaném vnějším tkalcovském míchání opět uspořádán v původním pořadí. Obecným řešením téhle úlohy je právě nejmenší společný násobek čísel z definující rovnosti Eulerovy funkce, viz (42) na str. 56. Důkaz tohoto obecného výsledku necháváme pro obzvlášť (jS> zvídavé zájemce... Průměrně zvídavého čtenáře uspokojíme aspoň zdůvodněním jednoho z úvodních postřehů pro specifické počty karet: Věta. Pokud balíček obsahuje N = 2m karet, pak nejmenší možné L je rovno m. Důkaz. Vzhledem k předchozím rozvahám stačí ukázat, že L 2L = 1 mod (2m - 1), což je vskutku snadné. = m je nejmenším řešením rovnice □ 2 Přelévání vody a lineární diofantické rovnice 9 1.5 Poznámky Existují jiné a další karetní triky založené na specifických mícháních a jejich dokonalé kontrole. Za mnohými se opět skrývá zajímavá matematika...1 Jiný problém spojený s mícháním, který má potenciál k zajímavému zobecnění, lze najít např. v následující jednoduché úloze: <@j) Úloha 3 ([MO]). Recepční v hotelu si vykládala karty a dostala následující posloupnost: 5, 9, 2, 7, 3, 6, 8, 4. Přesunula dvě sousední karty na jiné místo tak, že tato dvojice opět sousedila, a to ve stejném pořadí. Tento krok provedla celkem třikrát, dokud nebyly karty uspořádány vzestupně podle své hodnoty. Zjistěte, jak recepční postupovala. 2 Přelévání vody a lineární diofantické rovnice Diofantické rovnice jsou algebraické rovnice ovšem řešené výhradně nad celými, příp. přirozenými čísly. Základní otázky zní: • Je daná rovnice řešitelná? • Pokud je rovnice řešitelná, má konečně nebo nekonečně mnoho řešení? • Je možné nějak koncepčně najít všechna řešení? Nejjednoduššími typy rovnic, pro které umíme uspokojivě odpovědět na všechny zmíněné otázky, jsou lineární diofantické rovnice, což jsou rovnice tvaru ax + by + • • • = h, (3) kde všechny koeficienty h,a,b,... jsou celá čísla a x, y,... jsou celočíselné neznámé. Pokud je taková rovnice řešitelná, pak má automaticky nekonečně mnoho celočíselných řešení. S jistými dodatečnými omezeními může mít jenom konečně mnoho řešení, které lze zpravidla najít systematickým zkoušením, viz odst. 2.4. 2.1 Úvod Úlohy vedoucí k těmto typům rovnic jsou velmi hojné a poměrně oblíbené. Pro příklad uvádíme jednu takovou typickou úlohu: Úloha 4. Najděte nějaký způsob, jak odměřit 10 litrů vody, pokud máte k dispozici neomezený zdroj vody, libovolně velkou pomocnou nádobu a dále (i) tři nádoby o objemu 4, 7 a 12 litrů, resp. (ii) dvě nádoby o objemu 4 a 7 litrů. Něco podobného řešil každý nejednou, takže se touto konkrétní úlohou moc zdržovat nebudeme; odpovídající diofantické rovnice jsou <@j) Ax + 7y + 12 z = 10, resp. Ax + 7y = 10. Pokud hledáme nějaké řešení, pak víc nádob znamená víc možností, a tudíž větší šance na úspěch. Pokud hledáme všechna řešení, pak je naopak jednodušší začít s menším počtem nádob, tedy neznámých. V tomto duchu povedeme následující diskuzi. 1http://www.ams.org/samplings/feature-column/fcarc-mulcahyl 10 I Příklady Uvažujme obecnou lineární diofantickou rovnici (3). Pokud koeficienty a,b,... na levé straně mají nějakého společného dělitele, který není dělitelem čísla h napravo, pak je jasné, že taková rovnice nemůže mít celočíselné řešení. Máme tedy jednoduchou nutnou podmínku řešitelnosti rovnice (3). V následujících odstavcích naznačíme, proč je tato podmínka také dostatečná. Tzn., že (poněkud neformálně) dokážeme následující tvrzení: Věta. Lineární diofantická rovnice (3) je řešitelná právě tehdy, když největší společný dělitel čísel a,b,... dělí číslo h. Pro rovnice s jednou neznámou věta evidentně platí a tímto případem se nemusíme zaobírat. Nejprve probereme rovnice se dvěma neznámými, poté naznačíme zobecnění. V každém případě budou následující argumenty konstruktivní, to znamená, že z nich vyplyne několik metod řešení. 2.2 Rovnice se dvěma neznámými Uvažme obecnou rovnici se dvěma neznámými ax + by = h, (4) pro niž předpokládáme, že NSD(a, b) dělí h. Chceme najít všechna řešení a současně si uvědomit, kde přesně předpoklad vstupuje do hry. Postřehy Pokud jsou a, b a, h dostatečně milá čísla, může se nám podařit nějaké řešení uhodnout; takové řešení označíme xp,yp. Uvědomte si, že to už vždycky stačí k tomu, abychom našli všechna řešení! Platí totiž, že dvojice x = —kb a y = ka je řešením homogenní rovnice ax + by = 0 pro libovolné fceZ. Odtud plyne, že dvojice x = xp — kb, y = yp + ka, pro k e Z, popisují nekonečně mnoho řešení rovnice (4). Pozor, to obecně neznamená, že jsme našli všechna řešení: může se stát, že mezi řešeními odpovídajícími sousedním hodnotám parametru k leží nějaké další řešení. V takovém případě je pak nutné uvedený popis zjemnit! (Rozmyslete si, kdy k takové situaci může dojít a kdy nikoli. Je možné upravit předchozí postup tak, aby tato @3> kontrola nebyla nutná?) Řešení pomocí Eukleidova algoritmu Jediné slabé místo předchozího postupu spočívalo v uhodnutí jednoho konkrétního řešení xp, yp. Z algebry bychom však měli vědět, že i když se nám nedaří žádné řešení uhodnout, tak určitě existuje (za předpokladu, že je splněna podmínka řešitelnosti rovnice): Podle tzv. Bezoutovy věty existují celá čísla k a l taková, že platí ak + bl = NSD(a,6), (5) 2 Přelévání vody a lineární diofantické rovnice 11 viz odst. 12.2. Pokud tedy NSD(a, b) = d dělí h, potom je zřejmé, že dvojice Xp~ ď Vv~ d je řešením rovnice (4). Všechna ostatní řešení je možné určit stejně jako v předchozím odstavci. Odtud vidíme, že diskutovaná podmínka je skutečně dostatečná k řešitelnosti diofantické rovnice (4). Podstatné je, že se nejedná pouze o teoretický výsledek, ale že všechny kroky byly konstruktivní — zdůvodnění Bezoutovy rovnosti je odvozeno z (rozšířeného) Eukleidova algoritmu k určení NSD celých čísel. Čísla k,l, a tedy i řešení xp,yp, lze vždy velmi efektivně spočítat bez ohledu na to, jaké jsou koeficienty v dané diofantické rovnici! Řešení pomocí kongruencí Vzpomeňme, jak by se rovnice (4) řešila nad tělesem reálných nebo racionálních čísel: Jednu neznámou prohlásíme za libovolnou, např. x, a druhou dopočítáme, h — ax y = —- (6) Nyní řešíme tutéž úlohu nad celými čísly, takže potřebujeme určit, pro která x e Z je taky číslo (6) celé. To je samozřejmě ekvivalentní s tím, že číslo h — ax je dělitelné číslem b. Najít nějaké takové x je možné systematickým zkoušením, přičemž stačí probrat nejvýše tolik možností, jaká je absolutní hodnota b. Všechna ostatní vyhovující x se pak opakují právě s periodou b. Takto se lze vždy dopracovat k popisu všech řešení, nicméně uvedený postup má několik nedostatků: Jednak se nám nelíbí ono zkoušení, jednak není příliš jasné, jakou roli zde hraje předpoklad řešitelnosti rovnice (4), tj. předpoklad, že NSD (a, b) dělí h. Proto přidáváme ještě jednu interpretaci. Podmínku, že „číslo h — ax je dělitelné číslem b", můžeme říct tak, že „zbytek po dělení čísla h — ax číslem b je 0" nebo taky „čísla ax a h mají po dělení číslem b stejný zbytek". Totéž stručně zapisujeme následovně: h — ax = 0 mod b, (7) ax — h mod b. Naše úloha je tímto transformována na řešení jedné kongruence s jednou neznámou. Podstatné pro nás je, že tento problém je opět velmi dobře prostudován, o čemž svědčí následující: Věta. Kongruence (7) je řešitelná právě tehdy, kdyžNSD(a,b) dělí h. Důkaz. Stejně jako ve Větě 2.1, je implikace zleva dopřávaje snadná (a snadno se ukáže nepřímo). Proto diskutujeme jenom druhou implikaci, tj. předpokládáme, že NSD(a, b) = d dělí h a chceme najít řešení. Pokud je d ^ 1, můžeme místo (7) psát ekvivalentní kongruenci ^x = -| mod ^, kde už jsou čísla | a ^ nesoudělná. Abychom nemuseli všechno přeznačovat, rovnou (bez újmy na obecnosti) předpokládáme, že NSD(a, b) = 1. Pro libovolné c ^ 0 je kongruence (7) ekvivalentní s c-ax = c-h mod b. Řešení určíme tak, že nedosazujeme libovolné, ale naopak nějaké vhodné c, řekněme 12 I Příklady kde ip : N —>• N je Eulerova funkce. Takto dostáváme a^Ett^-1-/! modb, což je podle Eulerovy věty totéž jako lEfl*'-1-/! modĎ. (8) To znamená, že x = ha^^^1 je řešením kongruence (7). Navíc všechna další řešení se liší právě o celočíselné násobky čísla b. □ Pokud tedy umíme vyjádřit hodnotu Eulerovy funkce (pro rovnice o n neznámých). Na rozdíl od případu se dvěma neznámými však může být docela problém rozhodnout, zda jsou řešení všechna, a předchozí popis případně zjemnit. Proto tuto myšlenku dál nerozvíjíme a zamyslíme se nad alternativním řešením. Obecné řešení pomocí kongruencí V tomto odstavci zobecníme předchozí elegantní užití kongruencí. Ukážeme, jak postupovat pro rovnice se třemi neznámými, jejichž obecné řešení je odvozeno výhradně z poznatků, které jsme formulovali výše pro rovnice se dvěma neznámými. Obecný indukční krok necháváme zájemcům (jS> k vlastnímu procvičení... 2 Přelévání vody a lineární diofantické rovnice 13 Řešení. Uvažujme obecnou rovnici se třemi neznámými ax + by + cz = h, (9) kde bez jakékoli újmy opět můžeme předpokládat, že NSD(a, b, c) = 1. Chceme ukázat, že tento předpoklad zaručuje řešitelnost rovnice (9). Pokud je trojice x, y, z řešením této rovnice, pak je také řešením každé kongruence ax + by + cz = h mod m, kde m je libovolné číslo. Pokud nyní za m dosadíme nikoli libovolné číslo, ale právě m := NSD(a, b), potom je tato kongruence ekvivalentní s cz = h mod m. (10) Protože NSD(to, c) je roven NSD(a, b, c), a ten je podle předpokladu roven 1, máme podle Věty 2.2 zaručenu řešitelnost této kongruence. Když ji vyřešíme a výsledek dosadíme do (9), dostáváme diofantickou rovnici se dvěma neznámými (x a y) a jedním volným celočíselným parametrem (který je schován ve vyjádření z): ax + by = h — cz. (11) V předchozích odstavcích jsme dokázali, že tato rovnice má celočíselné řešení právě tehdy, když NSD(a, b) = m dělí číslo h — cz na pravé straně. Protože však z je řešením kongruence (10), musí být h — cz násobkem čísla m. Proto má tato rovnice celočíselné řešení a navíc jsme se naučili několik způsobů, jak všechna řešení najít. Celkem tedy vidíme, že z předpokladu NSD(a, b, c) = 1 plyne řešitelnost rovnice (9). □ Opět zdůrazňujeme, že z uvedeného neplyne pouze řešitelnost diofantické rovnice, ale taky konkrétní návod, jak všechna její řešení určit! Úloha 5. Aplikujte všechny uvedené metody k určení všech řešení úlohy 4; porovnejte všechny výstupy. <@j) 2.4 Modifikace a poznámky Další typické úlohy, které vedou k lineárním diofantickým rovnicím, jsou úlohy s vážením na vahách, placením v obchodě, v restauraci apod. Tyto úlohy často obsahují dodatečné podmínky a omezení, které mohou skýtat dodatečné komplikace. Často taková omezení omezují výsledný počet řešení, jež je pak možné najít systematickým zkoušením. To samozřejmě není pro naše zkoumání úplně atraktivní, ale i zde se dá občas najít zajímavá matematika. Např. následující úlohu lze interpretovat jako hledání cesty v jistém orientovaném grafu.2 Úloha 6. Mezi všemi řešeními úlohy 4 najděte to, které je nejméně energeticky náročné. Řešte znova tutéž úlohu za předpokladu, že máte k dispozici pouze 12 litrů vody. Je možné, aby na ostrově zůstali jenom modří draci? Kolik by jich potom bylo? Úloha 9. Honza dostal kouzelný meč, kterým má zabít kouzelného trojhlavého a trojocasého draka. Drak je usmrcen, pokud má useknuty všechny hlavy a všechny ocasy. Kouzelné vlastnosti meče, resp. draka jsou tyto: • usekne-li se drakovi jeden ocas, narostou mu hned dva nové, • useknou-li se dva ocasy současně, naroste jedna hlava, • usekne-li se jedna hlava, narostou dvě nové hlavy, • useknou-li se dvě hlavy současně, nenaroste nic. Kolik nejméně seků potřebuje Honza k usmrcení draka? Kolik nejméně seků potřebuje Honza (jS> k usmrcení draka, aby měl nakonec stejně mnoho useknutých hlav jako ocasů? Společným rysem předchozích tří úloh je také to, že u případných rovnic se zajímáme pouze o kladná celočíselná řešení. Kanonickou úlohou tohoto typu je tzv. Frobeniův problém s mincemi, který může vypadat např. takto: Úloha 10. Útrata v obchodě je vyjádřena přirozeným číslem. Máme k dispozici pouze čtyřkoru-nové a sedmikorunové mince. Určete všechny možné částky, které není možné s těmito mincemi uhradit. Takových částek je jen konečně mnoho, tzn. od jisté hodnoty lze takto uhradit cokoli za předpokladu, že máme dost mincí. Jinými slovy, pro dostatečně velká h má rovnice (jS> vždy nějaké kladné celočíselné řešení. Protože se jedná o lineární úlohu se dvěma neznámými, můžeme si do jisté míry pomáhat obrázky, viz obr. 3. 4x + 7y = h 2 I 5 Obrázek 3: 4x + 7y = h Obecná formulace Frobeniova problému je tato:3 3http://en.wikipedia.org/wiki/Coin_problem 3 Pythagorejské trojice a nelineární diofantické rovnice 15 Úloha tttjll (Frobeniova). U rovnice (3) předpokládáme, že koeficienty a,b,... jsou kladná celá nesoudělná čísla. Určete největší možné h, pro které nemá tato rovnice kladné celočíselné řešení. Na rozdíl od dosud diskutovaných problémů, obecná odpověď na tento problém není známá. Pro rovnici se dvěma neznámými platí, že největší takové číslo je h = ab — a — b; zdůvodnění však není vůbec jednoduché...4 Pro a = 4 a b = 7 vychází vskutku h = 28 — 4 — 7 = 17. Úlohu 10 a následující úvahy můžeme formulovat také následovně (jakožto hezké procvičení matematické indukce): Úloha 12. Dokažte, že pro libovolné h > 18 má rovnice 4x + 7y = h řešení v oboru přirozených čísel. 3 Pythagorejské trojice a nelineární diofantické rovnice V následujících odstavcích si budeme povídat o několika nelineárních diofantických rovnicích. Začneme s tzv. Pythagorejskými trojicemi, což jsou řešení homogenní algebraické rovnice druhého stupně se třemi neznámými. Stručně se zmíníme o příbuzných rovnicích a o velké Fermatově větě. 3.1 Pythagorejské trojice Pythagorejské trojice jsou přirozená čísla, která jsou řešením rovnice x2+y2 = z2. (12) Pojmenování je zřejmě odvozeno z Pythagorovy věty, která říká, že v pravoúhlém trojúhelníku s odvěsnami délek x a y a přeponou délky z platí právě tato rovnost. Pythagorejské trojice lze proto interpretovat jako pravoúhlé trojúhelníky s celočíselnými délkami stran. Aspoň jeden takový trojúhelník zná úplně každý, totiž x = 3, y = 4, z = 5. Vidíme tedy, že (12) má řešení, a v tomto odstavci odpovíme také na zbylé otázky z úvodu podkap. 2: Úloha 13. Nejděte všechny pravoúhlé trojúhelníky s celočíselnými velikostmi stran, neboli najděte všechna kladná celočíselná řešení rovnice (12). Jednoduché postřehy a plán Protože rovnice (12) je symetrická vzhledem k x a y, dostaneme záměnou těchto dvou neznámých u libovolného jejího řešení opět řešení (např. x = 4, y = 3, z = 5). Proto se o pořadí x a, y zatím moc nestaráme, tuto dvojznačnost si uvědomujeme a časem nějak zafixujeme. Protože rovnice (12) je sudého stupně, dostaneme změnou znaménka u kterékoli neznámé libovolného jejího řešení opět řešení (např. x = —3, y = 4, z = 5). Proto se od začátku do konce staráme pouze o kladná řešení. Protože rovnice (12) je homogenní, dostaneme po vynásobení libovolného jejího řešení jakýmkoli přirozeným číslem opět řešení (např. x = 6, y = 8, z = 10). S každým řešením tedy 4http://www.ams.org/samplings/feature-column/fc-2013-08 16 I Příklady ihned máme nekonečně mnoho dalších řešení. Proto se v dalším budeme soustředit výhradně na "nejmenší možná" řešení, tj. řešení tvořená navzájem nesoudělnými čísly. Takovým řešením se říká primitivní řešení, příp. primitivní pythagorejské trojice. Z uvedeného vidíme, že pythagorejských trojic je nekonečně mnoho. Nejprve se přesvědčíme, že také primitivních pythagorejských trojic je nekonečně mnoho, posléze tuto množinu přesně popíšeme. Způsobů, jak generovat primitivní pythagorejské trojice, existuje celá řada. Mnohé jsou sice zajímavé, často však poměrně trikové nebo neúplné. My zde představíme jednu metodu, která je založena na zmíněné geometrické interpretaci a která nás navíc přivede k úplné charakterizaci. Částečné řešení Protože z 7^ 0, rovnice (12) je ekvivalentní rovnici Místo toho, abychom hledali celočíselná řešení rovnice (12), stačí se zajímat o racionální řešení rovnice p2 + q2 = í. (14) Za touto rovnicí vidíme jednotkovou kružnici se středem v počátku kartézské souřadné soustavy. Racionální řešení rovnice (14) tedy odpovídají racionálním bodům na této kružnici.5 Tvrdíme, že nekonečně mnoho takových bodů odpovídá nekonečně mnoha racionálním bodům na vhodné přímce. Toho lze dosáhnout např. pomocí stereograflcké projekce z bodu S = [—1, 0] na osu q: / r s\ 0 Obrázek 4 Pro libovolný bod A na kružnici je jeho stereografický obraz A' určen jako průsečík přímky S A s osou q. Předpokládejme, že bod A má souřadnice \p,q]. Potom na základě podobnosti (jS> trojúhelníků SBA a SO A' snadno vyvodíme, že obraz bodu A má souřadnice A' = 0, q i Odtud je zejména vidět, že bod A je racionální právě tehdy, když bod A' je racionální. Celkem tedy celočíselnému řešení rovnice (12) odpovídá racionální bod na kružnici, a tomu odpovídá racionální bod na ose q. Naopak, každý racionální bod na ose q určuje racionální 6 Racionálními body myslíme body, které mají obě souřadnice racionální. 3 Pythagorejské trojice a nelineární diofantické rovnice 17 bod na kružnici, a ten — po vynásobení jeho souřadnic vhodným číslem — určuje celočíselné řešení rovnice (12). Nás zajímají výhradně kladná řešení: ta odpovídají racionálním bodům na čtvrtkružnici v prvním kvadrantu,6 a ty odpovídají racionálním bodům na ose q ovšem pouze z intervalu (0,1). Tímto jsme zdůvodnili následující tvrzení: Věta. Kladné řešení diofantické rovnice (12) odpovídá nějakému racionálnímu číslu z intervalu (0,1), a naopak. Z uvedeného neplyne, že tato korespondence je vzájemně jednoznačná, a to ani v případě, že se omezíme pouze na primitivní řešení. Abychom se v problému vyznali úplně, bude nutné popsat inverzní zobrazení k stereografické projekci, která v této interpretaci hraje hlavní roli. Předpokládejme, že bod A' na ose q má souřadnice [0, r] a bod A na kružnici má souřadnice [p,q\; chceme vyjádřit p a, q pomocí r. Z výše uvedeného víme, že tato tři čísla jsou svázána rovnostmi q = r(í + p) a p2 + q2 = l. Dosazením první rovnice do druhé a obvyklými úpravami dostáváme (1 + r2)p2 + (2r2)p + (r2 - 1) = 0, což chápeme jako kvadratickou rovnici s neznámou p a parametrem r. Jedním kořenem této rovnice je zajisté p = — 1 (jakožto první souřadnice bodu S). Proto můžeme druhý kořen snadno vyjádřit pomocí Viětových vzorců a odtud — po dosazení do výše uvedené lineární rovnice — vyjádříme q: <@J) 1-r2 p = —ň, q - 1 + r2 1 + r2 Pokud tedy za r dosazujeme pouze racionální čísla z intervalu (0,1), tzn. r = kde to < n jsou přirozená čísla, potom po úpravě dostáváme: n2 — m2 2mn P=~,-2' 1=~,-2' (15) nz + toz nz + toz Po vynásobení obou těchto souřadnic společným jmenovatelem dostáváme kladné celočíselné řešení rovnice (12): x = n2 — m2, y = 2mn, z = n2 + m2. (16) Korespondence zformulovaná v předchozí větě tedy explicitně vypadá takto: • Kladné celočíselné řešení (x,y,z) rovnice (12) určuje racionální bod [p,q] = [f, f 1 na čtvrtkružnici, a ten určuje racionální číslo = z intervalu (0,1): {x, y, z) ^ z + x • Racionální číslo r = ^ z intervalu (0,1) určuje racionální bod [p, q] na čtvrtkružnici se souřadnicemi (15), a ten určuje kladné celočíselné řešení (16): — i—> (n2 — m2, 2mn, n2 + to2). 3Nebo taky ve třetím kvadrantu, který však ignorujeme kvůli větší přehlednosti a jednoznačnosti. 18 I Příklady Další postřehy a úplné řešení <@J) Ještě než začneme generovat pythagorejské trojice, můžeme si všimnout několika věcí: • Pokud je trojice (16) nesoudělná, čísla man musí být nutně nesoudělná. • Pokud je trojice (16) nesoudělná, čísla man musí mít nutně opačnou paritu (jedno sudé, druhé liché). V následující tabulce uvádíme několik pythagorejských trojic odpovídajích malým hodnotám m a n: m 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 n 2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 x 3 8 5 15 12 7 24 21 16 9 35 32 27 20 11 48 45 40 y 4 6 12 8 16 24 10 20 30 40 12 24 36 48 60 14 28 42 z 5 10 13 17 20 25 26 29 34 41 37 40 45 52 61 50 53 58 NSD 1 2 1 1 4 1 2 1 2 1 1 8 9 4 1 2 1 2 Z uvedeného vzorku to vypadá, že výše uvedené nutné podmínky jsou také dostatečné. Nyní ukážeme, že tento postřeh platí obecně, čímž dostaneme vytouženou úplnou charakterizaci primitivních pythagorejských trojic: Věta. Trojice x, y, z je primitivním řešením diofantické rovnice (12) právě tehdy, když platí (16), kde m < n jsou nesoudělná přirozená čísla opačné parity. Důkaz. V předchozím textu jsme zdůvodnili, že trojice (16) je řešením rovnice (12) a že každé řešení (12) je tvaru (16). Dále jsme ukázali, že pokud je trojice (16) nesoudělná, potom man musí být nutně nesoudělná čísla opačné parity. Stačí tedy dokázat opačnou implikaci, což uděláme nepřímo: Předpokládejme, že trojice (16) má společného (netriviálního) dělitele, kterého označíme d. Chceme odtud vyvodit, že čísla man jsou soudělná nebo mají stejnou paritu. Z předpokladu plyne, že d dělí také x + z = 2n2 a z — x = 2m2. To znamená, že d = 2 nebo d dělí n2 a současně d dělí m2: • Pokud d = 2, potom všechna tři čísla x, y, z jsou sudá. Z vyjádření x a, z plyne, že čísla m2 a n2 musí mít stejnou paritu, tudíž čísla man musí mít také stejnou paritu. • Pokud n2 a m2 mají společného dělitele, potom také n a m musí mít společného dělitele. □ 3.2 Příbuzné rovnice Varianta předchozí úlohy: Úloha 14 ([L]). Dokažte, že rovnice x2 + y2 = zn má kladné celočíselné řešení pro libovolné (j3> n = 1,2,3,... Podobně vyhlížející, avšak zcela jiná úloha: 4 Záhon zelí a konečné součty 19 Úloha jí 15 (Fermatova). Dokazte, že rovnice x4 + y4 = z4 nemá řešení v oboru přirozených čísel. Řešení. Nebudeme zabíhat do podrobností, ale aspoň zformulujeme hlavní myšlenky: (1) Dokážeme, že neexistuje pythagorejská trojice, jejíž některá dvojice by byla tvořena druhými mocninami nebo dvojnásobky druhých mocnin přirozených čísel. (2) Odtud plyne, že neexistuje řešení rovnice r2 + s4 = t4 v oboru přirozených čísel. (3) Odtud plyne, že rovnice x4 + y4 = z4 nemá řešení v oboru přirozených čísel. Implikace (1)=^(2) a (2)^>(3) se velmi jednoduše zdůvodní nepřímo. Důkaz tvrzení (1) podle principu nekonečného sestupu vypadá takto: Předpokládáme, že pythagorejská trojice se zmiňovanou vlastností existuje a označíme ji třeba (x,y,z). Podle toho, pro kterou dvojici tato vlastnost platí, rozdělíme diskuzi na tři případy. V každém z těchto případů vyvodíme, že existuje jiná pythagorejská trojice (x',y',z') s úplně <@J) stejnými vlastnostmi, pro kterou navíc platí z' < z. Stejným způsobem lze potom sestrojit další trojici (x",y",z") takovou, že z" < z', a takto by se dalo postupovat do nekonečna. To však není možné, protože všechna čísla z > z' > z" > ... jsou přirozená. Žádná pythagorejská trojice s uvedenou vlastností tedy existovat nemůže. □ 3.3 Poznámky Pyth. trojice: Eukleidés X.29 a další zdroje...7 Něco o dalších diofantických rovnicích se lze naučit např. z knih [HKS, Si]. Otázky, které jsme formulovali na začátku podkap. 2, jsou různě komplikované pro různé typy rovnic. Otázka řešitelnosti se proto v roce 1900 objevila jako 10. problém na slavném Hilbertově seznamu tehdy otevřených závažných matematických problémů.8 Nejslavnější ze všech diofantických rovnic je bezpochyby rovnice v následující úloze: Úloha jj|jl6 (Fermatova). Dokažte, že pro n > 2 nemá rovnice xn + yn = zn řešení v oboru přirozených čísel. Díky úloze 15 víme, že tvrzení platí, pokud n je násobkem 4. Zobecnění pro ostatní n se ukázalo být mnohem komplikovanější, než si autor úlohy pravděpodobně představoval. Tato úloha má velice zajímavou historii, která od formulace problému do jeho úplného vyřešení trvala více než tři století...9 4 Záhon zelí a konečné součty Osvědčenou skupinou úloh, na nichž lze trénovat jak standardní počtárske dovednosti, tak i míru ostrovtipu, jsou úlohy s doplňováním posloupností, určováním jejich součtů apod. Pro mnoho úloh tohoto typu existují také velice přímá a elegantní řešení, což si samozřejmě nenecháme ujít. Základní otázka zní: • Jak vyjádřit n-tý součet posloupnosti v uzavřeném tvaru? 7http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html 8http: //cs .wikipedia. org/wiki/Hilbertovy_probľ/,C3'/,A9my 9http: //cs .wikipedia. org/wiki/Velk'/.C3'/.Al_Fermatova_v'/.C4'/.9Bta 20 I Příklady Uzavřeným tvarem se myslí vyjádření „bez tří teček", neboli vyjádření v závislosti na n pouze pomocí elementárních funkcí. Tato podkapitola velmi úzce souvisí s podkap. 7; obecné zázemí hledejte v podkap. 15, příp. taky podkap. 11. Tady diskutujeme jenom několik nejmilejších typů posloupností, zevrubněji se tomuto tématu věnuje např. celá jedna kapitola v [HKS] nebo [L]... 4.1 Zahradnické počty Začněme s jednoduchou motivační úlohou (zatím bez posloupností): Úloha 17. Zahradník pěstuje zelí, a to vždy na nějakém čtvercovém záhoně se stejným počtem hlávek v každém řádku a každém sloupci. Letos vypěstoval o 113 hlávek více než vloni. Určete, kolik hlávek zelí letos vypěstoval. Řešení. Rozdíl výpěstků je rozdílem dvou čtvercových čísel, což můžeme vyjádřit jako n2 — m2 = (n + m)(n — m) = 113. Vzhledem k tomu, že 113 je prvočíslo, musí být n + m = 113 an — m = 1. Odtud plyne n = 57 (a m = 56), tedy n2 = 3 249. □ Jednoznačnost řešení plynula z předpokladu, že rozdíl výpěstků v letošním a loňském roce byl prvočíslem. Bezprostředním důsledkem bylo, že loňský záhon byl o jeden řádek a jeden sloupec menší než ten letošní. Nyní uvažujme následující variantu předchozí úlohy: Úloha 18. Zahradník pěstuje zelí, a to vždy na čtvercovém záhoně, který je každým rokem o jeden řádek a jeden sloupec větší. První rok vypěstoval 144 hlávek a letos vypěstoval o 113 hlávek více než vloni. Určete, kolikátým rokem pěstuje zahradník zelí a kolik hlávek za celou tu dobu vypěstoval. Řešení. Bavíme se o posloupnosti (an)^Li = (144,169,196,..., (n + ll)2,...). Máme určit, pro které n platí Aan = an — a„_i = 113, a pro toto n máme dále určit odpovídající součet sn = ai + a2 + ■ ■ ■ + an. Jednoduchou úpravou zjišťujeme, že Aan = (n + ll)2 — (n + 10)2 = 113 právě tehdy, když n = 46. Naopak, vyjádřit součet s46 = 122 + 132 + • • • + 572 (17) vyžaduje hodně trpělivosti, nějakou inteligentní úpravu nebo jiný nápad. Např. podle rovnosti (18), kterou záhy zdůvodníme, vychází s46 = (57-58-115 - 11-12-23) : 6 = 62 859. □ O několika metodách, jak vyjádřit součty typu (17) v uzavřeném tvaru, se obšírněji zmíníme v následujících odstavcích. Než tak učiníme, uvědomte si, že zelí se zpravidla sází do sponu, a (jS> řešte předchozí úlohu v této variantě... 4.2 Součet posloupnosti čtverců V tomto odstavci uvažujeme posloupnost (1,4,9,16,...), neboli (an) := (n2). Máme za úkol vyjádřit n-tý částečný součet n s„ = l + 4+ 9H-----hfi2 = ^i2 fe=i 4 Záhon zelí a konečné součty 21 v uzavřeném tvaru. Prvních několik členů posloupnosti částečných součtů vypadá takto: (sn) = (1,5,14,30,55,91,140, 204,285,385, 506,...). Tato posloupnost, tzv. posloupnost pyramidových čísel, je prostudována velmi zevrubně.10 V následujících odstavcích několika různými způsoby zdůvodníme, že platí: Věta. Pro libovolné n e N platí Efc2 = "("+D(2"+1). (18) fe=i Indukce Máme-li na základě experimentování nápad, jak by mohl vypadat n-tý člen posloupnosti (sn) v závislosti na n (nebo nám to někdo prozradí), potom můžeme tuto domněnku ověřit matematickou indukcí: Řešení (a). Pro m = 1 rovnost zřejmě platí. Předpokládáme, že rovnost platí pro m e N, chceme odtud ukázat, že platí také pro m + 1: <@j) m+l m fe=l fe=l + (m+l)2 = □ m(m+ l)(2ra+ 1) . ,2 (m+ l)(m + 2)(2m + 3) 6 Problém je, když nám nikdo nenapovídá a žádný nápad nepřichází. Proto představujeme další odvození... Vizualizace Často pomáhá vizualizace sčítaných čísel, příp. jejich vhodné přeskupení. Řešení (b). Dva příklady takového zdůvodňování, které nepotřebují žádné další komentáře, jsou na obr. 5 a obr. 6. □ <@j) Úpravy K témuž výsledku se lze dopracovat také různými početními úpravami pomocí drobných triků. n Např., pokud stávající úkol chápeme jako speciální případ obecnější úlohy — vyjádřit kr pro fe=i r e N —, potom se snadno ztotožníme s následující reduktivní myšlenkou: °http://oeis.org/A000330 22 I Příklady m. I_ WJrJ mm □ □ □ r i i i i i i i i i i i i Obrázek 5: 3(12 + 22 + • • • + n2) = (2n + 1)(1 + 2 + • • • + n) n + 1 Obrázek 6: 3(12 + 22 H-----h n2) = n(n + í)(n + \) Řešení (c). Podle binomické věty platí (k + íf = k3 + 3k2 + 3k + 1 neboli (k + íf - k3 = 3k2 + 3k + 1. Pokud tento nápad zopakujeme n-krát, a to pro k = 1,..., n, a všechny tyto rovnosti sečteme, potom dostaneme (n + l)3 - 1 = 3(H-----h n2) + 3(H-----h n) + n. Odtud vidíme, že součet kr Pro r = 2 je možné vyjádřit pomocí součtu téhož typu pro r = 1, fe=i a ten umí v uzavřeném tvaru vyjádřit skutečně každý. Odtud po jednoduchých úpravách skutečně (jS> dostaneme (18). □ 4 Záhon zelí a konečné součty 23 Přímé odvození Nejobecnější metoda, která nevyžaduje žádné speciální nápady ani představivost, je založena na pojmu primitivní posloupnosti a aplikaci základní věty sumačního počtu, viz odst. 15.2: Řešení (d). Primitivní posloupnost k posloupnosti (an) = (n2) z hlavy neznáme. Se značením jako v odst. 15.1, tj. pomocí n- = n a n- = n(n — 1), se však n2 dá vyjádřit takto: n2 = (n2 — n) + n = n- + n-. Podle (51) na str. 64 tedy určíme primitivní posloupnost, resp. neurčitý součet: E2 n± n- 3 2 Podle věty 15.2 už jenom dosadíme meze: (n + l)3 (n + l)2 13 l2 J2k2 = 3 2 3 2 fe=i _ (n + í)n(n - 1) (n + l)n n(n+í)(2n+í) ~ 3 + 2 ~ ~ 6 ' 4.3 Instantní zobecnění Většinu z právě uvedených myšlenek (zejména tu poslední) lze pohodlně zobecnit pro součty typu lr + 2r + ---+nr = Er' fe=i kde r e N. Tady shrnujeme několik ukázkových výsledků, které doporučujeme k samostatnému ověření: <@j) Věta. Pro libovolné n G N platí n n n(n+í)/2, n(n+ l)(2n-F l)/6, fc=l fc=l n n fe=i (19) J^k3 = n2(n+l)2/4, A:4 = n(n + l)(2n- f l)(3n2 + 3n- - l)/30. fe=i fc=i Možné zdůvodnění rovnosti odpovídající r = í, resp. r = 3 je na obr. 7, resp. obr. 8. 4.4 Další počitatelné příklady Každý výklad o posloupnostech obvykle začíná aritmetickou a geometrickou posloupností. Každá z těchto posloupností je definována jednoduchým rekurentním vztahem, jednoznačně je určena hodnotou jednoho libovolného členu, např. a\. Aritmetická posloupnost s diferencí d je definována rekurentním vztahem an+i = an + d. Jednu specifickou aritmetickou posloupnost jsme sčítali na obr. 7. 24 I Příklady o o o o o o o o • o o o d q o o octoq o o o do C!qjo o o do o o qo ooooooooo ooioooooio Obrázek 7: 1 + 2 2 / Ti liÄflI Obrázek 8: l3 + 23 H-----h n3 = (1 + 2 H-----h n)2 Úloha 19 (aritmetická). Dokazte, že pro aritmetickou posloupnost s diferencí d platí <@j) n(ai + an) an = a>i + (n — l)d a sTl (20) Geometrická posloupnost s kvocientem q je definována rekurentním vztahem an+1 = an-q. (jS> Úloha 20 (geometrická). Dokažte, že pro geometrickou posloupnost s kvocientem q platí l-qn an = aiq n-l a sn = ai- í-q (21) Uvědomte si, že v obou případech lze jako obvykle argumentovat mnoha rozličnými způsoby. (jS> V duchu předchozích odstavců bychom měli vidět alespoň čtyři různé metody! (Několik cvičení s aritmetickou a geometrickou posloupností ještě absolvujeme v podkap. 15, viz např. úlohu 56 na str. 65.) Příliš mnoho posloupností, s nimiž bychom si uměli poradit tak jako s výše uvedenými, neznáme. Tady připomeneme jenom několik dalších typů, se kterými jsme se většinou již někde potkali. U každé úlohy uvádíme dvě metody řešení, o dalších doporučujeme aspoň krátce zapřemýšlet. .. Úloha 21 (aritmeticko-geometrická). Vyjádřete n-tý částečný součet posloupnosti an = a domyslete nějaká přirozená zobecnění. 4 Záhon zelí a konečné součty 25 Řešení, (a) Podobnou úpravou jako při jednom z řešení úlohy 20 lze vyjádřit 111 lni ts„ = - + - + ■■■ + ---—v = 1 2 2 4 2™ 2n+1 V 2™ / 2™+1 Odtud se již snadno vyjádří sn... Obecnější posloupností, na niž lze aplikovat tento typ úprav, je jakákoli posloupnost, jejíž n-tý člen je součinem odpovídajícího členu nějaké aritmetické a nějaké geometrické posloupnosti (odtud název úlohy)... (b) Pro posloupnosti tohoto typu lze taky docela snadno vyjádřit primitivní posloupnost, tudíž jakýkoli součet lze snadno vyjádřit dosazením podle věty 15.2. V tomto případě platí <@j) ^ n_ = n + 1 po dosazení a úpravě dostaneme tentýž výsledek jako v předešlém řešení... □ Úloha 22 (Leibnizova). Vyjádřete n-tý částečný součet posloupnosti an = n^+i) a domyslete nějaká přirozená zobecnění. Řešení, (a) K vyřešení a zobecnění tohoto součtu významně přispívá tento postřeh: 1 1 1 (22) n(n +1) n n + 1 Vyjádření an v závislosti na n je racionální a rozklad tohoto výrazu na parciální zlomky je náhodou takový, že většina sčítanců v sn = ai + ■ ■ ■ + an se vyruší; konkrétně vychází 1 n sn = l--—7 = -—7- Tento postřeh současně naznačuje přirozená zobecnění tohoto postupu. (b) Na pravé straně (22) samozřejmě rozeznáváme (až na znaménko) diferenci posloupnosti (i). Podle věty 15.2 tedy platí fe=1 n(n+1) n+1 , =--- + 1. □ ! n+1 4.5 Problematické příklady Posloupností, pro které je možné vyjádřit jejich libovolný konečný součet v uzavřeném tvaru, je sice hodně, ale v žádném případě to nejsou všechny. Obecně je to tak, že funkce vyjadřující sn v závislosti na n jsou zpravidla vyšší transcendentní funkce, a to i v poměrně nevinně vyhlížejících případech:11 n Úloha 23. Dokažte, že pro žádné r > 0 neumíte vyjádřit w v uzavřeném tvaru. 2 platí 1 1 1 k(k + í) k2 (k-í)k' tudíž stejné nerovnosti platí také pro jakékoli odpovídající součty. Součty, které omezují hledanou hodnotu, však umíme vyjádřit podle řešení úlohy 22: n 1 n 1 O 1 n 1 El n >—^ 1 In — 1 >—^ 1 jfc(jfc +1) = íT+T < ^ ä* < ~= + ^ (k-1)*' ^ ' fe=l V ; fe=l fe=2 V ; □ K tomuto problému se ještě vrátíme v úlohách 29-30, odkud by mělo být patrné, že tutéž věc lze dělat různým způsobem a že příslušný odhad je možné podle potřeby zpřesnit... 5 Achilles, želva a nekonečné součty V této podkapitole se snažíme domýšlet výše diskutované úkoly ad infinitum. Doplňující otázka k té, kterou jsme formulovali na začátku podkap. 4, zní: • Co se stane, když n —>• oo? Obecné zázemí k této části hledejte v podkap. 16. 5.1 Achilles a želva Nelze začít jinak než následujícím klasickým problémem: Úloha 25 (Zénónova). Zjistěte, jak rychle běhal Achilles a jak želva ve slavném Zénónově závodě. Dokažte, že Achilles želvu určitě doběhne a v závislosti na želvím náskoku určete kde. Obrázek 9 Řešení. Schválně odkazujeme na Zénónovu interpretaci, aby nás to navedlo k nekonečnému součtu. Předpokládejme, že Achilles i želva běží konstantní rychlostí, Achilles je p-krát rychlejší než želva (p > 1), a ta má na startu náskok a\. Než Achilles uběhne vzdálenost a\, želva se (jS> posune o vzdálenost a2 = než Achilles uběhne vzdálenost a2, želva se posune o a3 = ^ atd. 5 Achilles, želva a nekonečné součty 27 Vzdálenost, kterou Achilles urazí, než želvu doběhne, je rovna s := ai+ a2 + &3 oo = J2ak- k=l Protože posloupnost (an) je geometrická, s kvocientem q = i, umíme její n-tý součet vyjádřit v uzavřeném tvaru podle (21). Protože q = i < 1, platí lim qn = 0 a, hledaný nekonečný součet je roven 1 p s = Ci\--= ßl" 1 — q p — 1 □ V řešení úlohy jsme si připomněli standardní odvození součtu (konvergentní) geometrické řady. Vzhledem k jeho důležitosti, výsledek náležitě zvýrazníme: Věta. Geometrická řada s kvocientem q je konvergentní právě tehdy, když \q\ < 1; v takovém případě je její součet roven ^ fe-i i- !-9n 1 > ciiq = lim cii- = ai —^ n—>oo 1 — n k=l y í-q Alternativní odvození téhož je naznačeno na obr. 10 (kde kvocient je označen r)... Obrázek 10: (a + ar + ar2-\----) : (±) = (ar) : (1 - r) S touto poznámkou bychom si měli uvědomit, že k vyřešení předchozí úlohy určitě není nutné manipulovat s nekonečnými součty. Návod tkví ve formulaci úkolu: Úloha 26 (ad 25). Zjistěte, jak rychle běhal Achilles a jak želva ve slavném Zénónově závodě. Dokažte, že Achilles želvu určitě doběhne a v závislosti na želvím náskoku určete kdy. (™) aP°d- k=l k=l Řešení. Z vyjádření částečných součtů sn= E ak v řešení úloh 21 a 22 plyne: fe=i ^ 2k n^oo \ 2™"1 2™ fe=l oo ^ ^ k(k + í) = lim 1 — = 1. £—^k(k + l) n^rco y n+1 Zobecnění ve výše zmiňovaném duchu doporučujeme jako užitečné cvičení... □ Úloha 28 (ad 23). Dokažte, že pro každé r > 0 umíte rozhodnout, zda řada E konverguje k=l či diverguje. Řešení. Tady se nejlépe hodí integrální kritérium... _ v oo (jS> Závěr je následující: Rada E w konverguje právě tehdy, když r > 1. fe=i Ilustrace k meznímu případu odpovídajícímu r = 1 je na obr. 11. □ 1 2 3 4 5 6 Obrázek 11: / i dx< Es ( < / ^ i k—i Úloha 29 (ad 24). Dokažte, že umíte odhadnout hodnotu součtu ^ ^ a ie tento odhad umíte k=l libovolně zpřesnit. 5 Achilles, želva a nekonečné součty 29 Řešení. Díky přímému srovnání v (23) víme, že platí n „ 1 2n — 1 hni-- = 1 < > — < 2 = lim -. n^oo n + 1 z—' K n^oo n k=l Tento odhad lze jednoduše zpřesňovat tak, že předchozí srovnání neprovádíme od k = 1, ale podle potřeby od 2, 3,.... Na základě předchozího počítání snadno doplníme <@j) OO-. -.OO-. OO-. El 1 v -v 1 1 v -v 1 k(k + í) ~ l<^k2~ 1 umíte odhadnout hodnotu součtu ^2 a že k=l tento odhad umíte libovolně zpřesnit. Řešení. O konvergenci této řady jsme v úloze 28 rozhodli pomocí integrálního kritéria. Místo, abychom jako v předchozí úloze srovnávali řadu s jinou konvergentní řadou, můžeme hodnotu hledaného součtu odhadnout pomocí vhodných integrálů. Protože všechny sčítance v řadě jsou kladné a postupně klesající, pro libovolné i > 2 platí 00 1 oo ^ °° 1 — dx < N — < / -dx xr ^ kr J (x - 1Y Nevlastní integrály na obou stranách se snadno dopočítají, odtud dostaneme nějaký odhad, a ten lze dále libovolně zpřesňovat... □ <@j) 5.3 Poznámky K vyčíslení součtu Způsob argumentace v předchozích úlohách je spíše pravidlem než výjimkou: Často umíme poznat, že nekonečná řada má reálný součet, ale nejsme schopni určit přesně jaký. Důvodem bývá to, že neumíme určit posloupnost částečných součtů, tudíž nemůžeme počítat její limitu. Nicméně každé z kritérií, pomocí něhož o konvergenci dané řady rozhodujeme, nám vždy současně nabízí jakýsi odhad celkového součtu, a to s libovolnou přesností! <@j) Přestože např. řada v úloze 29 je právě tohoto typu, je kupodivu možné její součet vyjádřit přesně: Úloha ttt)31 (Eulerova). Dokažte, že platí 5ľ 12 k2 6 ' fe=i Toto tvrzení lze zdůvodnit mnoha způsoby, všechny jsou však netriviální a poměrně rafinované. ..12 http: //math, stackexchange. com/quest ions/8337/dif f erent-methods -to - compute - sum- limits -n-1- inf ty-f racln2 30 I Příklady Na druhé straně existují řady se stejnými vlastnostmi, jejichž součet však lze určit poměrně snadno. Máme na mysli zejména řady, které vzniknou dosazením konkrétních hodnot do Tay-lorova rozvoje některé elementární funkce. Takto lze např. vyjadřovat iracionální (či transcendentní) čísla jakožto součty řad čísel racionálních. Tady uvádíme několik dobře známých ukázek: (j3> Úloha 32. Dokažte, že OO (i) Eá = i + | + š + á + "- = e» fe=0 (H) E^P = l-| + §-Í + --- = ln2, fe=i fe=l (iv) apod. K použitým kritériím Uvědomte si, že užití integrálního kritéria má jistá omezení: Jednak funkce, která interpoluje danou posloupnost musí být kladná a klesající. Hlavně však obecně čelíme podobným nástrahám jako v poznámce před úlohou 23 — neurčité integrály k mnoha elementárním funkcím jsou vyšší transcendentní funkce. Vzpomeňte na některé typické příklady... Kromě integrálního a srovnávacího kritéria si jistě ještě vzpomínáme na kritérium podílové a odmocninové (pro alternující řady ještě Leibnizovo). Uvědomte si, čím byla tato dvě kritéria @3> motivována a proč je jejich užití u většiny předchozích úloh k ničemu... 6 Kvadratura mnohoúhelníku a integrální počty Podstatnou část této podkapitoly můžeme chápat jako volné pokračování té předchozí — nekonečné součty se přirozeně objevují při vyjadřování obsahů (křivých) rovinných útvarů. Základní otázka zní: • Jak vyjádřit obsah (měřitelného) rovinného útvaru? Tomuto problému se přezdívá kvadratura rovinného útvaru. Pojmenování odkazuje do klasických časů, kdy se obsah nevyjadřoval reálným číslem jako dnes, ale odkazem na nějaký jednodušší útvar, např. čtverec. Konstrukci čtverce, který má stejný obsah jako daný útvar, budeme nazývat geometrickou kvadraturou; vyjádření obsahu reálným číslem (vzhledem k dané jednotce) budeme nazývat analytickou kvadraturou. Několik obecných poznámek k tématu lze najít v odst. 17.2 a odst. 14.2... 6.1 Kvadratura mnohoúhelníku Analytická kvadratura jakéhokoli mnohoúhelníku je v podstatě nezajímavá, tudíž diskutujeme pouze kvadraturu geometrickou. Pro obecné mnohoúhelníky lze navíc každou takovou úlohu názorně řešit pomocí nůžek... Úloha 33 ([Po]). Kříž na obr. 12 je stvořen z pěti shodných čtverců. Rozdělte kříž (i) několika, (ii) dvěma řezy a ze vzniklých částí složte jeden čtverec. 6 Kvadratura mnohoúhelníku a integrální počty 31 Obrázek 12 Řešení, (i) Bez omezení na počet řezů se jedná o standardní cvičení k větě 17.2... (ii) Pokud je počet řezů nějak omezen, musíme přemýšlet trochu intenzivněji; v tomto případě může pomoci následující postřeh: Ozn. stranu daného mnohoúhelníku a a stranu hledaného čtverce x. Podle zadání má platit x2 = ba2 = a2 + (2a)2. Pokud nám toto vyjádření připomíná Pythagorovu větu, pak neznámou veličinu x v zadaném mnohoúhelníku snadno najdeme a požadované řezy podle toho doplníme... □ <@j) 6.2 Kvadratura paraboly V celém tomto odstavci se zabýváme kvadraturou paraboly, čímž myslíme kvadraturu obrazce omezeného parabolou a přímkou (příp. několika přímkami)... Úloha 34 (parabolická). Určete obsah parabolické úseče. Přístup Archimédův Úloha 34 byla poprvé vyřešena Archimédem (ve 3. století př. Kr.), a to několika způsoby, jejichž hlavní myšlenky zde stručně představíme. K jejich úplnému pochopení potřebujeme několik jednoduchých vlastností paraboly, které na příslušných místech zmíníme. Archimedovo geometrické řešení spočívá v postupném vyčerpávání parabolické úseče vepsanými trojúhelníky, jak jest naznačeno na obr. 13. Parabolická úseč je zde vymezena tětivou Qq. Obrázek 13 První vepsaný trojúhelník je PQq, přičemž bod P je určen tím, že tečna paraboly v tomto bodě 32 I Příklady je rovnoběžná s Qq. (Takový bod se nazývá vrcholem parabolické úseče.13.) Rozdíl mezi původní úsečí a trojúhelníkem PQq sestává právě ze dvou menších úsečí vymezených úsečkami PQ a Pq, do nichž jsou vepsány trojúhelníky PQR a Pqr. Každý z těchto trojúhelníků zaujímá víc než polovinu plochy odpovídající úseče. Opakováním tohoto postupu je tudíž možné aproximovat obsah dané úseče s libovolnou přesností. Ukážeme, že: Věta. Obsah parabolické úseče určené tětivou Qq je roven 4/3 obsahu trojúhelníku PQq, kde P je vrchol úseče. Řešení (a). Vyjádříme posloupnost obsahů trojúhelníků, kterými postupně úseč vyplňujeme: V prvním kroku máme trojúhelník PQq, jehož obsah označíme a\ (= si). Ve druhém kroku přidáváme dva trojúhelníky PQR a Pqr, jejichž součet obsahů označíme (jS> a2. Z geometrických vlastností paraboly se dá vyvodit, že SpQR = Spqr = ^SpQq. To znamená, že a2 = \a\ a obsah vepsaného mnohoúhelníku PRQqr je roven s2 = &i + \a-\_. V dalším kroku přidáváme čtyři trojúhelníky, jejichž součet obsahů označíme a3. Ze stejného důvodu jako výše mají všechny tyto trojúhelníky stejný obsah, který je roven osmině obsahu (libovolného) trojúhelníku z kroku předcházejícího. Platí tedy a3 = \a2 a obsah odpovídajícího vepsaného mnohoúhelníku je s2 = a\ + + j^ai- V n-tém kroku přidáváme 2™ trojúhelníků, jejichž součet obsahů je roven an = |a„_i, a obsah odpovídajícího mnohoúhelníku je S" = fll + I + á + + Odtud pro n —>• oo dostaneme obsah parabolické úseče. Tady však jasně rozeznáváme geometrickou řadu s kvocientem ^, kterou bez problému sečteme: Susece = Ľni Sn = --í-y = ~SpQq. (25) Archimedovo mechanické řešení je založeno na rafinovaném vyvažování parabolické úseče a jistého trojúhelníku, jak jest naznačeno na obr. 14. Parabolická úseč je zde opět vymezena tětivou Qq. Přímka QE je tečnou paraboly v bodě Q, všechny svislé čáry jsou rovnoběžné s osou paraboly a naznačují dělení (a aproximaci obsahu) dané úseče, které lze podle potřeby libovolně zjemňovat... Řešení (b). Z geometrických vlastností paraboly se dá vyvodit, že pro libovolnou přímku rovno-@3> běžnou s osou paraboly platí OíRí : OíEí = O.q : Qq, (26) kde Oí,Rí, rep. Ei jsou průsečíky přímky s tětivou, parabolou, resp. tečnou jako na obrázku. Na páku Q A, která je podepřená v bodě O a O A = OQ, ještě doplníme body Hi. Předchozí poměr můžeme (na základě podobnosti trojúhelníků) vyjádřit také jako HiO : QO, či O H i : O A. Proporce (26) je tedy ekvivalentní s rovností OlRl-OA = OíEí-OHí. 13Vrchol parabolické úseče je vrcholem paraboly, právě když je tětiva kolmá k ose paraboly. 6 Kvadratura mnohoúhelníku a integrální počty 33 Tuto rovnost můžeme přeložit jako rovnováhu mezi tenounkým plátkem OíRí parabolické úseče umístěném na páce v (pevném) bodě A a tenounkým plátkem OíEí trojúhelníku EQq umístěném v (proměnném) bodě iíj. Po „sečtení" (integraci) tak dostáváme rovnováhu mezi celou parabolickou úsečí působící v bodě A a trojúhelníkem EQq spojitě působícím na druhém rameni. Působení trojúhelníku na pravém rameni je stejné, jako kdyby celý působil v jediném bodě odpovídajícím těžišti. Tento bod se nachází v jedné třetině mezi O a, Q (blíže k O). Platí tedy S useče ■ O A = S EQq ' - OQ, neboli Susece = -^SEQq- (27) Ó □ Vztah (27) představuje uspokojivou odpověď na zadání úlohy 34. Abychom se přiblížili výše formulovanému vyjádření, stačí si uvědomit, jaký je vztah mezi trojúhelníky, které se objevovali v řešení (a) a (b): Z geometrických vlastností paraboly — a to právě těch, které byly použity v uvedených řešeních — bezprostředně vyplývá, že <@j) SEQq — ^SpQq, viz obr. 15. Odtud tedy vidíme, že rovnosti (25) a (27) jsou ekvivalení. Přístup Fermatův Tutéž úlohu řešil také Pierre de Fermat, avšak v trochu jiném kabátě: Místo na úseč paraboly se nejprve soustředíme na oblast, která je k ní vzhledem k opsanému trojúhelníku jako na obr. 15 34 I Příklady Obrázek 15 komplementární. Abychom eliminovali nepodstatné technické drobnosti, uvažujeme parabolu určenou grafem funkce y = x2 s body Q = [0,0] ag = [1,1] (a tedy E = [1,0]). Obsah diskutované oblasti označíme Skomp; zřejmě platí skomp + susece = sEQq = -. Řešení (c). Pro libovolné a e (0,1) uvažujme posloupnost čísel (a, a2,a3,...). Tato posloupnost konverguje k 0 a platí 1 > a > a2 > • • • > 0; interval (0,1) je tak rozdělen na nekonečně mnoho postupně se zmenšujících podintervalů. Diskutovaný útvar je pokryt nekonečně mnoha obdélníky s výškami rovnými funkčním hodnotám y = x2 v pravých krajních bodech těchto podintervalů, viz obr. 16. Součet obsahů všech těchto obdélníků je roven Obrázek 16 Sa := (1 - a)l + (a - a2)a2 + (a2 - a3)a4 H----= (1 - a)(l + a3 + a6 H----). Tato řada je geometrická, s kvocientem a3 < 1, pročež ji umíme snadno sečíst: _ 1 - a 1 — ad 6 Kvadratura mnohoúhelníku a integrální počty 35 Z konstrukce plyne, že Sa je horním odhadem hledaného obsahu P, který je tím přesnější, čím menší jsou základny pokrývajících obdélníků. Pro a —>• 1 tedy dostaneme výsledek: komp = lim 1 — a i 1 - a3 Odtud zejména plyne S III '-'useče . * ., r. i Zob což je v naprostém souladu s (27)... □ Přístup Riemannův Pokračujeme se stejnými konvencemi jako v předchozím přístupu. Řešení (d). Jiný způsob pokrytí diskutované oblasti je na obr. 17: Zde je interval (0,1) rozdělen l/i '/? V/2. v3 % 1 Obrázek 17 na šest stejně dlouhých podintervalů, z nichž každý tvoří stranu jednoho z pokrývajících obdélníků. Součet obsahů těchto šesti obdélníků je horním odhadem hledaného obsahu Skomp a je roven 1/1 1 1 4 25 \ S6:=6U+9 + 4 + 9 + 3li+1)=--- Tento odhad lze zpřesnit tak, že základní interval rozdělíme na více podintervalů: pokud jej rozdělíme na n stejně dlouhých podintervalů (s hraničními body 0<^<^<-• oo. Vyjádřit tento součet v uzavřeném tvaru není tak snadné jako v případě geometrické posloupnosti, ale možné to je — viz Větu 4.2. Odtud plyne, že o _ i:„ o _ i:„ n(n+l)(2n+l) 1 ^komp lim S„ lim 6n3 □ Protože funkce f(x) = x2 je spojitá, je riemannovsky integrovatelná a v uvedeném řešení i jsme nespočítali nic jiného, než J x2 dx = |. Z definice riemannovské integrovatelnosti víme, 36 I Příklady že výsledek nezávisí na tom, jakou posloupnost dělení a jaký výběr reprezentantů (určujících aproximující obdélníčky) volíme. Jako užitečné cvičení doporučujeme dopočítat totéž pomocí dolních nebo nějakých obecnějších součtů... Přístup Newtonův a Leibnizův Pokračujeme se stejnými konvencemi jako v předchozím přístupu, ovšem s naprosto novými myšlenkami: Experimentováním s diferencemi posloupností a určováním konečných součtů, resp. přemýšlením nad vztahem mezi okamžitou rychlostí pohybu a délkou dráhy, kterou sledovaný objekt za daný interval urazí, přišel G. W. Leibniz, resp. I. Newton k první verzi zásadního tvrzení, které dnes nazýváme základní větou matematické analýzy, příp. Newtonovou-Leibnizovou větou (viz odst. 14.2)... Řešení (e). Funkce f(x) = x2 je na intervalu novsky integrovatelná a platí Funkce f(x) = x2 má primitivní funkci F(x) = ^- (+ libovolná konstanta). Podle Newtonovy-Leibnizovy věty platí i J x2dx = o 6.3 Poznámky (jS> Odvodit nedokázaná tvrzení o parabole, např. analyticky... Upravit pořadí chronologicky + pozn. Eudoxos, Cavalieri, Cauchy, ... b b Co takhle J x2 dx, resp. J xr dx, ... ? a a Co takhle kvadratura kruhu, příp. kruhové úseče? 7 Dělení roviny a další rekurentní vztahy V této podkapitole navazujeme na některé problémy, které jsme potkali už v podkap. 4. Základní otázka zní: • Jak vyjádřit n-tý člen posloupnosti, která je zadána rekurentním vztahem? Uvědomte si, že základní otázka podkap. 4 je jen speciálním případem té stávající: Posloupnost částečných součtů (sn) libovolné posloupnosti (an) je určena právě rekurentním vztahem sn+i = sn + an+1, kde s1=a1. Opět se jedná o problémy induktivního charakteru, takže se opět budeme soustředit hlavně na velmi typickou potíž: • Co dělat, když je naše indukce krátká? Obecné zázemí hledejte v odst. 15.3... (0,1) spojitá, proto je na tomto intervalu rieman- í = J x2 dx. o x y □ 7 Dělení roviny a další rekurentní vztahy 37 7.1 Dělení roviny Jedna přímka rozděluje (eukleidovskou, příp. afinní) rovinu na dvě nesouvislé části. Dvě přímky rozdělují rovinu na nejvýše 4 části (právě když přímky nejsou rovnoběžné). Tři přímky vymezují nejvýše 7 částí (právě když jsou každé dvě navzájem různoběžné) atd. 2 4 7 11 n =\ n = 2 n = 3 n = 4 Obrázek 18 Ptáme se, jak tato pozorování zobecnit: Úloha 35. Určete, na kolik nejvýše částí může být rozdělena rovina právě n přímkami. Obecně platí, že přidáme-li k n přímkám v rovině jednu další, můžeme dostat nejvýše n + 1 nových částí. Odpovídající posloupnost maximálního počtu částí v závislosti na počtu přímek je <@j) (an) = (2,4, 7,11,16, 22, 29, 37,46, 56, 67, 79, 92,106,121,... ).14 Tato posloupnost je zcela určena rekurentním vztahem an+i = a„ + (n + 1), kde a\ = 2. (29) Otázka zní, jak odtud obecně vyjádřit an? Indukce Začali jsme induktivně, můžeme zkusit v tomto duchu pokračovat: Řešení (a). Pokud si napíšeme několik dalších členů posloupnosti (a„), můžeme si všimnout, že součin n(n + 1) je vždy sudý a jeho polovina se liší od an o 1: n(n+í) an = -^--^ 1- Tento postřeh skutečně platní obecně, což lze snadno ověřit matematickou indukcí... □ <@j) Úpravy Definující vztah (29) je docela jednoduchý, takže můžeme zkusit na něco přijít rekurzivním, tj. zpětným dosazováním: Řešení (b). Takto postupně dostáváme Cín = fln-1 + n = ftn-2 + (n-í) +n = ai+2 + 3H-----\-(n-l) + n. 14http://oeis.org/A000124 38 I Příklady Na posledním řádku vidíme součet několika členů aritmetické posloupnosti a ze zadání víme, že a\ = 2. Odtud tedy plyne o , (n-í)(n + 2) an = 2 H----. U Přímé odvození Definující rovnost (29) můžeme přepsat jako Aan = n + 1, což by nám mělo připomenout obecné závěry odst. 15.2. Řešení najdeme pomocí primitivní posloupnosti k aritmetické posloupnosti (n + 1): Řešení (c). Podle (51) na str. 64 víme, že an = — + n + C. Protože ai = 2, musí být C = 1. Celkem tedy dostáváme n(n — 1) ,_, an = ^-^-L+n+í. □ Závěr Závěr, který jsme právě trojím způsobem odvodili, zní takto: Věta. Rovina může být rozdělena n přímkami nejvýše na an částí, kde n2 + n + 2 Hodnotu an jsme vyjádřili pokaždé jinak, takže pokud to ještě někdo neudělal, doporučujeme (jS> všechna tato vyjádření porovnat. Za pozornost stojí, že totéž číslo lze vyjádřit také takto: n\ In\ in 0"n = ... ... 2 VI/ VO To signalizuje, že výsledek lze odvodit ještě jiným způsobem... 15 7.2 Další rekurentní vztahy V tomto odstavci zmíníme několik dalších typických úloh s rekurentními vztahy. Zamyslíme se zejména nad možnostmi a omezeními výše diskutovaných metod. 7 Dělení roviny a další rekurentní vztahy 39 Obrázek 19 Hanojské věže Úloha 36 (Lucasova). Najděte obecné řešení problému známého jako hanojské věže16 ve variantě se třemi kolíky. Experimentováním s malými počty pater si každý vytvoří nějakou hypotézu, jak by to mohlo fungovat obecně. Pro n-patrovou věž označíme an počet tahů, které stačí k přemístění této věže. Rádi bychom vyjádřili an v závislosti na n. Postupně zjišťujeme, že platí cii = 1, a2 = 3, a3 = 7 atd.17 Obecně, věž o n + 1 patrech můžeme přemístit tak, že nejprve přeskládáme horních n pater, poté přemístíme spodní patro a na něj naskládáme zpět n pater. Vzhledem k zavedenému značení tedy platí an+i = 2an + 1, kde a± = 1. (30) Řešení (a). Na základě úvodního experimentování si můžeme všimnout, že pro malá n platí an = 2n - 1. To, že taková posloupnost je skutečně řešením (30), se snadno ověří dosazením a matematickou indukcí... □ vyznat se v nich není vůbec snadné, viz též obr. 20. Obrázek 20 (c) Rekurentní rovnice (31) je sice druhého řádu, je však pořád poměrně jednoduchá. Proto se ničeho nelekáme a rovnici prostě vyřešíme podle návodu, který je odvozen v odst. 15.3: Řešení. Předpokládáme, že řešení je tvaru an = qn, což má tyto důsledky: a„+1 = qan, an+2 = q2an apod. Po dosazení do rovnice (31) dostáváme algebraickou podmínku na hodnotu kvocientu q: q2 = q+í, neboli q2 - q - 1 = 0. (32) 18http://oeis.org/A000045 7 Dělení roviny a další rekurentní vztahy 41 Tato rovnice má dva různé reálné kořeny q=—2— Obecné řešení naší rovnice je tedy tvaru kde Ci, C2 jsou libovolné konstanty. Koeficienty C\,C2 <= K jsou jednoznačně vymezeny počáteční podmínkou a\ = a2 = 1. Po dosazení do (33) a úpravě dostáváme C\ a C2 jako řešení soustavy dvou lineárních rovnic o dvou neznámých: <@j) Tyto hodnoty dosadíme zpět do (33), trošku upravíme a s mimořádným uspokojením podtrhneme výsledek: (i + Vš)" - (i - Vš)" an =-wš-' (34) □ 7.3 Poznámky Všechno je jednoduché, protože to je lineární...! Předpokládejme, že v Hanoji jsou čtyři a více věží:19 Úloha jjjj38 (Reveova). Najděte (i) nějaké, (ii) optimální řešení úlohy 36 ve variantě se čtyřmi a více kolíky. Kvadratickou rovnici (32) lze ekvivalentně přepsat takto: i±l = f (35, Důvodem tohoto přepisu je, že tady rozpoznáváme definici zlatého řezu.20 Z uvedeného tedy mj. vysvítá, jak a proč spolu tyto věci souvisí... Mnoho a mnoho rekurentních vztahů můžeme potkat téměř na každém rohu — např. Fi-bonacciho posloupnost odpovídá neomezenému růstu idealizované nesmrtelné králičí populace apod. Rekurzivní úvahy se přirozeně objevují také u řady kombinatorických úloh; zde je několik ukázek: <@j) Úloha 39 ([L]). Hážeme n-krát nějakou mincí. V závislosti na n vyjádřete pravděpodobnost, že někdy během házení padne panna dvakrát za sebou. Úloha 40 ([L]). Určete, kolika způsoby lze rozmístit n věží na šachovnici n x n tak, aby se věže navzájem neohrožovaly a současně aby platilo některé z následujících omezení: 19http://oeis.org/A007664 20http://en.wikipedia.org/wiki/Golden_ratio 42 I Příklady (i) Aby žádná věž nestála na hlavní úhlopříčce. (ii) Aby rozmístění věží bylo symetrické podle hlavní úhlopříčky. (iii) Aby rozmístění věží bylo symetrické podle středu šachovnice. (iv) Apod. 8 Dláždění roviny a další diofantické rovnice Každý umí vydláždit (eukleidovskou) rovinu kachličkami, které mají tvar rovnostranných trojúhelníků, nebo čtverců, nebo pravidelných šestiúhelníků. Pokud uvažujeme dláždění, kde se střídají různé typy pravidelných mnohoúhelníků, pak objevujeme nové a nové možnosti. Dláždit lze mnoha různými způsoby, my se zda omezíme na dláždění typu „hrana na hranu": Úloha 41. Kolika způsoby je možné vydláždit rovinu pravidelnými mnohoúhelníky tak, aby hrana jednoho mnohoúhelníku lícovala s hranou jiného ? Za chvíli uvidíme, že s jistými slabými omezeními je všech možností jenom konečně mnoho a kupodivu jenom velmi málo... 8.1 Nutná podmínka Protože každý mnohoúhelník má se všemi sousedními mnohoúhelníky společný vrchol, evidentní nutnou podmínkou existence dláždění typu hrana na hranu je, aby součet úhlů okolo každého vrcholu byl roven plnému úhlu. Pokud se v dláždění okolo jednoho vrcholu potká k mnohoúhelníků s počty vrcholů n1; n2,..., nk, potom musí platit ani + an2 +----h ank = 360°, kde ani značí velikost vnitřního úhlu pravidelného n^-úhelníku. Protože pravidelné mnohoúhelníky mají jen velmi omezené velikosti vnitřních úhlů, dostaneme jen velmi omezenou množinu řešení... (jS> Součet vnitřních úhlů v obecném n-úhelníku je roven (n — 2)180°; velikost vnitřního úhlu pravidelného (konvexního) n-úhelníku je tedy an := — 180° = (1 - -) 180°. n \ n) Výše uvedená nutná podmínka má tedy tuto konkrétní podobu: V nlJ V n2/ V nk) cca, je po úpravě totéž, co 1 1 l k-2 — + — + ••• + — = —-. 36 nx n2 nk 2 Nejmenší mnohoúhelník je trojúhelník, v předchozí rovnici je tedy každé rii větší než nebo rovno 3. Kolem jednoho vrcholu jsou alespoň 3 a nejvýše 6 mnohoúhelníků (a to 6 trojúhelníků), v uvedeném vyjádření je tedy k = 3,4, 5, nebo 6. 8 Dláždění roviny a další diofantické rovnice 43 8.2 Lokální řešení Vzhledem k předchozím postřehům začínáme řešení úlohy 41 tím, že najdeme řešení několika specifických nelineárních diofantických rovnic: Úloha 42. Pro k = 3,4,5,6 určete všechna celočíselná řešení rovnice (36), která jsou větší než nebo rovna 3. Než tuhle úlohu úplně vyřešíme, doporučujeme zkontrolovat, že u každého vrcholu v každém dláždění, které známe (nebo někde najdeme), je podmínka (36) skutečně splněna. To by nám mohlo pomoci k nalezení obecné metody řešení každé takové rovnice... <@j) Řešení. Rovnice (36) je symetrická vzhledem k neznámým n\, n2,..., n^, proto stačí, když se omezíme pouze na řešení vyhovující dodatečné podmínce 3 < ni < n2 < • • • < rik (37) (všechna ostatní řešení lze pak obdržet permutacemi)... k = 3 Rovnice (36) má v tomto případě tvar ■i+ + 4 (38) n! n2 n3 2 Jedno z řešení odpovídá třem šestiúhelníkům, tj. ni = n2 = n3 = 6. Pokud by ni > 7, potom také n2, n3 > 7 a součet zr + zr + zr by v takovém případě byl ostře menší než \. Odtud plyne, že ni může nabývat jenom několika málo možností, a to ni = 3, 4, 5, 6. Dosazením každé z těchto možností do (38) dostáváme rovnici stejného typu, ale už jen o dvou neznámých. Tuto novou rovnici lze řešit obdobným způsobem (tj. další redukcí) nebo taky roznásobením a rozkladem (tato metoda má však jistá omezení)... <@j) Postupně tak dostáváme následujících deset řešení: (3,7,42), (3,8,24), (3,9,18), (3,10,15), (3,12,12), (4,5,20), (4,6,12), (4,8,8), (5,5,10), (6,6,6). k = 4 Rovnice (36) má v tomto případě tvar 1 1 1 1 — + — + — + — = 1. n\ n2 n3 n4 Podobně jako v předchozím případě postupně zjistíme omezení na n\, pro každé vyhovující n\ zjistíme omezení na n2 atd. Postupně tak dostaneme následující čtyři řešení: <@j) (3,3,4,12), (3,3,6,6), (3,4,4,6), (4,4,4,4)- 44 I Příklady k = 5 Rovnice (36) má v tomto případě tvar 11111 --1---1---1---1-- n\ n2 n3 n4 n5 Podobně jako výše postupně dostaneme další dvě řešení: {3,3,3,3,6), (3,3,3,4,4)- = 2. k = 6 Rovnice (36) má v tomto případě tvar 111111 --1---1---1---1---1-- ni n2 n3 n4 n5 n6 (jS> Tady čekáme jediné řešení, což se také snadno ověří: (3,3,3,3,3,3). Celkem jsme takto dostali 10 + 4+ 2+1 = 17 řešení, která vyhovovala dodatečné podmínce (37). Všechna řešení lze získat všemožnými permutacemi... □ Každému řešení rovnice (36) odpovídá konkrétní rozmístění určitých mnohoúhelníků kolem jednoho vrcholu. Tady je samozřejmě namístě zamyslet se nad případnými permutacemi, které jsme v řešení úlohy 42 poněkud upozadili, viz obr. 21. Uvědomte si, že ne každá permutace nutně (jS> dává jinou konfiguraci kolem vrcholu a zkuste s v tom všem nějak vyznat... Obrázek 21: (3,4,4,6); (4,3,4,6). 8.3 Globální řešení K určení všech řešení úlohy 41 potřebujeme uvažovat všechny možné lokálně přípustné konfigurace (které jsme úspěšně vyčerpali v předchozím odstavci) a pokusit se je rozšířit do celé roviny. O to se lze pokoušet buď stejnorodým, nebo nestejnorodým způsobem: v prvém případě je kolem každého vrcholu konfigurace stejného typu, ve druhém případě mohou být typy konfigurací u různých vrcholů různé, viz obr. 22. Stejnorodá Všechny možnosti lze vyčerpat systematickým zkoušením a diskuzí u každého nového vrcholu. To je v každém případě poměrně pracné, ale — aspoň v případě stejnorodého dláždění — poměrně (jS> přímočaré: 8 Dláždění roviny a další diofantické rovnice 45 Obrázek 22: (4, 3, 4, 6); (3, 4, 4, 6) a (3, 6, 3, 6) Věta. Existuje právě 11 (neshodných) stejnorodých dláždění roviny pravidelnými mnohoúhelníky typu hrana na hranu. Těchto 11 dláždění se obvykle dělí na 3 regulární a 8 poloregulárních: Regulární dláždění jsou taková, kdy všechny mnohoúhelníky jsou shodné, čili právě ta, která zná každý: (6, 6, 6), (4, 4, 4,4) a (3,3, 3, 3,3,3). Poloregulární jsou povětšinou nová, tudíž zajímavá... Jako nápovědu jsme všechny vyhovující typy v předchozích výčtech vyznačili kurzívou; všechna poloregulární dláždění jsou znázorněna na obr. 23. Obrázek 23 Nestej noro dá Obdobná diskuze pro nestejnorodá dláždění je samozřejmě podstatně subtilnější. Bez nějakého dodatečného upřesnění je takových dláždění nekonečně mnoho, avšak přípustných typů vrcholů není o moc víc než v předchozím případě: 46 I Příklady Úloha jj43 (ad 41). Dokažte, že existuje nekonečně mnoho nestejnorodých dláždění roviny pravidelnými mnohoúhelníky typu hrana na hranu, avšak v každém z těchto dláždění se vyskytují pouze vrcholy výše vyznačeného typy nebo typu (3, 3,4,12). (jS> Povšimněte si, že oněch nekonečně mnoho možností lze vytvořit jenom variací dláždění na obr. 24! Dodatečná upřesnění a odpovídající klasifikace (obvykle konečné!) jsou důkladně prostudovány; použité nástroje většinou přesahují možnosti tohoto kurzu...21 Obrázek 24 8.4 Poznámky Nutná podmínka v odst. 8.1 vedla k řešení několika specifických diofantických rovnic. Z uvedených řešení vidíme následující bezprostřední zobecnění pro libovolný počet neznámých a libovolnou (racionální) pravou stranu: @3> Úloha 44. Dokažte, že libovolná diofantická rovnice typu 11 - + - + ••• = w, (39) x y kde w e Q, má jen konečně mnoho kladných celočíselných řešení. Místo omezení „hrana na hranu" lze uvažovat mírnější omezení, místo pravidelných mnohoúhelníků můžeme dovolit jakékoli — čím více uvolňujeme omezení, tím více se objevuje možností a tím hůře se tyto možnosti klasifikují. Avšak i v těch nej divočejších případech je vždy poměrně snadné třídit dláždění podle jejich symetrií. Např. všechna stejnorodá dláždění typu hrana na hranu mají tu vlastnost, že vzniklý vzor se pravidelně opakuje ve dvou nezávislých směrech; dlážděním s touto vlastností se říká periodická. (U nestejnorodých dláždění právě omezení tohoto typu mohou být oněmi dodatečnými omezeními, o kterých jsme mluvili u úlohy 43.) Něco o symetriích si řekneme v následující podkapitole. Všimněte si, že výše uvedené teoretické výsledky lze často najít jen tak na podlaze, viz obr. 25. 9 Periodické vzory a diskrétní grupy transformací U různých dláždění můžeme pozorovat různé symetrie; často však na pohled rozdílná dláždění mají naprosto stejné symetrie, viz např. dláždění znázorněná na obr. 26 a obr. 25 (resp. obr. 22 (jS> vlevo). Pokud bychom se omezili pouze na periodická dláždění (bez ohledu na to, zda jsou tvořená pravidelnými nebo obecnými mnohoúhelníky, zda jsou „hrana na hranu" či nikoli), pak zjistíme, @3> že z hlediska symetrií jich z nějakého záhadného důvodu nebude víc než 17 typů, viz úlohu 46... 21http://mathworld.wolfram.com/DemiregularTessellation.html 9 Periodické vzory a diskrétni grupy transformací 47 Obrázek 26 Protože z hlediska symetrií je jedno, jestli studujeme dláždění nebo tapety, budeme v dalším mluvit obecně o periodických vzorech. Všechny symetrie nějakého vzoru (s operací skládání) tvoří grupu, tzv. grupu symetrií onoho vzoru. Základní otázka zní: • Jak klasifikovat periodické vzory podle jejich symetrií? 9.1 Frízové vzory V tomto odstavci se budeme zabývat jednodušší verzí uvedeného problému, a to periodickými vzory, které se opakují pouze v jednom směru. Takovým vzorům se přezdívá frízové vzory a odpovídající grupy symetrií se proto nazývají frízové grupy. V následujících odstavcích naznačíme řešení této základní úlohy: Úloha 45 (frízová). Určete, kolik existuje typů frízových vzorů, které mají navzájem různé symetrie. Jinými slovy, máme určit, kolik existuje — až na izomorfismus — frízových grup. Je přirozené začít zkoumat různé frízové vzory a zkoušet se v problému trochu zorientovat. Takto např. zjistíme, že 7 vzorů na obr. 27 má 7 různých (přesněji neizomorfních) grup symetrií. Ptáme se, zda <@J) existují další frízové grupy, které nejsou izomorfní žádné z těchto sedmi... Možné symetrie Základní symetrie, kterou mají všechny frízové vzory, je • posunutí (nejkratší možné ozn. ŕ). 48 I Příklady A XXX A A A/ ^ Si ^ ^ ^ "X ^ ^ ^> ^ ^ „; ti/Au. anď .■'■-jiljin..'i*" Obrázek 27 Dále takový vzor může mít některou z následujících symetrií: • osová souměrnost podle vodorovné osy (ozn. ox), • osová souměrnost podle svislé osy (ozn. oy), • středová souměrnost (ozn. sc), • posunutá souměrnost ve směru vodorovné osy (ozn. gT). Jednotlivé grupy můžeme začít rozlišovat podle jejich generátorů. V každém z těchto případů potřebujeme rozlišit, co všechno ony grupy obsahují, neboli co všechno může vzniknout skládáním generujících prvků. Potom snadno rozpoznáme, které jsou navzájem izomorfní a které nikoli... Skládání symetrií Kvůli stručnějšímu vyjadřování označíme myšlenou frízovou grupu G. Každá taková grupa má podgrupu (ŕ) = {tk | k e Z}, kde stejně jako výše t značí nejkratší možné posunutí. Začneme sérií jednoduchých tvrzení, která budeme potřebovat a která je nejprve potřeba zdůvodnit. Všude v následujícím je k e Z a t občas značí vektor posunutí (tedy nikoli posunutí (jS> jako transformaci): • Oy e G • sc e G - • sv e G • ox e G ^=> • ox ,oV' e G Oy, e G, kde y' = tk(y), sc' G G, kde c' = c + kt, t = kt nebo t = -|í, 9t e G, =^> sc e G, kde c = x n y', 10 Periodické vzory a diskrétni grupy transformací 49 • ox, sc e G =^> Oy> e G, kde y1 3 c, • oy,sc e G, potom ox e G ^=4> c e y. • Oy, sc e G a c ^ y =^> <7| e G. Nyní vidíme, že kromě í (který je všude), stačí uvažovat jenom následujících několik generátorů: Ox, Oy, sc, g±. V tuto chvíli tedy vidíme nejvýše 24 = 16 možností... Závěr Nyní víme, s čím a jak počítat; začneme tedy uvažovat rozličné generátory, určíme důsledky, porovnáme s dosud získanými grupami, každou novou grupu zvýrazníme a doplníme nějaké ilustrace: <@J) • G = (t) LLL, QQQ • G = (t, ox) = (t,ox,gt) CCC, EEE • G = (t, oy) AAA, VVV • G = (t, sc) NNN, SSS . G = (í^) LľL • G = (t, ox,Oy) = (t,ox,oy,sc,gt) HHH, OOO o G = (t,ox,sc) = (t,ox,sc,oyr,gt) o G = (t,ox,gt) = (±,ox,gt) „ ^ , í(t,Oy,sc,ox,gt), pokud c e y • G = (t, Oy, s c) = < ,, . , , , VAV {(t,Oy,sc,gt), pokud c (f, y o G = (t,oy,gt) = (t,oy,gt,sc) o G = (t,sc,gt) = (t,sc,gt,oy) o Atd... Dostáváme celkem 7 možností, které nutně musí korespondovat s těmi na obr. 27 — proveďte toto přiřazení. <@j) Tímto jsme zdůvodnili, že na obr. 27 jsou skutečně zastoupeny všechny možné frízové grupy a jakákoli jiná frízová grupa je nutně izomorfní některé z oněch sedmi: Věta. Existuje právě 7 typů frízových vzorů, které mají navzájem různé symetrie. 50 I Příklady 9.2 Poznámky Úloha jj46 (tapetová). Dokažte, že existuje právě 17 typů tapetových vzorů, které mají navzájem různé symetrie. 10 Trisekce úhlu a kořeny polynomů Problém trisekce úhlu patří mezi slavné problémy starověku, které odkazují na možnosti eukleidovských konstrukcí, tzn. geometrických konstrukcí prováděných eukleidovským pravítkem a kružítkem. Charakterizace eukleidovsky sestrojitelných veličin v odst. 17.1 dává tušit, že řešení tohoto geometrického problému musí být v podstatě algebraické... Úloha 47 (třetinová). Pro daný úhel rozhodněte, zda je možné jej rozdělit na třetiny pomocí eukleidovského pravítka a kružítka. Některé úhly zaručeně roztřetit lze (např. pravý úhel), s jinými si poradit neumíme. Jde o to, jestli se v problému lze vyznat nějak koncepčně... 10.1 Algebra Reformulace Abychom získali kontrolu nad tímto problémem, diskutujeme sestrojitelnost nějaké délkové veličiny přidružené k danému úhlu a, např. cos a, tg a apod. Vztah mezi cos a a cos 3a lze snadno (jS> vyvodit ze součtových vzorců: cos 3a = 4 cos3 a — 3 cos a. Pokud označíme a := cos 3a (dáno) a x := cos a (hledáno), potom předchozí rovnost je ekvivalentní 4x3 - 3x - a = 0. (40) (jS> Pro srovnání, vztah mezi tg a a tg 3a je tento: 3 tg a-tg3 a 1 — 3 tg a Pokud označíme b := tg 3a (dáno) a x := tg a (hledáno), potom předchozí rovnost je ekvivalentní x3 - 3bx2 - 3x + b = 0. (41) Tímto je problém redukován na následující: Úloha 48 (ad 47). Pro dané číslo a (resp. b) rozhodněte, zda polynom (40) (resp. (41)) má sestrojitelný kořen x. Obecná odpověď na tento dotaz není zatím zřejmá, uvedená reformulace nám však umožní aspoň něco... 10 Trisekce úhlu a kořeny polynomů 51 Obecné poznatky Tady na chvíli přejímáme značení z odst. 17.1: Qk+i značí algebraické rozšíření Qfe+i :=®k[y/ďk], kde dk e Qfe a Qk značí nějaké algebraické rozšíření tělesa Qfc-i atd., přičemž Q0 = Q. Následující poznatky a jejich zdůvodnění jsou velmi analogické tomu, co umíme říct o kořenech (jS> polynomů s reálnými koeficienty nad C = R[v~ 1]- • • Věta. Pro polynomy lichého stupně s koeficienty z Qk platí: (1) Má-li polynom nějaký kořen z Qfe+i> pak má i kořen z Qk- (2) Odtud, speciálně, má-li polynom racionální koeficienty a kořen z Qfc+i> pak má i kořen zQ. (3) Odtud obráceně, nemá-li polynom s racionálními koeficienty racionální kořen, nemá ani kořen z žádného rozšíření Qi! Užitek Nyní stačí vzpomenout, jak se hledají racionální kořeny pro polynomy s racionálními koeficienty, a otestovat sílu předchozích úvah např. na následující úloze: Úloha 49 (ad 48). Dokažte, že (i) úhel 6(P, (ii) žádný ostrý vnitřní úhel v pravoúhlém trojúhelníku s odvěsnami 1 a 2 nelze eukleidovsky rozdělit na třetiny. ...... □ Nyní máme několik konkrétních eukleidovsky sestrojitelných úhlů, u kterých umíme zdůvodnit, že nejsou eukleidovsky roztřetitelné. Z výše uvedeného však vyplývá obecná charakterizace: Věta. Úhel (3 lze eukleidovsky rozdělit na třetiny právě tehdy, když polynom (40) je reduci-bilní nad Q[a], kde a = cos(3. 10.2 Poznámky Konstrukce s označeným pravítkem S problémem trisekce úhlu souvisí následující úloha: Úloha 50 ([MO]). Libor narýsoval kružnici se středem S a body A, B, C, D, viz obr. 28. Zjistil, že úsečky SC a B D jsou stejně dlouhé. V jakém poměru jsou velikosti úhlů ASC a ABC? Na této znalosti je založena trisekce úhlu pomocí „označeného pravítka", jak ji znal již Archimedes. .. 52 I Příklady Obrázek 28 Pravidelné mnohoúhelníky Konstrukce pravidelného n-úhelníku evidentně souvisí s problémem trisekce úhlu, akorát je podstatně redukována množina úhlů do diskuze. V [E] najdeme konstrukce pro n = 3, 4, 5 a 15. Pro každý sestrojitelný pravidelný fc-úhelník, není problém sestrojit taky pravidelný 2/j-úhelník. Tzn. úloha je řešitelná také pro n = 6, 8,10,12,16, 20 a další. Úloha jj51 (Gaussova-Wantzelova). Dokažte, že pravidelný n-úhelník lze sestrojit eukleidovským pravítkem a kružítkem právě tehdy, když n je součinem libovolné mocniny 2 a navzájem různých Fermatových prvočísel. Fermatovo prvočíslo je prvočíslo tvaru Fk = 22k + 1. K dnešnímu dni22 je známo pouze pět Fermatových prvočísel: F0 = 3, Fi = 5, F2 = 17, F3 = 257, F4 = 65 537. Úloha sestrojitelnosti pravidelného n-úhelníku tedy není řešitelná pro n = 7, 9,11,13,14,18,19, 21,... 21. září 2016 KAPITOLA Zázemí a další příklady 11 Matematická indukce Matematickou indukci potřebujeme ke korektnímu zobecňování pořád, viz ... 11.1 Prostá matematická indukce Princip matematické indukce v její nejjednodušší a nejčastěji používané podobě se srozumitelně vysvětluje pomocí dominového efektu, viz obr. 29. Podstatné při této interpretaci je, že uvažujeme výhradně dílky postavené v jedné řadě! V takovém případě můžeme rozšířit princip dominového efektu pro nekonečný počet dílků... Obrázek 29 Za touto popularizací samozřejmě vidíme přirozená čísla, jakožto prototyp nekonečné dobře uspořádané množiny. Ve všech následujících formulacích značí V(n) nějakou (libovolnou) výrokovou formuli, která závisí na n e N. 54 II Zázemí a další příklady Princip (matematické indukce). Předpokládejme, že • platí V (1), • pro libovolné k e N platí (V (k) => V (k + í)). Potom platí V (n) pro všechna n e N. Vzpomeňte si, že v Peanově axiomatickém popisu přirozených čísel je princip matematické indukce jedním z axiómů. Často užíváme matematickou indukci v různě pozměněných podobách. Typickou variantou je omezení typu n > n0, kde n0 je nějaké přirozené číslo různé od 1, viz např. úlohu 12. (Takové modifikace můžeme uvažovat i u všech následujících formulací, což už znova připomínat nebudeme.) 11.2 Silná matematická indukce U některých úloh s výše zformulovaným principem nevystačíme a potřebujeme matematickou indukci v poněkud silnější podobě, viz např. úlohu 37. Pokud tedy řešíme předchozí úlohu matematickou indukcí, musíme použít o něco silnější princip: Princip (silnější matematické indukce). Předpokládejme, že • platí V (í) a V (2), • pro libovolné k e N platí (V (k) A V (k + í) => V (k + 2)). Potom platí V(n) pro všechna n e N. Tento princip můžeme nadále podle potřeby zesilovat až k následujícímu: Princip (silné matematické indukce). Předpokládejme, že platí • (V(k) pro všechna k e N) =^> V (k + í). Potom platí V (n) pro všechna n e N. Typické a velmi dobře známé tvrzení, které se dokazuje pomocí tohoto principu, je v následující úloze: Úloha 52. Dokažte, že každé celé číslo větší než 1 je součinem prvočísel. 11.3 Poznámky a modifikace Zobecnění principu matematické indukce pro libovolnou dobře uspořádanou množinu vypadá takto: 12 Dělitelnost 55 Princip (transfmitní indukce). Předpokládejme, že M je dobře uspořádaná množina, k,l e M a platí • (V(k) pro všechna k < l) =^> V(l). Potom platí V(n) pro všechna n e M. Úloha 53. Najděte ve svých poznámkách z teorie množin nějaké tvrzení, které se dokazuje pomocí transfinitní indukce. Související metodou je tzv. princip nekonečného sestupu, lépe řečeno princip nemožnosti nekonečného sestupu. Zde opět uvažujeme množinu přirozených čísel, ačkoli lze princip formulovat obecněji. Princip (nekonečného sestupu). Předpokládejme, že k, l e N a platí • V(l) =^> (existuje k < l takové, že V(k)). Potom V(n) nemůže platit pro žádné n e N. Jedná se o důkazovou metodu sporem, jež odkazuje právě na fakt, že existuje jenom konečně mnoho přirozených čísel, která jsou menší než dané číslo. Typické užití tohoto principu najdete v řešení proslulé úlohy 15 na str. 19... 12 Dělitelnost 12.1 Věta o dělení se zbytkem Zde zformulujeme větu o dělení se zbytkem a připomeneme, že platí nejen v okruhu celých čísel, ale taky např. v okruhu polynomů...... 12.2 Eukleidův algoritmus a důsledky Eukleidův algoritmus pro nalezení největšího společného dělitele (NSD) celých čísel lze najít na začátku VII. knihy Základů [E]... Bezprostředním důsledkem je následující tvrzení: Věta (Bezoutova). Je-li NSD (a, b) = d, pak existují celá čísla k a l taková, že platí ak + bl = d. Čísla k a l obdržíme zpětným dosazováním jednotlivých kroků Eukleidova algoritmu, tzn. lze je vyjádřit i pro poměrně velké a a b docela efektivním způsobem... 12.3 Kongruence Tady připomeneme ekvivalentní úpravy kongruencí. V porovnání s ekvivalentními úpravami rovností je tu jeden chyták... 56 II Zázemí a další příklady 12.4 Eulerova funkce a Eulerova věta Eulerova funkce je zobrazení p : N —>• N, které lze definovat různě: je-li b = p"1 -p%2 ■ ■ ■ ■ prvočíselný rozklad čísla b, potom hodnota p(b) je -'•0-s)-0-s)-- = počet čísel od 1 do b, která jsou nesoudělná s b; je-li 6=1, definuje se p(b) = 1. Pokud bereme první rovnost v (42) jako definující, potom zdůvodnění druhé rovnosti je velmi prosté. Zdůvodnění třetí rovnosti není sice těžké, ale není ani g3> triviální, viz [HKŠ]... Věta (Eulerova). Jsou-li seZ a b e N nesoudělná čísla, potom platí avW = 1 mod b. (43) Eulerova věta je zobecněním tzv. malé Fermatovy věty, kterou lze za předpokladu, že p je prvočíslo a a je libovolné s ním nesoudělné číslo, formulovat takto: aP^1 = 1 mod p. (44) Pro nás asi nej srozumitelnější zdůvodnění Eulerovy věty lze najít v rámci teorie konečných grup, (jS> s odkazem na větu Lagrangeovu...1 13 Kořeny polynomů aneb algebraické rovnice Tady připomeneme něco o kořenech polynomů, a to včetně základní věty algebry... V podkap. 10 (konkrétně v řešení úlohy 49 na str. 51) jsme vzpomínali na následující nutnou podmínku pro racionální kořeny polynomů s celočíselnými koeficienty: Věta. Uvažme polynom P{x) = anxn + • • • + a\x + ciq s celočíselnými koeficienty, kde an a a0 jsou nenulové. Pokud x = | je racionálním kořenem polynomu P a toto vyjádření je v nesoudělném tvaru (tj. NSD(p, q) = 1), potom p dělí ciq a q dělí an. Protože každé celé číslo má jen konečný počet dělitelů, dostáváme pro libovolný celočíselný polynom jenom konečný počet racionálních kandidátů na kořeny. Ty pak stačí postupně otestovat, zda jimi skutečně jsou... http://en.wikipedia.org/wiki/Euler's.theorem 14 Diferenciální a integrální počty 57 14 Diferenciální a integrální počty Vstupenkou do světa vyšší matematiky je pojem limity. Limitní úvahy jsou patrné jak za pojmem derivace, tak integrálu. Tady shrnujeme pouze nej základnější základy. Několik dalších postřehů/vlastností lze najít v paralelní podkap. 15... 14.1 Limita, spojitost, derivace Všechny níže uvedené pojmy mají své levé/pravé varianty, příp. rozšíření z bodu na nějaké podmnožiny definičního oboru... Limita Všechny možné limity, které jsme kdy potkali, lze shrnout do následující neformální (ale pořád celkem přesné) definice: Zobrazení / : X —>• Y má v bodě x0 e X limitu L eľ, pokud se body, které jsou dostatečně „blízko" k x0, avšak jsou různé od x0, zobrazují na body, které jsou libovolně „blízko" k L. V takovém případě píšeme f(x) —>• L pro x —>• x0 nebo lim f(x) = L. X—>Xq Důraz klademe na slovo libovolně, aby bylo zřejmé, že nestačí, když se hodnoty f(x) „blíží" k L, ale že tato „blízkost" musí umět být libovolně malá! Z formulace je patrné, že limitu lze uvažovat pouze pro zobrazení mezi takovými množinami, kde jsme schopni dát nějaký význam výrazům v uvozovkách. Obecně lze „blízkost" charakterizovat pomocí okolí bodů: Zobrazení / : X —>• Y má v bodě x0 e X limitu L eľ, pokud pro každé okolí Ol q Y bodu L existuje okolí Oxo C X bodu x0 tak, že platí f(OX0\{x0})COL. Pro prostory typu M.n se zpravidla uvažují hodně symetrická okolí, jejichž „velikost" se měří pomocí nějaké (ne nutně eukleidovské) metriky a vyjadřuje se pomocí písmenek S (pro dostatečně) a e (pro libovolně)... <@j) Pro posloupnosti je X = N, a protože N je diskrétní množina, jediné limity, které má smysl uvažovat, jsou limity „pro x dostatečně blízko oo", neboli pro „dostatečně velká x"... Spojitost Zobrazení / : X —>• Y je v bodě x0 e X spojité, pokud je v tomto bodě definováno, má v tomto bodě limitu a tato limita je rovna funkční hodnotě, tj. lim f(x) = f(x0). X—>Xq 58 II Zázemí a další příklady Pomocí okolí, můžeme totéž formulovat následovně: Zobrazení / : X —>• Y je v bodě x0 e X spojité, pokud pro každé okolí Oi C ľ bodu L existuje okolí Oxo C X bodu x0 tak, že platí f(OX0) C Ol. (jS> Nutnou podmínkou spojitosti je existence limity; tato podmínka však není dostatečná... Derivace Pojem derivace jsme se učili pro reálné funkce jedné, resp. více reálných proměnných (tzn. vzhledem k předchozímu značení uvažujeme Y = R a X = R, resp. X = Rn). Derivace funkce / : R —>• R měří okamžitou rychlost, s jakou se mění hodnoty funkce / v závislosti na proměnné x. Pro funkce více proměnných / : Rn —>• R můžeme uvažovat, jak se funkce mění vzhledem k jednotlivým proměnným (parciální derivace) nebo obecněji, jak se mění v obecném směru (směrové derivace)... Okamžitá rychlost změny je limitou průměrných rychlostí, což přesně obsahem v následující formulace: Derivace funkce / bodě x0 e R je následující limita (pokud existuje) tu \ v f(x0 + h) - f(x0) f (xa) := lim -;-. (jS> Nutnou podmínkou existence derivace je spojitost; tato podmínka však není dostatečná... Diskrétní analogií derivace (funkce) je diference (posloupnosti), viz odst. 15.1... 14.2 Riemannův a Newtonův integrál Názorné cvičení k pojmu určitého integrálu je v odst. 6.2... Riemannův integrál Obecný Riemannův integrální součet funkce / na intervalu (a, b) závisí na dělení D tohoto intervalu na podintervaly (xí,xí+1), kde a = xq < x\ < • • • < xn = b, a výběru V reprezentujících bodů q G (xj, xi+1), a to následujícím způsobem: n S(D,V):=YJf(^)-^xl, (45) i=0 kde Axí := Xj+i — Xj. Délka nejdelšího podintervalu dělení D se nazývá normou tohoto dělení. Pokud platí, že s libovolným zjemňujícím se dělením a libovolným jemu příslušným výběrem reprezentujících bodů 14 Diferenciální a integrální počty 59 xi - 3 X2 4- 1 Hstimntfd Arén = 0.465197 Actual Area = 0.6 Obrázek 30: Riemannův integrální součet funkce f(x) = x2 — 3x2 + 1 na intervalu (—1, 2) odpovídající ekvidistantnímu dělení na 7 podintervalů a výběru reprezentujících bodů v polovinách těchto podintervalů. Riemannovy součty konvergují, a to pokaždé ke stejnému číslu, potom říkáme, že funkce je na daném intervalu riemannovsky integrovatelná. Přesněji řečeno: Funkce / je riemannovsky integrovatelná na intervalu (a, b), jestliže existuje reálné číslo I takové, že pro dostatečně jemná dělení D tohoto intervalu — s naprosto libovolnými výběry V — jsou odpovídající Riemannovy součty S(D, V) libovolně blízko /, neboli lim S(D,V) = I. norma(-D)—>0 b V takovém případě píšeme I = J/(i)di a toto číslo nazýváme Riemannovým určitým a integrálem... Nutnou podmínkou integrovatelnosti je omezenost; tato podmínka však není dostatečná... Dostatečnými podmínkami integrovatelnosti je např. spojitost nebo monotónnost; tyto podmínky však nejsou nutné... <@J) Metoda Pokud víme, že funkce / je na intervalu (a, b) integrovatelná, je možné odpovídající integrál určit následujícím způsobem: (1) zvolíme jednu libovolnou posloupnost dělení (D\, D2,...), jejíž norma konverguje k 0, (2) pro každé n vybereme úplně libovolně reprezentující body Vn příslušné dělení Dn, (3) vyjádříme posloupnost odpovídajících Riemannových součtů S(Dn, Vn) podle (45), (4) spočítáme limitu a podtrhneme výsledek: b ( f(x)dx= lim S(Dn,Vn). (46) 60 II Zázemí a další příklady Toto je přesně postup, který jsme aplikovali v řešení (d) úlohy 34. Kritickým místem této metody je samozřejmě krok (3), kdy potřebujeme vyjádřit součet S(Dn,Vn) v uzavřeném tvaru v závislosti na n... Ekvivalentní definice K pojmu riemannovské integrovatelnosti se lze ekvivalentně dobrat následujícím způsobem: Omezená funkce má na každém intervalu supremum a infimum. Pro dělení D intervalu (a, b) označíme na každém podintervalu infimum, resp. supremum funkce / jako m := inf{/(x)}, resp. M, := sup{/(x)}, X X kde x G (xí, xi+i). Dolním, resp. horním integrálním součtem funkce / vzhledem k dělení D pak nazýváme číslo n n S(D, inf) := ■ Ax,, resp. S(D, sup) := M, ■ Ax,. i=i i=i Vztah mezi všemi typy součtů, o kterých jsme dosud mluvili, je S(D, inf) < S(D, V) < S(D, sup), kde D je libovolné dělení a V" je libovolný jemu příslušný výběr reprezentujících bodů. i4 - 3 x7 + 1 x4 - 312 i-1 Estimated Area = -1.3518 Estimated Ar;a= 3.10603 Actual Area = 0.5 Actual Area = 0.5 Obrázek 31: Dolní a horní integrální součet funkce f(x) = x2 — 3x2 + 1 na intervalu (—1,2) odpovídající ekvidistantnímu dělení na 7 podintervalu. Množina všech dolních, resp. horních součtů je vzhledem ke všem možným dělením intervalu (a, b) omezená. To mimo jiné znamená, že každá z těchto množin má supremum a infimum. Dvě z těchto čísel se tradičně značí b b / f (x) dx := sup{S(D, inf)}, resp. / f (x) dx := mí{S(D, sup)} J D J D a a a nazývají se dolní, resp. horní integrál funkce / na intervalu (a, b). Slibovaná charakterizace integrovatelnosti je tato: 15 Diferenciální a integrální počty 61 Věta (Darbouxova). Funkce f, která je omezená na intervalu (a, b), je riemannovsky inte-grovatelná právě tehdy, když odpovídající dolní a horní integrál jsou stejná čísla. V takovém b b b případě platí J f (x) dx = J f (x) dx = J f (x) dx. Newtonova—Leibnizova věta Základní, krásná, extrémně užitečná a na první pohled rozhodně překvapující Newtonova a Leibnizova věta odhaluje souvislosti mezi integrováním a derivováním... Věta (Základní věta integrálního počtu). X (1) Pokud funkce f je spojitá na intervalu (a,b), potom funkce F(x) := J f(t)dt je její a primitivní funkcí, tj. F(x) má derivaci v každém bodě tohoto intervalu a platí F'(x) = -±(jf(t)d^J =f(x). (47) (2) Pokud funkce f je riemannovsky integrovatelná na intervalu (a, b) a F je (libovolná) primitivní funkce k funkci f na tomto intervalu, potom platí b f(x)dx = F(b) - F(a). (48) Poznámky k důkazu. Intuitivní zdůvodnění první části věty je na obr. 32. Pro spojité funkce je druhá část věty bezprostředním důsledkem části první; v této obecnější podobě se dokazuje s odkazem na Lagrangeovu větu o střední hodnotě... □ <@j) Z první části věty se mimo jiné dozvídáme, že každá spojitá funkce je derivací nějaké jiné funkce, neboli, že ke každé spojité funkci existuje funkce primitivní. Pokud bychom uvažovali pouze integrovatelnost (a nikoli spojitost) /, potom by funkce F byla spojitá (ale ne nutně diferencovatelná)... Metoda Pokud víme, že funkce / je na intervalu (a, b) integrovatelná, je možné odpovídající integrál určit následujícím způsobem: (1) najdeme funkci F, která je primitivní k funkci / na (a, b), (2) dosadíme meze jako v (48) a podtrhneme výsledek. Toto je přesně postup, který jsme aplikovali v řešení (e) úlohy 34. Kritickým místem této metody je samozřejmě krok (1), kdy potřebujeme vyjádřit primitivní funkci k /, a to v uzavřeném tvaru... 62 II Zázemí a další příklady Obrázek 32: Rychlost, s jakou koberec pokrývá podlahu, odpovídá jeho šířce v příslušném bodě: ^ = f(x). 15 Diferenční a sumační počty V této části se vracíme ke dvěma otázkám, kterým jsme se částečně věnovali už dříve: • Jak vyjádřit n-tý součet posloupnosti, pokud možno v uzavřeném tvaru? • Jak vyjádřit n-tý člen posloupnosti, která je zadána rekurentním vztahem? Nějakou představu o obou těchto problémech máme z podkap. 4 a 7. V podkap. 5 jsme si mohli všimnout jisté symbiózy mezi konečnými, resp. nekonečnými součty a určitými, resp. nevlastními integrály. Tyto vztahy chápeme jako diskrétní a spojitou stranu jedné mince. V matematické analýze jsme převážně studovali tu druhou stranu mince, té první se budeme trochu důkladněji věnovat nyní. Začneme tím, že doplníme diskrétní protějšky k těm nejzákladnějším pojmům. Tady je stručný přehled: posloupnost a : N —>• R diference Aa„ = an+i — an primitivní posloupnost AAn = an neurčitý součet Y an = An + C 3 konečný součet Y an = Aj+± — Ai řada ^a„= lim Y an n=i 3^°° n=i f{x+h)-f{x) h funkce / : R ->• K derivace f (x) = lim primitivní funkce F'(x) = f(x) neurčitý integrál / f(x) dx = F(x) + C b určitý integrál J f (x) dx = F (b) — F (a) a oo b nevlastní integrál J f (x) dx = lim J f (x) dx Stručný úvod do problematiky a nějaké další odkazy lze najít v [G]. Odstavce odpovídající diferenciálním počtům, integrálním počtům, resp. diferenciálním rovnicím (jak je známe z kurzů mat. analýzy I, II, resp. III) jsou diferenční počty, sumační počty, resp. diferenční rovnice. 15.1 Diferenční počty Diskrétní verzí derivace funkce je diference posloupnosti. 15 Diferenční a sumační počty 63 Diference Diference posloupnosti (an) je posloupnost (Aan) definovaná vztahem Aan = an+1 — an. Ne každá funkce má derivaci, zato každá posloupnost má diferenci. Definici a obecné vlastnosti operátoru A shrnujeme v následující tabulce:2 Aan — an+i — an A2an = A(Aa„) = Aan+1 - Aan A(an + bn) = Aan + Abn A(c-an) = c-Aan A(an ■ bn) = an ■ Abn + Aan ■ bn+1 ffx) = lim /(*+")-/(*) f" (x) = (f (x))' = lim h— f'(x + h)-f'(x) h (f + g)' = f' + g' (c-f)' = c-f (f-g)' = f-g' + f'-g Máme namířeno ke konkrétnímu užití diferenčního počtu, takže budeme potřebovat diference některých užitečných posloupností. Úloha 54. Určete diferenci (i) aritmetické, (ii) geometrické a (iii) Fibonacciho posloupnosti. (i) Pro aritmetickou posloupnost s diferencí d zřejmě platí Aan = d. (ii) Pro geometrickou posloupnost s kvocientem q je Aan = an ■ q — an = (q — 1) -an. (iii) Pro Fibonacciho posloupnost platí Aan = (an + a„_i) — an = an-\. □ Geometrická posloupnost je exponenciální vzhledem k n a její diference je typově stejná. Aritmetická posloupnost je lineární vzhledem k n a její diferencí je konstantní posloupnost. Diferencí konstantní posloupnosti je samozřejmě nulová posloupnost. Obecněji, pro posloupnosti tvaru an = nr platí Anr = (n+ iy -nr = rrf-1 + ^-^nr~2 1. Vidíme, že diferencí se snižuje stupeň exponentu o jedničku, ale výsledný výraz vypadá jaksi komplikovaně. Při následujícím užitečném značení n- := n(n — 1) • • • (n — r + 1) = (n — r)! (49) se snadno zdůvodní, že platí An- = r-rv r-l Zde jsme uvažovali r e N, ale definici n- lze přirozeně rozšířit tak, že předchozí rovnost platí pro libovolné r e R.3 2V každém dílčím přehledu budeme pro porovnání doplňovat odpovídající vztahy ze spojitého světa. 3Pro r = 0 se vezme n- := 1; pro r = —1, —2,... se definuje n- := ^.(K_r) i Pr0 neceločíselné hodnoty r se použije gamma funkce n- r(re+l) r(n-H-l) ■ 64 II Zázemí a další příklady Závěr Dva důsledky předchozího rozvažování, na které se hodláme odkazovat, jsou tyto (rovnosti platí pro libovolné ij,reRaneN): Aqn = {q-l)-qn (qx)' = \nq-qx (50) An- = r ■ n——- (xr)' =r-xr~1 Úloha 55. V předchozím přehledu dokažte všechny rovnosti, které nejsou na první pohled zřejmé. 15.2 Sumační počty Diskrétní verzí určitého integrálu je konečný součet. O tom obecně není moc povídat, takže začneme oklikou, abychom se ke konečným součtům vrátili v tzv. základní větě sumačního počtu... Primitivní posloupnost a neurčitý součet Posloupnost {An) taková, že platí AAn = an F'{x) = f(x) se jmenuje primitivní posloupnost, příp. antidiference (a„). Každá posloupnost (a„) má mnoho různých primitivních posloupností, všechny se však od sebe liší jenom o nějakou konstantu CeR. Obecné primitivní posloupnosti k (a„) se říká neurčitý součet a značí se El fxn An C f f(x)dx = F(x) + C Důvod tohoto pojmenování a značení by měl být zřejmý z následujícího pododstavce... Nyní uvádíme dva zřejmé důsledky (50), na které se budeme několikrát odkazovat (rovnosti (jS> platí pro libovolné q, r e R a n e N): Jxráx=£±L+C (51) fq*dx=£-q+C Konečný aneb určitý součet Pro libovolnou posloupnost (a„) uvažme posloupnost {An) definovanou jako An ■= ai H----- n-1 (52) fe=l 15 Diferenční a sumační počty 65 Potom pro libovolné n e N zrejme platí AAn = an, neboli (An) je primitivní posloupností k posloupnosti (a„). Při tomto značení navíc pozorujeme, že i ak = cii H-----h a.,- = (ai H-----h a,) - (ai H-----h <2j_i) = A,-+i - Aj. (53) k—i Tím jsme zdůvodnili následující analogii věty 14.2: Věta (Základní věta sumačního počtu). n-l (1) Pro libovolnou posloupnost (an) je posloupnost (An := Y afe) její primitivní posloup- k=l /n-l AAn = A E ak \k=l ností, tj. F'(*) = -h(ff(t)dt)=f(x) (2) Pokud (An) je (libovolná) primitivní posloupnost k posloupnosti (an), potom platí Y ak = AJ+1 -A, f f(x) dx = F(b) - F{a) k=i a Všimněte si, že — na rozdíl od věty 14.2 — tato věta neobsahuje žádné omezující předpoklady. Navíc zdůvodnění této věty je o poznání primitivnější: stačilo nám k tomu právě pět řádků! Metoda 3 Každá posloupnost (an) má pro libovolné iaj určitý součet ak- Tento součet je možné přímo k—i (tj. bez matematické indukce) určit následujícím způsobem: (1) najdeme posloupnost (An), která je vzhledem k (an) primitivní, (2) dosadíme meze jako v (53) a podtrhneme výsledek. Toto je přesně postup, který jsme poprvé aplikovali ve zdůvodnění (d) věty 4.2. Kritickým místem této metody je samozřejmě krok (1), kdy potřebujeme vyjádřit primitivní posloupnost k dané posloupnosti, a to v uzavřeném tvaru... Úloha 56. Určete n-tý součet (i) aritmetické, (ii) geometrické a (iii) Fibonacciho posloupnosti. Řešení. Ve všech třech případech umíme vyjádřit an pomocí n a tato závislost je buď mocninná nebo exponenciální. Podle (51) tedy umíme najít primitivní posloupnost An a podle věty 15.2 pak můžeme určit kterýkoli součet se nám zlíbí. Např. vyjádření n-tého částečného součtu geometrické posloupnosti an = aiq™^1 vypadá podle tohoto návodu následovně: /ak = ai-- + C, '-^ q — 1 " qn q° g"-l _ > ak = <2i-- - <2i-- = <2i-—. U q-1 q-1 q-1 66 II Zázemí a další příklady Posloupnosti v předchozí úloze umíme celkem pohodlně sečíst i bez diferenčního počtu, takže nám tento postup nemusí přijít úplně atraktivní. Právě nabyté dovednosti bychom však měli docenit v případech jako např. (19) na str. 23, které se bez nápovědy řeší dost těžko... 15.3 Rekurentní vztahy aneb diferenční rovnice Řešení úlohy 35 můžeme interpretovat jako řešení jednoduché diferenční rovnice prvního řádu (Aan = n+1) s počáteční podmínkou (cti = 2). Obecné diferenční rovnice prvního, druhého, ... řádu jsou rovnice tvaru f'(x) = (n, an, an+1), To jsou známé rekurentní vztahy, se kterými jsme se potkali již mnohokrát. Úloha 57. Najděte v tomto textu další rekurentní vztahy, resp. diferenční rovnice. Řešení. V úloze 36 o hanojských věžích jsme měli posloupnost (an) popsánu rekurentním vztahem, resp. diferenční rovnicí an+i = 2an + 1, resp. Aan = an + 1 s počáteční podmínkou a\ = 1. Podobně, aritmetická, geometrická a Fibonacciho posloupnost jsou určeny rekurentními vztahy, resp. diferenčními rovnicemi an+i = an + d, resp. Aan = d, fln+i =q-an, resp. Aan = {q— l)a„, an+2 = fln+i + an, resp. A2a„ = an — Aan. □ Lineární diferenční rovnice Všechny uvedené vztahy/rovnice mají společné to, že jsou lineární, tzn. jednoduché. Ukážeme si, jak najít řešení těchto rovnic přímo, tj. bez matematické indukce. Lineární diferenční rovnice jsou rovnice, které je možné přepsat ve tvaru f'(x) = k(x)-f(x)+r(x) f"(x) = k(x)-f'(x) + l(x)-f(x)+r(x) kde koeficienty (kn), (ln), (rn) jsou nějaké posloupnosti. Pokud je rn = 0, pak se rovnice jmenuje homogenní a právě s těmi začneme. Aan = (f(n, an) A2an = ip(n, an,Aan) CLn-\-i kn • cin -\- rn 15 Diferenční a sumační počty 67 Úloha 58. Najděte v předchozím výčtu homogenní lineární diferenční rovnice a určete jejich obecná řešení. Řešení. Z uvedených rovnic to jsou právě rovnice popisující geometrickou a Fibonacciho posloupnost. V obou případech jsou všechny koeficienty konstantní, což dělá úlohu výrazně jednodušší. Obecným řešením rovnice an+i = q-an je každá geometrická posloupnost tvaru an = C -qn, kde C e M je libovolná konstanta. Z předchozí rovnice plyne, že an+2 = q2 -an, což má následující užitečné důsledky: Pokud by kvocient q byl řešením algebraické rovnice x2 = k-x + l, potom by geometrická posloupnost qn zřejmě byla řešením diferenční rovnice = k ■ a„+i + l-an. Přitom každý její násobek by taky byl řešením a pro dvě různá řešení by také jejich součet byl řešením. Odtud plyne návod, jak hledat obecné řešení rovnic tohoto typu, který jsme demonstrovali <@j) na rovnici popisující Fibonacciho posloupnost v úloze 37 na str. 40. □ Úloha 59. Najděte v předchozím výčtu nehomogenní lineární diferenční rovnice a určete jejich obecná řešení. Řešení. Velmi speciální rovnice tohoto typu jsou rovnice popisující aritmetickou posloupnost a rovnice z úlohy 35. Speciálnost spočívá v tom, že obě tyto rovnice lze vyjádřit ve tvaru rn, tudíž obecné řešení je an = Y rn + C, kde C e R. Dalším příkladem nehomogenní lineární diferenční rovnice byla rovnice z úlohy 36 o hanojských věžích... □ 15.4 Poznámky V souvislosti s určováním součtů posloupností typu an = nr potřebujeme hned zkraje řešit následující úlohu, která může být zajímavá sama o sobě: Úloha 60. Vyjádřete nr jakožto lineární kombinaci n- pro i = 1,..., r. Řešení. Z předešlého víme, že n1 = n-, n2 = n- + n—. Podobně se zdůvodní, že n3 = + 3n- + n-, n4 = n- + 6n^ + In- + n-, ... Zajímavou diskuzi k možnému zobecnění lze najít v [G]... □ Uvědomte si, že s větou 15.2 jsme se obecně nezbavili problému, který zmiňujeme před úlohou 23. Tato věta jej však transformuje na problém, zda lze primitivní posloupnost k dané posloupnosti vyjádřit v uzavřeném tvaru, či nikoli. Úloha 61. Dokažte, že pro žádné r > 0 neumíte vyjádřit primitivní posloupnost k posloupnosti an = v uzavřeném tvaru. 68 II Zázemí a další příklady Nejen, že to neumíme — ono to opravdu, ale opravdu nejde! Nicméně při experimentování s tímto úkolem si pravděpodobně každý všimne, že A ji) n+1 n n(n + 1) Tento postřeh s maximálním potěšením používáme při řešení (b) úlohy 22 na str. 25... Pokud narazíme na lineární diferenční rovnici, která nemá konstantní koeficienty, pak nemůžeme předpokládat existenci konstantního řešení, jak jsme to dělali v řešení úlohy 36. V takovém případě těžiště úlohy tkví právě v nalezení nějakého jednoho partikulárního řešení! Tento problém tady nehodláme příliš rozmazávat, ale měli bychom si aspoň uvědomovat, že existují různé metody, jak si s ním poradit. Tak jako v celé této části, spousta nápadů je analogická tomu, co znáte z matematické analýzy: Úloha 62. Vzpomeňte na některé metody řešení lineárních diferenciálních rovnic a zkuste je (jS> aplikovat k dořešení např. diferenční rovnice (30). 16 Nekonečné součty aneb řady Číselná posloupnost je uspořádaná oo-tice reálných čísel, neboli zobrazení a : N —>• R. Místo a(n) píšeme an a (a\, a2,......) zkracujeme (an)^=1 nebo taky (an). Konečné součty prvních n členů obvykle značíme n sn ■= «1 + «2 H-----1- an = ^ ftfc- fe=i Nekonečný součet posloupnosti (a„)^=1, neboli řada, je právě limita posloupnosti částečných součtů: cli + a2 + • • • = > &/c := lim s ' * Tí.—^OO fe=l Tato limita může, ale nemusí existovat; podle toho rozlišujeme, zda řada konverguje, nebo diverguje. Základní otázky — v případě, že neumíme vyjádřit posloupnost částečných součtů v uzavřeném tvaru — jsou: • Jak poznat, zda daná řada konverguje/diverguje? • Jak přibližně vyjádřit součet konvergentní řady a jak případně tento součet zpřesnit? Reprezentativní vzorek konkrétních úloh tohoto typu jsme řešili v podkap. 5. Tady rychle doplníme několik souvisejících poznatků... 16.1 Vybrané poznatky Jednoduchá, ale užitečná nutná podmínka konvergence řady: oo Věta. Pokud řada ak konverguje, potom lim ak = 0. fe=i fe^°° 16 Nekonečné součty aneb řady 69 To, že opačná implikace obecně neplatí, se s oblibou ilustruje např. na harmonické řadě, viz úlohu 28 na str. 28... Aplikace integrálního kritéria v oné úloze byla obzvlášť jednoduchá a elegantní, takže nemusíme cítit potřebu se k této úloze vracet. Avšak divergenci harmonické řady lze taky velmi snadno zdůvodnit s odkazem na následující obecné tvrzení. Věta. Řada E ak konverguje absolutně právě tehdy, když její součet nezávisí na pořadí k=l sčítanců v řadě. (To, že řada E afe konverguje absolutně znamená, že konverguje řada E lafcl> jejíž všichni fe=i fe=i sčítanci jsou nezáporní.) Úloha 63 (harmonická podruhé). Dokažte znovu, že harmonická řada diverguje. Řešení. Vzhledem k tomu, že harmonická řada je tvořena výhradně kladnými sčítanci, tak předpoklad konvergence automaticky znamená absolutní konvergenci. Předpokládejme tedy, že harmonická řada konverguje a má součet s. Podle předchozí věty by se žádným přeskládáním sčítanců neměl tento součet změnit. My však ukážeme, že se po vhodném přeskládání změní, což bude spor s předpokladem, takže harmonická řada musí být divergentní. Nápadů s přeskládáním této řady existuje celá řada,4 zde je jedna ukázka: S=[í + \) + (l + \) + (l + l = 11 n íl 1V íl 1 2) \2 12 J \3 30 Nyní sčítance přeskládáme a dostaneme 11 \ (\ 1 1 2 + 3+---J + U + T2^3Ô což se rovná s plus něco nenulového, čili něco jiného než byl původní součet s. □ Do páru s předposlední větou ještě připomínáme jedno důležité tvrzení, se kterým se taky dá vymyslet spousta inteligentní zábavy. Věta (Riemannova). Předpokládejme, že řada E konverguje, ale nikoli absolutně. Potom k=l je možné přeskládat sčítance v řadě tak, že tato nová řada konverguje k libovolnému reálnému číslu, příp. diverguje k oo, příp. diverguje k — oo, příp. osciluje. Úloha 64 (Leibnizova). Přeskládejte Leibnizovu řadu tak, abyste dostali řadu s dvojnásobným součtem. http://www.mathteacherctk.com/blog/2010/lO/a-divergent-harmonic-series/ 70 II Zázemí a další příklady Řešení. Leibnizova řada je alternující řada 111 ~(_i)fe+i k=l Pomocí Leibnizova kritéria se snadno zdůvodní, že Leibnizova řada konverguje; součet označíme s. Bereme-li všechny sčítance v absolutní hodnotě, dostáváme řadu harmonickou, o níž víme, že diverguje. Proto Leibnizova řada konverguje, ale nikoli absolutně. Podle Riemannovy věty je možné sčítance zamíchat tak, že dostaneme libovolný součet. Dvojnásobný součet je možné obdržet např. takto: Nejprve si sčítance (v původním pořadí) upravíme po vhodném přeskládání dostáváme □ 16.2 Další poznatky V předchozím jsme odkazovali na integrální kritérium konvergence (pro klesající řady s kladnými členy) a Leibnizovo kritérium (pro alternující řady). Dále jsme např. v úloze 29 použili přímé porovnání s nějakou lépe uchopitelnou řadou, což je vůbec nejlepší... Kromě těchto kritérií si jistě ještě vzpomínáme na kritérium podílové a odmocninové. Uvědomte si, čím byla tato dvě kritéria motivována a proč je jejich užití u většiny předchozích (jS> úloh k ničemu... Současně připomínáme, že kdykoli umíme pomocí nějakého kritéria rozhodnout o konvergenci dané řady, jsme odtud vždy schopni zformulovat určitý odhad neznámého součtu, a to s libovolnou přesností. Tímto jsme se částečně zabývali v odst. 5.2... 17 Eukleidovské konstrukce Eukleidovské konstrukce jsou geometrické konstrukce, které jsou realizovatelné výhradně pomocí eukleidovského pravítka a kružítka, tzn. v duchu prvních tří Eukleidových postulátů [E]... 17.1 Sestrojitelné veličiny Několikrát jsme se dotkli problému sestrojitelnosti reálných veličin. Konstrukci té či oné veličiny chápeme jako konstrukci reálného čísla, které onu veličinu zastupuje. Vzhledem k tomu, že v eukleidovské geometrii neexistuje žádná kanonická jednotka, musí být tato nějak specifikována předem. Základní otázky zní: • Jak poznat, zda je dané reálné číslo sestrojitelné? • Jak přesně takové číslo — vzhledem k dané jednotce — sestrojit? 17 Eukleidovské konstrukce 71 Cvičení Algebraické operace, které jistě umíme s eukleidovským pravítkem a kružítkem reprodukovat, (jS> jsou následující: • součet a rozdíl, a to pomocí přikládání a odebírání úseček na přímce, • součin a podíl, a to např. pomocí podobných trojúhelníků (viz též konstrukci na obr. 34), • druhá odmocnina, a to např. pomocí Eukleidovy věty o odvěsně, resp. o výšce (viz obr. 35), ve specifických případech lze použít také větu Pythagorovu. Z uvedeného plyne, že jsou-li a a b sestrojitelná reálná čísla, pak také a + b, a — b, a-b, a:b, ^[a jsou sestrojitelná čísla. Opakováním těchto operací můžeme sestrojovat další a další čísla... Charakterizace Pokud chceme úplně charakterizovat všechna eukleidovsky sestrojitelná čísla, je nutné se na problém podívat více algebraickýma očima. Bod v eukleidovské rovině interpretujeme jako dvojici reálných čísel (souřadnice v kartézské reálné rovině). Stačí charakterizovat, která reálná čísla jsou sestrojitelná z 1 (volba jednotky na souřadných osách): • Pomocí konstrukcí odpovídajících operacím + a — lze sestrojit pouze body s celočíselnými souřadnicemi. • Pomocí konstrukcí odpovídajících operacím • a : lze sestrojit pouze body s racionálními souřadnicemi. • Jakoukoli další eukleidovskou konstrukcí lze sestrojit buď bod s racionálními souřadnicemi (průnik dvou přímek), nebo bod se souřadnicemi z tělesa5 Qi := Q[Vď\ = {a + bVď\a,be Q}, kde \fd není racionální (průnik přímky a kružnice nebo průnik dvou kružnic). • Dalšími konstrukcemi lze sestrojit jedině body, jejichž souřadnice postupně patří do těles Q2:=Qi[V^i], Q3:=Q2[V^2], atd., kde dx e Qi, d2 G Q2, atd. Věta. Reálné číslo je sestrojitelné eukleidovským pravítkem a kružítkem právě tehdy, když jej lze vyjádřit pomocí konečného počtu 1 a operací +, —, ■, :, ^J~, příp. závorek. Jinak řečeno, reálné číslo je eukleidovsky sestrojitelné, právě když patří do nějakého tělesa z posloupnosti {1} C Z C Q =: Q0 C Qi C Q2 C • • • C Qk C • • • C R, kde Qi+i = Qi [vW| pro nějaké di e sestrojitelné. Pokud ano, vymyslete nějakou jeho konstrukci. Pokud potřebujete konkrétnější zadání, zkuste např. čísla (54), resp. (55). Viz též několik problémů v odst. 17.3... 17.2 Kvadratura rovinných útvarů (Geometrickou) kvadraturou rovinného útvaru se myslí konstrukce čtverce, který má stejný obsah jako daný útvar. Přitom konstrukcí jako obvykle myslíme konstrukci eukleidovskou. Pojem obsahu není v Základech nijak vymezen, avšak nakládá se s ním jako s každou jinou veličinou podle vyslovených axiómů. Zejména platí, že shodné útvary mají stejný obsah. Kvadratura obecného mnohoúhelníku Posloupnost tvrzení v [E] (počínaje 1.34 a vrcholíce 11.14) řeší tento problém pro libovolné mno-(jS> hoúhelníky. Klíčová tvrzení a konstrukční návody připomínáme na obr. 33-35... Obrázek 33:1.35: Rovnoběžníky se stejnou základnou a stejnou výškou mají stejný obsah. Všimněte si, že se znalostí Thaletovy věty lze úsečku EH na obr. 35 interpretovat jako výšku v pravoúhlém trojúhelníku BHF. Tvrzení 11.14 tedy zdůvodňuje tzv. Eukleidovu větu o výšce. Stříhání Zdůvodnění mnoha tvrzení, která se týkají stejných obsahů, jsou založena na shodnostech částí, z nichž se dané útvary skládají. To znamená, že stejnoplochost lze v mnoha případech názorně demonstrovat tak, že se jeden útvar rozstříhá a ze vzniklých částí se složí ten druhý. 17 Eukleidovské konstrukce 73 Obrázek 34: 1.44: Konstrukce rovnoběžníku (ABML), který má dánu jednu stranu (AB) a stejný obsah jako daný trojúhelník (resp. rovnoběžník GBEF). Obrázek 35: 11.14: Konstrukce strany čtverce (EH), který má stejný obsah jako daný mnohoúhelník (resp. obdélník BCDE). Ve výše diskutované kvadratuře mnohoúhelníku nemusí být na první pohled zřejmé, jak by (jS> se měly stříhat stejnoploché pravoúhelníky — tento krok je znázorněn na obr. 36... Drobné zobecnění dosavadních pozorování je shrnuto v následující větě: Věta (Wallaceova-Bolyaiova-Gerwienova). Dva mnohoúhelníky mají stejný obsah právě tehdy, když jeden lze rozstříhat na části, z nichž lze složit ten druhý. S těmito poznatky můžeme snadno sestrojovat svoje vlastní důkazy některých známých tvrzení, která se týkají rovností obsahů... Úloha 66. Dokažte, že umíte kvadraturovat obecný mnohoúhelník, a to i s dodatečným stříháním. Jedna z možností kvadratury obecného trojúhelníku je představena na obr. 37. Kvadratura křivých oblastí Kromě libovolného mnohoúhelníku je možné kvadraturovat také řadu oblastí s křivou hranicí. Klasickými příklady jsou např. parabolická úseč (viz úlohu 34 na str. 31) nebo Hippokratovy půlměsíce: Úloha 67 (Hippokratova). Dokažte, že nad libovolným pravoúhlým trojúhelníkem platí, že obsah půlměsíců vyznačených na obr. 38 je stejný jako obsah trojúhelníku. <@j) S kruhem je to samozřejmě jiné — viz úlohu 68... 74 II Zázemí a další příklady 17.3 Slavné problémy starověku Problém geometrické kvadratury kruhu je jeden z nej slavnějších problémů starověku. Do této skupiny problémů patří také • problém rektifikace kružnice (konstrukce úsečky, jejíž velikost je rovna obvodu dané kružnice) , • problém zdvojení krychle (konstrukce krychle s dvojnásobným objemem jako daná krychle), • problém trisekce úhlu (rozdělení daného úhlu na třetiny), • problém konstrukce pravidelného n-úhelníku. Posledním dvěma jmenovaným problémům se věnujeme samostatně v podkap. 10 (viz úlohy 47 a 51); diskuzí nad zbylými problémy se rozloučíme: Úloha 68 (slavná). Zdůvodněte, proč není možné (i) zdvojit krychli, (ii) kvadraturovat kruh, (iii) rektifikovat kružnici, a to pouze pomocí eukleidovského pravítka a kružítka. Řešení, (i) Je-li velikost hrany dané krychle a, pak hledaná krychle má mít hranu délky x = y/2a. Třetí odmocnina ze 2 je sice algebraické číslo, ale podle věty 17.1 není sestrojitelné. (ii) Je-li poloměr daného kruhu r, pak hledaný čtverec má mít hranu dlouhou x = y/Ťřr. Číslo 7T, natož pak jeho odmocnina, není vůbec algebraické číslo, tudíž není sestrojitelné. 17 Eukleidovské konstrukce 75 Obrázek 38: Hippokratovy půlměsíce (iii) Je-li poloměr dané kružnice r, pak hledaná úsečka má mít velikost x = 2irr. Ze stejného důvodu jako výše není tato úloha řešitelná. □ Poznámky k měření kruhu V řešení předchozí úlohy používáme dnes obvyklý způsob vyjadřování obsahu kruhu a obvodu kružnice, stejně jako poměrně nedávný poznatek, že ir není algebraické číslo. Vzhledem k důležitosti těchto informací, přikládáme stručný přehled: (1) Ve XII. knize Eukleidových Základů je odvozeno, že: • Poměr obsahů kruhů je stejný jako poměr druhých mocnin jejich průměrů.6 Při obvyklém značení můžeme obsah věty psát takto: Sx : S2 = r\ : r2 neboli Sx : r\ = S2 : r\ = konst. (56) (2) V Archimedove práci O měření kruhu je dokázáno, že: • Obsah kruhu je roven obsahu pravoúhlého trojúhelníku, jehož jedna odvěsna je shodná s poloměrem, druhá s obvodem kruhu. 7 Při obvyklém značení věta říká, že S = \r ■ o, což spolu s (56) dává 1 „ S = —r-o = konst-r . 2 To znamená, že stejná konstanta vystupuje ve vyjádření jak obsahu, tak obvodu kruhu v závislosti na jeho poloměru. Tradičně se tato konstanta značí ir, tudíž o = 2tt-t a S = tt-r2. Z tohoto výsledku vyplývá, že problém kvadratury kruhu je ekvivalentní problému rektifikace kružnice. (3) Od roku 1767 se díky J.H. Lambertovi ví, že: 6http://alephO.clarku.edu/~dj oyce/java/elements/bookXII/propXII2.html 7http://en.wikipedia.org/wiki/Measurement_of_a_Circle 76 II Zázemí a další příklady Obrázek 39: K měření kruhu. • Číslo tt není racionální.8 (4) A teprve od roku 1882 se díky F. Lindemannovi ví, že: • Číslo tt není algebraické.9 Odtud je konečně patrné, proč byla kvadratura kruhu (ekvivalentně, rektifikace kružnice) po tak neobyčejně dlouhou dobu otevřeným problémem... 18 Shodnosti v rovině V podkap. 9 potřebujeme znát, kolik existuje typů shodností v rovině a jak se navzájem skládají. Pro doplnění přikládáme jednu dobře známou tabulku, kde jsou všechny shodnosti charakterizovány podle jejich samodružných prvků... Mezi těmito transformacemi je jedna základní — osová souměrnost. Důvod tohoto pojmenování je zřejmý z následujícího cvičení: Úloha 69. Dokažte, že každou shodnost v rovině lze vyjádřit pomocí nejvýše tří osových soměr-(jS> ností. Obrázek 41 8http: //en. wikipedia. org/wiki/Proof _that_'/,CF'/,80_is_irrational 9http: //en. wikipedia. org/wiki/Lindemann,/,E2'/,80,/,93Weierstrass_theorem#Transcendence_of _e_and_. CF. 80 18 Shodnosti v rovině 77 Samodrožaé . \^ směry body Žádný Právě dva na sebe kolmé Každý 1 Žádný Posunutá souměrnost P Posunuti Právě jeden | cosa -siná ^„ P isina cosa / a*ku, k celé' Rotace o úhel