MA2MP_SMR2 podzim 2013 Obsah 1. Lineární diofantické rovnice 1 2. Míchání karet 6 3. Matematická indukce 9 4. Posloupnosti a jejich součty 11 5. Diferenční a sumační počty 18 6. Zatím nezařazeno 24 Reference 30 Seznam obrázků 31 Rejstřík 32 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 s 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ř. [C, Ko, Pe, Smi, Stí], 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, E, HKS, L, N, Po] apod. Vybíráme taky úlohy ze školních seminářů a soutěží, jako např. [MO, MKS, V]. Pozor, tento materiál se průběžně vyvíjí a upravuje, sledujte datum aktualizace... 1. 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í? Tyto otázky 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ů.1 Něco o diofantických rovnicích se lze naučit např. z knihy [HKS]. Nej jednodušší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, (1) 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 Date: 22. listopadu 2013, V. Žádník. ^http : //cs . wikipedia. org/wiki/Hilbertovy_probl0/oC30/0A9my 1 2 PODZIM 2013 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 odstavec 1.6. S takovými případy se každý mnohokrát setkal, proto začínáme rovnou s obecnou úlohou. 1.1. Postřehy. Pokud čísla a,b,... na levé straně (1) mají nějakého společného dělitele, který není dělitelem čísla k, pak je jasné, že taková rovnice nemůže mít celočíselné řešení. Máme tedy jednoduchou nutnou podmínku řešitelnosti. 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 1. Lineární diofantická rovnice (1) 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 moc zaobírat. Pro rovnice se dvěma neznámými začneme s konkrétním příkladem. Úloha 1. Určete všechna řešení diofantické rovnice Ax + 7y — 10. Nyní uvažujme obecnou rovnici se dvěma neznámými ax + by — h, (2) pro niž předpokládáme, že NSD(a, b) dělí h. Pokud jsou a, b a h dostatečně hezká čí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 G Z, popisují nekonečně mnoho řešení rovnice (2). 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 (Eř> kontrola nebyla nutná?) 1.2. Obecné řešení. 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 nějaké takové řešení vždycky najdeme početně (za předpokladu, že je splněna podmínka řešitelnosti rovnice). Návod plyne z následující věty a jejího důkazu: Věta 2 (Bezoutova). Je-li NSD(a, b) — d, pak existují celá čísla k a l taková, že platí ak + bl — d. (3) Podstatné je, že důkaz tohoto tvrzení je konstruktivní — čísla k a l je možné velmi efektivně (jE3> spočítat pomocí Eukleidova algoritmu! Předpokládejme tedy, že NSD(a, b) — d, d dělí h a že máme určena celá čísla kal, pro něž platí (3). Potom je zřejmé, že dvojice Xp~ cť Vp~ d je řešením rovnice (2). Zbytek řešení je stejný jako v předchozím odstavci... MA2MP.SMR2 3 1.3. Alternativní obecné řešení. Vzpomeňme, jak by se rovnice (2) ř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, »=—■ W Nyní řešíme tutéž úlohu nad celými čísly, takže potřebujeme určit, pro která i £ Z je taky číslo (4) 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 (2), 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 6", 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, ax — h mod o. Naše úloha je tímto transformována na řešení jedné kongruence s jednou neznámou. Pokud je kongruence řešitelná, lze řešení celkem rychle najít obvyklými úpravami, které je vhodné si na tomto místě připomenout.. . 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 3. Kongruence (5) je řešitelná právě tehdy, kdyžNSD(a,b) dělí h. Zdůvodnění tohoto tvrzení vypadá následovně: Stejně jako ve Větě 1, je implikace zleva doprava je 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 (5) psát ekvivalentní kongruenci ^x = ^ mod ^, kde už jsou čísla 2 a 2 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 7^ 0 je kongruence (5) ekvivalentní s c-ax = c-h mod b. Řešení určíme tak, že nedosazujeme libovolné, ale naopak nějaké vhodné c, řekněme c = a^-\ kde (f : N —>• N je Eulerova funkce. Takto dostáváme a^iEo^"1-/! mod b, což je podle Eulerovy věty totéž jako lEa^1-/! mod b. (6) To znamená, že x — je řešením kongruence (5). Navíc všechna další řešení se liší právě o celočíselné násobky čísla b. □ Pokud umíme vyjádřit hodnotu Eulerovy funkce (p(b), potom z (6) máme rovnou všechna řešení kongruence (5), což nám po dosazení do (4) dává všechna řešení diofantické rovnice (2), se kterou jsme začínali... 4 PODZIM 2013 1.4. Eulerova funkce a Eulerova věta. Eulerova funkce je zobrazení ip : N —>• N, které lze definovat různě: je-li b — p^1 -p^'2 ■ ■ ■ ■ prvočíselný rozklad čísla b, potom hodnota p(b) je p^^ip^-pr-^-ipr-p?-1)---- í1 pi) í1 p2) ^ — počet čísel od 1 do b, která jsou nesoudělná s b; je-li 6=1, definuje se ip(b) — 1. Pokud bereme první rovnost v (7) 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 triviální. Úloha 2. Dokažte platnost třetí rovnosti v definici Eulerovy funkce. Věta 4 (Eulerova). Jsou-li a G Z a b G N nesoudělná čísla, potom platí av{b) = 1 mod b. (8) 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. (9) Pro nás asi nej srozumitelnější zdůvodnění Eulerovy věty lze najít v rámci teorie konečných grup, s odkazem na větu Lagrangeovu... 2 1.5. Rovnice s libovolným počtem neznámých. Ve Větě 1 uvažujeme libovolný počet neznámých, ale zatím jsme mluvili jen o rovnicích se dvěma neznámými. Předchozí postřehy je však možné velmi jednoduše rozšířit tak, že věta skutečně platí. Ukážeme, jak by se argumentovalo pro rovnici se třemi neznámými, a obecný indukční krok necháváme zájemcům k vlastnímu procvičení. Úloha 3. Určete všechna řešeni diofantické rovnice Ax + 7y + 12 z — 10. Abychom si uvědomili, jak je to vlastně s podmínkou řešitelnosti, uvažujme obecnou rovnici se třemi neznámými ax + by + cz — h, (10) 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 nám zaručuje řešitelnost rovnice (10). 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. (11) Protože NSD(to, c) je roven NSD(a, b, c), a ten je podle předpokladu roven 1, máme podle Věty 3 zaručenu řešitelnost této kongruence. Když ji vyřešíme a výsledek dosadíme do (10), 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. 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 (11), 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 (10). □ 2http://en.wikipedia.org/wiki/Euler's_theorem MA2MP.SMR2 5 1.6. Poznámky a modifikace. Typické úlohy, které vedou k lineárním diofantickým rovnicím, jsou úlohy s přeléváním vody, vážením na vahách, placením v obchodě, 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ř. úlohu 4 ve variantě (b) lze interpretovat jako hledání cesty v jistém orientovaném grafu... Úloha 4. Pomoci tři nádob o objemu 4-, 7 a 12 litrů potřebujeme odměřit 10 litrů vody. (a) Určete všechna řešení za předpokladu, že máte neomezený zdroj vody a libovolně velkou pomocnou nádobu. (b) Určete všechna řešení, pokud máte pouze ony tři nádoby, z nichž ta největší je na začátku plná. (c) U obou předchozích variant úlohy najděte nejméně pracné řešení. Často také potkáváme soustavy diofantických rovnic, příp. nerovnic. Je typické, že k jednoznačnému, příp. ke konečnému počtu řešení vedou i soustavy, kde je méně rovnic než neznámých (což je nad racionálními nebo reálnými čísly nemyslitelné). Úloha 5 (Eulerova). Jistá osoba koupila vepře, kozy a ovce, celkem 100 kusů za 100 korun. Vepři ho stáli 3| koruny za kus, kozy l| a ovce \ koruny. Kolik kusů každého druhu nakoupil1? [Po] Úloha 6. Na dračím ostrově žilo 103 modrých a 113 zelených draků. Zlý čaroděj ostrov zaklel: „Když se setkají 3 draci jedné barvy s 5 draky druhé barvy, všech 8 navždy zmizí!" Je možné, aby na ostrově zůstali jenom modří draci? Kolik by jich potom bylo ? [MO, 50. ročník] Úloha 7. 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 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 8. Útrata v obchodě je vyjádřena přirozeným číslem. Máme k dispozici pouze čtyřkorunové 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 Ax + 7y — h vždy nějaké kladné celočíselné řešení. Protože se jedná o lineární úlohu ve dvou proměnných, můžeme si do jisté míry pomáhat obrázky, viz obr. 1. Obecná formulace Frobeniova problému je tato:3 Úloha t)9 (Frobeniova). U rovnice (1) 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; 3http://en.wikipedia.org/wiki/Coin_problem 6 PODZIM 2013 1 2 3 4 6 x Obrázek 1. 4x + 7y — h zdůvodnění však není vůbec jednoduché...4 2. míchání karet 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 částečné řešení jednoho specifického problému spojeného s mícháním, jež je popsán v [Stí, kap. 11]. Všechny následující empirické údaje a grafy jsou dílem Š. Křehlíka. Opakujeme-li míchání balíčku s N kartami aspoň AM-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. Zmíněná kapitola v [Stí] se soustředí na tzv. faro čili tkalcovské mícháni: 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 tkalcovském míchání změní na 142536; po jednom vnitřním tkalcovském míchání na 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 10. 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í. 2.1. 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 38 40 L 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 N 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 L 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 Na obr. 2 pro představu znázorňujeme prvních 25 výsledků graficky (vodorovně N, svisle Ľ). ^http : //www. ams . org/samplings/feature-column/fc-2013-08 MA2MP.SMR2 7 Obrázek 2. 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í AT = 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, • pro n — 10 jeden cyklus délky 6 a jeden délky 2, • 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ě. 2.2. 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. Onu permutaci označíme P a úplně jednoduše se ukáže, že tato permutace funguje následovně: P(k) = 2k-Í 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) ee16A;-15 ? mod (JV-1). Tato pozorování potřebujeme zobecnit. Pomocí matematické indukce snadno dokážeme, že pro libovolné n e N platí Pn(k) = 2n(k-Í) + Í mod(iV-l). (12) 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 E {1,..., N}, což je vzhledem k (12) ekvivalentní s podmínkou 2L(k-í) + í = k mod(iV-l). Tato kongruence platí pro všechna k právě tehdy, když 2L = Í mod(iV-l). (13) Celý odstavec tak můžeme uzavřít následující sympatickou ekvivalencí, jež charakterizuje řešení úlohy 10: 8 podzim 2013 Věta 5. 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í (13). 2.3. Řešení. Protože N je zde vždycky sudé, jsou čísla 2 a N — 1 nesoudělná. Tudíž podle Eulerovy věty víme, že L = if(N - 1) je zaručeně řešením předchozí rovnice, viz odstavec 1.4. Odtud mimochodem plyne, že L < N — 1, což je celkem slušný odhad (zejména ve srovnání s úvodním N\). 2.4. Minimální řešení. Jak z praktických, tak i z teoretických důvodů nás samozřejmě zajímá (Eř> nejmenší možné řešení. Úplně snadno lze zdůvodnit následující tvrzení: Věta 6. 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í, potom L dělí (p(N — 1). 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 — 1): N 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 L 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 f 1 2 4 6 6 10 12 8 16 18 12 22 20 18 28 30 32 24 36 24 N 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 L 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 f 40 42 24 46 42 Stejně tak doplníme předchozí grafické znázornění, viz obr. 3. 50 -i- 40 30----- 25--1-i-~ 15 10 B ■ 0 H-1-1-1-1-1-1-1-1-1-1- 0 5 10 15 20 25 30 35 40 45 50 55 Obrázek 3. Vidíme, že minimální řešení někdy je a jindy není vlastním dělitelem hodnoty ip(N — 1). Vyznat (Eř> se v tomhle obecně vypadá jako mnohem složitější problém... Úloha jjll. 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í. Obecnou odpověď neznáme; snadno však zdůvodníme jeden z úvodních postřehů: Věta 7. Pokud balíček obsahuje N — 2m karet, pak nejmenší možné L je rovno m. MA2MP.SMR2 9 Vzhledem k předchozím rozvahám stačí ukázat, že L — m je nejmenším řešením rovnice 2L = 1 mod(2m-l), což je vskutku snadné. □ 3. Matematická indukce Matematickou indukci potřebujeme ke korektnímu zobecňování pořád. V tomto materiálu na ni odkazujeme v odstavcích 1.5 a 2.2, v úloze 2 a jinde. Hodně úloh, které lze taky řešit indukcí, najdete v částech 4 a 5. 3.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: Pokud • pro libovolný dílek platí, že je-li tento shozen, pak spadne taky dílek následující, • a je-li současně shozen první dílek, potom nakonec leží všechny dílky. 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ů, ovšem za předpokladu, že řada má jasně vymezený začátek. Obrázek 4. 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ějaký (libovolný) výrok, který závisí na n g N. Princip (matematické indukce). Předpokládejme, že • platí V(1), • pro libovolné k g N platí (V (k) =4> V (k + 1)). Potom platí V(n) pro všechna n g N. Vzpomeňte si, že v Peanově axiomatickém popisu přirozených čísel je princip matematické indukce jedním z axiómů. K výše uvedeným příkladům užití matematické indukce přikládáme ještě pár dalších: Úloha 12 (Binomická věta). Dokažte binomickou větu: (a + b)n = an + nan-Yb + ■ ■ ■ + Q an-kbk + ••• + &". (14) Úloha 13. Dokažte, že libovolnou mapu tvořenou výhradně přímkami nebo kružnicemi lze vybarvit dvěma barvami. 10 PODZIM 2013 Úloha 14 (Hanojské věže). Najděte obecné řešeni problému známého jako Hanojské věže? ve variantě pro tři věže. 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í a± — 1, a,2 — 3, a% — 7 atd. Obecně umíme zdůvodnit, že an+i — 2a„ + 1, odkud se snadno matematickou indukcí dokáže, že an — 2™ — 1. □ Často užíváme matematickou indukci v různě pozměněných podobách. Typickou variantou je omezení typu n > uq, kde uq je nějaké přirozené číslo různé od 1. (Takové modifikace můžeme uvažovat i u všech následujících formulací, což už znova dělat nebudeme.) Úloha 15. Dokažte, že pro libovolné h > 18 má rovnice Ax + 7y — h řešeni v oboru přirozených ěisel. 3.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ě... Úloha 16 (Fibonacciho posloupnost). Dokažte, že n-tý člen Fibonacciho posloupnosti lze vyjádřit v následujícím tvaru: (i + VE)n - (i - VE)n an =-wš-' (15) Fibonacciho posloupnost začíná takto 1,1, 2, 3, 5, 8,13,... a úplně je určena rekurentním vztahem «1 — «2 — 1, «n+2 — «n+l + «n ■ 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é keN platí (V(k) A V(k + 1) V(k + 2)). Potom platí V(n) pro všechna n g 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) =4> V (k + 1). Potom platí V (n) pro všechna n g N. Typické a velmi dobře známé tvrzení, které se dokazuje pomocí tohoto principu, je v následující úloze: Úloha 17. Dokažte, že každé celé číslo větší než 1 je součinem prvočísel. 3.3. Poznámky a modifikace. Z teorie množin bychom měli znát následující zobecnění principu matematické indukce pro libovolnou dobře uspořádanou množinu. Princip (transfinitní indukce). Předpokládejme, že M je dobře uspořádaná množina, k,l g M a platí • (V(k) pro všechna k < l) =>• V (V). Potom platí V(n) pro všechna n g M. 5http : //cs . wikipedia.org/wiki/Hanoj sk°/,C3y,A9_vy,C4y,9B°/,C5y,BE( MA2MP.SMR2 11 Úloha 18. Najděte ve svých poznámkách z teorie množin nějaké tvrzení, které se dokazuje pomocí transfinitní indukce. Jiná metoda, která souvisí s probíraným tématem 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 g N a platí • V(l) =4> (existuje k < l takové, že V(k)). Potom V(n) nemůže platit pro žádné n g N. Jedná se 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í následující proslulé úlohy: Úloha 19 (Fermatova). Dokažte, že rovnice x4 + y4 — z4 nemá řešení v oboru přirozených čísel. Myšlenka důkazu je následující: (1) Dokážeme, že neexistuje Pythagorejská trojice,6 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 — f4 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) pomocí 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ě O) 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. □ 4. Posloupnosti a jejich 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ů, příp. domýšlením těchto úkolů ad infinitum. Jisté obecné zázemí, na něž se ihned pokusíme rozpomenout, bychom měli mít z matematické analýzy III. Jedná se veskrze o úlohy induktivního charakteru, takže tuto část chápeme jako doplnění části předchozí. Většinu následujících úloh je však možné řešit i jinak, často velice přímo a elegantně, na což se taktéž soustředíme. Základní otázky zní: • Jak vyjádřit n-tý součet posloupnosti v uzavřeném tvaru? • Co se stane, když n —> oo? Uzavřeným tvarem v druhé otázce se myslí vyjádření „bez tří teček", neboli vyjádření n-tého součtu v závislosti na n pouze pomocí elementárních funkcí. V několika nejjednodušších případech ještě odpovíme na otázku • Jak vyjádřit n-tý člen posloupnosti, která je zadána rekurentním vztahem? K těmto otázkám se ještě budeme vracet v části 5. Všem fanouškům posloupností doporučujeme On-line Encyklopedii celočíselných posloupností.7 'Pythagorejské trojice jsou právě řešení úlohy 64. http://oeis.org/?language=czech 12 PODZIM 2013 4.1. Konečné součty. Číselná posloupnost je uspořádaná oo-tice reálných čísel, neboli zobrazení a : N —> M. Místo a(n) píšeme an a (ai, a,2,......) zkracujeme (an)^=1 nebo taky (a„). Konečné součty prvních n členů značíme sn ■■— ai + a2 H-----h a„ = ^ afc. «71 fe=i Nemůžeme samozřejmě začít jinak než s aritmetickými a geometrickými posloupnostmi. Aritmetická posloupnost s distancí d je definována rekurentním vztahem an+\ — an + d. Úloha 20 (Aritmetická). Dokažte, že pro aritmetickou posloupnost s distanci d piati in — «i + (n — l)d a sn — n{a\ + an)/2. Geometrická posloupnost s kvocientem q je definována rekurentním vztahem a„+i — an-q. Úloha 21 (Geometrická). Dokažte, že pro geometrickou posloupnost s kvocientem q platí n-1 1 1 an — aiq a sn — a\--. 1 - q Fibonacciho posloupnost jsme diskutovali v úloze 16. Úloha 22 (Fibonacciho). Dokažte, že pro Fibonacciho posloupnost platí Sn — Cln+2 — 1- Je mnohem lehčí dokázat, že daný vztah platí, než jej samostatně odvodit. Úloha 23. Dokažte, že všechny vztahy v předchozích třech úlohách umíte odvodit bez jakékoli předchozí nápovědy. Příliš mnoho posloupností, u nichž umíme obecně vyjádřit n-tý součet, neznáme. Připomeneme několik typů a pokusíme se naše obzory rozšířit. Zevrubněji se tomuto tématu věnuje např. celá jedna kapitola v [HKS] nebo [L]. Úloha 24. Pro následující posloupnosti vyjádřete jejich n-té součty a domyslete nějaká přirozená zobecnění: (a) an = (b) an = , (c) an = n3. Zobecněním případu (a) by mohla být jakákoli posloupnost, jejíž n-tý člen je součinem n-tých členů nějaké aritmetické a nějaké geometrické posloupnosti. K zobecňování případu (b) může významně přispět následující postřeh: 11 1 n(n +1) n n + 1 Zobecněním případu (c) by mohla být jakákoli posloupnost tvaru an — nr, (16) kde r g N. Právě pro posloupnosti tohoto typu lze vymyslet/najít skutečně mnoho různých odvození jejich součtů. Zejména pro malá r existují taky vizuálně atraktivní přímá zdůvodnění, viz např. [N]. Úloha 25. Dokažte, že rozumíte obrázkům 5-7. 4.2. Poznámky. Protože se k součtům posloupností typu (16) ještě hodláme vracet, shrneme tady několik ukázkových výsledků: J2k° = n, ^ k1 — n(n + l)/2, ^ k2 = n(n + l)(2n + l)/6, fe=i fe=i fe=i n n ^ k3 — n2(n + l)2/4, kA = n(n + l)(2n + l)(3n2 + 3n - l)/30 fe=i fe=i MA2MP.SMR2 13 O o o o o o o o • o O O O Q O o odob o o o do oao o o do o o op o o do o o do o oo#ooooo#o Obrázek 5. 1 + 2 MIMI . _!. . _ 5 ^3 □ □ □ Obrázek 6. 3(12 + 22 H-----h n2) = (2n + 1)(1 + 2 H-----h n) Ilimiti Obrázek 7. I3 + 23 H-----h n3 = (1 + 2 H-----h n)2 Poměrně hodně úloh, které se dají v této souvislosti úspěšně řešit, zahrnují součty s kombinačními čísly. Mezi nejznámější vztahy patří: E = 2" E n+í l + l E b« = (a + 6)r fe=0 v 7 fe=0 v 7 v 7 fe=0 Úloha 26. Dokažte některé z výše uvedených rovností, nejlépe několika různými způsoby. Uvědomte si, že 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, 14 podzim 2013 ž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:8 r n Úloha 27. Dokažte, že pro žádné r > 0 neumíte vyjádřit ^2 P7 v uzavřeném tvaru. k=l Ačkoli ani my ani nikdo jiný tyto součty v uzavřeném tvaru nevyjádří, měli bychom si být vědomi, že podle potřeby je možné jejich hodnoty odhadnout, a to v uzavřeném tvaru a s libovolnou přesností! Viz úlohy 32-35. 4.3. Nekonečné součty. Nekonečný součet posloupnosti (a„)^L1; neboli řada, je právě limita posloupnosti částečných součtů: oo Soo — «1 + «2 H----— ^ «fc ■— lim sn. fe=l Tato limita může, ale nemusí existovat — podle toho rozlišujeme, zda řada konverguje, nebo diverguje. Úloha 28. Pro řady tvořené posloupnostmi z předchozích dvou odstavců rozhodněte, zda konvergují, ěi divergují. Jediná aritmetická řada, která je konvergentní, je nulová řada. Geometrická řada je konvergentní právě tehdy, když |g| < 1; v takovém případě je lim qn — 0, takže taková řada má součet dl 1 - q viz též obr. 8. i r 1 a + ar + ar2 + ar3 + Obrázek 8. (a + ar + ar2 + ■ ■ •) : (£) — (ar) : (1 - r) Nejpozději na tomto místě bychom si měli vybavit zřejmou nutnou podmínku konvergence řady: oo Věta 8. Pokud řada ak konverguje, potom lim ak — 0. fe=i fe^°° To, že opačná implikace obecně neplatí, se s oblibou ilustruje např. na harmonické řadě, viz úlohu 32. Nejvíc úloh, které jsme kdy v těchto souvislostech potkali, se týká právě řad geometrických. Připomínáme jeden velmi známý problém: Úloha 29 (Achilles a želva). 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 přesně kdy. 8http://en.wikipedia.org/wiki/Harmonic_number MA2MP.SMR2 15 Na další úlohy operující s řadami lze narazit při elementárním vyjadřování obsahů rovinných obrazců. Úloha 30 (Kvadratura paraboly). Dokažte, že obsah úseče paraboly je roven 4/3 obsahu vepsaného trojúhelníku, jehož třetí vrchol je určen tím, že tečna paraboly v tomto bodě je rovnoběžná s protější stranou trojúhelníku. Obrázek 9. Na obr. 9 je naznačen postup řešení, jak jej realizoval Archimédés (ve 3. století př. Kr.): Trojúhelník, o kterém se mluví v zadání, je ten modrý. Plocha úseče je postupně vyčerpávána dalšími a dalšími vepsanými trojúhelníky, které mají stejnou vlastnost jako modrý trojúhelník. Z geometrických vlastností paraboly se dá vyvodit, že obsah každého trojúhelníku je osminový vzhledem k trojúhelníku, který mu v konstrukci předcházel. V n-tém kroku je tedy poměr obsahů vepsaného mnohoúhelníku a startovního modrého trojúhelníku roven 2 4 2™ odkud pro n —> oo dostaneme hledaný poměr obsahů parabolické úseče a modrého trojúhelníku. Tady však jasně rozeznáváme začátek geometrické řady s kvocientem i, kterou bez problému sečteme... □ Po této ukázce nás nemůže nenapadnout následující: Úloha 31. Řešte znovu úlohu 30 s nástroji moderní matematické analýzy. Máme samozřejmě na mysli užití určitého integrálu; z tréningových důvodů doporučujeme řešit (a) podle definice, (b) pomocí Newtonovy-Leibnizovy věty. n Uvědomte si, že díky výše zmiňovaným vzorcům pro ^ kr jsme v podstatě schopni určovat fe=i 6 integrály typu j xr dx podle definice. Naopak, pokud se nám nedaří sečíst nějakou posloupnost, a ale umíme zintegrovat funkci, která onu posloupnost interpoluje, pak nám tento výsledek může — za jistých předpokladů — pomoci v odhadu neznámého součtu. Úloha 32 (Harmonická). Dokažte, že oo (a) pro libovolné n > 1 platíhi ?|<| + | + -- - + i 1. fe=i Podobně jako pro harmonickou řadu, můžeme i v těchto případech odhadovat kterýkoli částečný součet a — pokud je řada konvergentní — taky její součet celkový. Odpovídající řady v následující úloze konvergentní jsou, což nám dovoluje stanovit odhad n-tého součtu nezávisle na n: 16 podzim 2013 Obrázek 10. j ^ dx < j] i < j dx i k—i i Úloha 34. Dokažte, že pro libovolné n > 1 platí: (a) & + + (b) £ + + (c) apod.9 Poté tyto odhady ještě o něco upřesněte. 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á konečný 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ů (viz úlohu 27), tudíž nemůžeme počítat její limitu. Nicméně každé z kritérií, pomocí něhož o konvergenci dané řady rozhodujeme, nám (jE3> vždy současně nabízí jakýsi odhad celkového součtu, a to s libovolnou přesností! Nezapomínejte, že nej jednodušším kritériem konvergence/divergence řady je přímé srovnání s nějakou řadou, o které víme všechno. e oo oo Úloha 35. Porovnejte řadu ^2 s řadou ^2 k(k+D > kterou jsme se naučili sčítat v úloze 24 (b), k=2 k=* a zrevidujte odhad v úloze 34(a). 4.4. Poznámky. 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 27 — neurčité integrály k mnoha elementárním funkcím jsou vyšší transcendentní funkce, což znamená, že je nelze vyjádřit v tzv. uzavřeném tvaru. Kromě integrálního a srovnávacího kritéria 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 (Eř> předchozích úloh k ničemu... Aplikace integrálního kritéria v úloze 32 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 9. Rada konverguje absolutně právě tehdy, když její součet nezávisí na pořadí k=l sčítanců v řadě. Úloha 36 (Harmonická podruhé). Dokažte znovu, že harmonická řada diverguje. 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á 9Nápověda: § = ! + §, I = § + I. MA2MP.SMR2 17 ř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,10 zde je jedna ukázka: a=(1+i) + (i+l) + (i+é = 11 n n n n 1 2) \2 12 J \3 30 Nyní sčítance přeskládáme a dostaneme 11 \ /l 1 1 1 ' 2 ' 3 ' "') \2 12 30 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 větou 9 ještě připomínáme jedno důležité tvrzení, se kterým se taky dá vymyslet spousta inteligentní zábavy. Věta 10 (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 37 (Leibnizova). Přeskládejte Leibnizovu řadu tak, abyste dostali řadu s dvojnásobným součtem. Leibnizova řada je alternující řada 1 1 1 ^(-l)fe+1 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 2\ 2 /2 2 ~2/4+(v3~6 po vhodném přeskládání dostáváme 2 2 2 2 2---1-----1------= 2s. □ 2 3 4 5 V tomto odstavci samozřejmě nesmíme opomenout některé obzvlášť významné nekonečné součty. Máme na mysli populární iracionální (zde dokonce transcendentní) čísla vyjádřená jako součty řad racionálních čísel. Jedno a to samé číslo lze samozřejmě vyjádřit různými způsoby, tady uvádíme jenom několik ukázek: Úloha 38. Dokažte, že oo (a) + Í + 1 + á fe=i oo (b) E <^- = l-i + i-i + ---=lii2, fe=i 10 http://www.mathteacherctk.com/blog/2010/10/a-divergent-harmonic-series/ 18 PODZIM 2013 (c) E fe=i (d) apod. (-i)fe 2fc-l 5. 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 prvním problému máme z odstavce 4.1, druhému jsme se okrajově věnovali tamtéž a navíc v úlohách 14 a 16. V předchozí části 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 Aan — an+i — an primitivní posloupnost AAn — an neurčitý součet E an — An + C 3 konečný součet ^2 an — Aj+\ — Ai n—i oo j řada ^2 an — lim E an n—i J-5"00 n—i funkce / : M ->• M derivace f (x) — lim /(a-+fe)~/(3-) primitivní funkce F'(x) — f(x) neurčitý integrál J f (x) dx — F(x) + C b určitý integrál / f (x) dx — F(b) — F(a) a oo b nevlastní integrál J f (x) dx — lim J f (x) dx b^co „ 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. 5.1. Diferenční počty. Diskrétní verzí derivace funkce je diference posloupnosti. Diference posloupnosti (a„) je posloupnost (Aa„) definovaná vztahem Aan — an+i — an- Ne každá funkce má derivaci, zato každá posloupnost má diferenci. Pojem iterované diference je snad jasný. Definici a obecné vlastnosti operátoru A shrnujeme v následující tabulce:11 Aa„ — an+i — an A2an — A(Aa„) — Aan+i - Aan A(an + bn) — Aan + Abn A(c-an) — c-Acin A(an ■ bn) — an ■ Abn + Aan ■ bn+i J K ' h^O h f"{x) = (f(x)Y = lim f'(*+»-f'M (/ + «fe = «1-7-«l-7 = «1-T' U 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ř. (17), které se bez nápovědy řeší dost těžko. Úloha 42. Určete součet E fe=i Primitivní posloupnost k posloupnosti (n2) z hlavy neznáme. Pomocí n- — n a n- — n{n — 1) se však n2 dá vyjádřit takto: n2 — (n2 — n) + n — n- + n-. Podle (20) tedy určíme primitivní posloupnost 1 2 Podle věty 11 už jenom dosadíme meze (n+l)^ (n+1)2 lä l2 Eo nä n-n2 = T + T+C. 3 2 3 2 fe=i _ {n + l)w(n — 1) (n + l)n _ n(n + l)(2n+l) 3 + 2 6 Na závěr ještě jeden problém, o němž jsme se začali bavit v úloze 13: Úloha 43. Uvažujte mapu tvořenou výhradně přímkami. Určete kolik nejvýše oblastí může být vymezeno právě n přímkami. Jediná přímka vymezuje právě dvě oblasti; dvě přímky vymezí nejvýše 4 oblasti (právě když jsou různoběžné); tři přímky vymezí nejvýše 7 oblastí (právě když jsou každé dvě navzájem různoběžné). Obecně, přidáme-li k n přímkám na mapě jednu další, můžeme dostat nejvýše n + 1 nových oblastí. Odpovídající posloupnost je (a„) — (2,4, 7,...), přičemž On+i = an + (n+ 1). Otázka zní, jak odtud vyjádřit an? Definující rovnost můžeme přepsat Aa„ — n + 1, MA2MP.SMR2 21 odkud podle (20) plyne n- a„ Y+n + C. Protože a\ — 2, musí být C — 1. Celkem po úpravě dostáváme ,2 , „ , 2 n - a„ □ 5.3. Diferenční rovnice. Řešení úlohy 43 můžeme interpretovat jako řešení jednoduché diferenční rovnice prvního řádu (Aan — n + 1) s počáteční podmínkou (ai = 2). Obecné diferenční rovnice prvního, druhého, .. . řádu jsou rovnice tvaru Aan — tp(n, an) A2an = ip(n, an, Aan) f'(x)= 0 neumíte vyjádřit primitivní posloupnost k posloupnosti a>n — v uzavřeném tvaru. 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 1 1 1 -1 A- = n n + 1 n n(n + 1)' takže aspoň můžeme alternativně vyřešit úlohu 24(b)... Kvadratickou rovnici (22) lze ekvivalentně přepsat takto: 1 1 - q (25) i - q q Důvodem tohoto přepisu je, že tady rozpoznáváme definici zlatého řezu.13 Ten se — stejně jako Fibonacciho posloupnost — objevuje v mnoha matematických zákoutích, pročež si o něm snad ještě něco řekneme... 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 47. V takovém případě těžiště úlohy tkví právě v nalezení nějakého jednoho partikulárního řešení (podobně jako tomu bylo v části 1 o lineárních diofantických rovnicích). 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 50. Vzpomeňte na některé metody řešení lineárních diferenciálních rovnic a zkuste je aplikovat k dořešení např. diferenční rovnice (24). Mnoho a mnoho diferenčních rovnic, resp. rekurentních vztahů můžeme potkat téměř na každém rohu. Vzpomeňte, že např. několikrát zmiňovaná Fibonacciho posloupnost odpovídá neomezenému růstu idealizované nesmrtelné králičí populace. Rekurzivní úvahy se přirozeně objevují také u řady kombinatorických úloh; zde je několik ukázek [L]: Úloha 51. 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 52. 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í? (a) Aby žádná věž nestála na hlavní úhlopříčce. (b) Aby rozmístění věží bylo symetrické podle hlavní úhlopříčky. (c) Aby rozmístění věží bylo symetrické podle středu šachovnice. (d) Apod. ^3http://en.wikipedia.org/wiki/Golden_ratio 24 podzim 2013 * * * 6. Zatím nezařazeno Dláždění roviny pravidelnými mnohoúhelníky. Každý umí vydláždit rovinu jenom pravidelnými trojúhelníky, nebo čtyřúhelníky, nebo šestiúhelníky. 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. Kupodivu jich však není až tak mnoho... Úloha 53. Kolika způsoby je možné vydláždit rovinu pravidelnými mnohoúhelníky (různých typů), které mají shodné strany a potkávají se ve vrcholech? Při rozboru této úlohy narazíme mimo jiné na několik diofantických rovnic typu: 1 1 —I---1----=w, x y kde w je nějaké racionální číslo... (26) Symetrie periodických vzorů. U periodických dláždění roviny pozorujeme různé typy symetrií. Pokud rozdělíme taková dláždění podle toho, zda mají nebo nemají stejné symetrie, pak z jistého důvodu těchto skupin určitě nebude víc než 17... Jednodušší verze tohoto problému se týká symetrií tzv. frízových vzorů, což jsou vzory, které se periodicky opakují jenom v jednom směru, viz obr. 11. Úloha 54. Dokažte, že z hlediska symetrií existuje právě 7 typů frízových vzorů. AXXXÁAÁ, ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^> Obrázek 11. * * * Kvadratura mnohoúhelníku. Úloha 55. Rozdělte kříž na obr. 12 (tvořený pěti shodnými čtverci) dvěma řezy na několik částí tak, abyste z nich složili jeden čtverec. [Ko] MA2MP.SMR2 25 Obrázek 12. Konstrukce čtverce se stejným obsahem jako má daný rovinný útvar je tzv. problém kvadratury. Tady bychom si měli připomenout, že s eukleidovským pravítkem, kružítkem, příp. nůžkami umíme kvadraturovat libovolný mnohoúhelník... Po krátkém experimentování a následném rozvažování můžeme prohlásit, že dokonale rozumíme následujícímu tvrzení: Věta 12 (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í týkajících se rovnosti obsahů, jako např. Pythagorovy věty. Na obr. 13 je představena jedna z mnoha možností kvadratury obecného trojúhelníku. Obrázek 13. 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 Archimedova kvadratura parabolické úseče v úloze 30 nebo kvadratura Hippokratových půlměsíců v úloze následující. Úloha 56 (Hippokratovy půlměsíce). Dokažte, že nad libovolným pravoúhlým trojúhelníkem platí, že obsah půlměsíců vyznačených na obr. H je stejný jako obsah trojúhelníku. Kvadratura kruhu a další slavné problémy starověku. S kruhem je to samozřejmě jiné — kvadratura kruhu je jeden z nejslavnějších problémů starověku. Úloha 57 (Kvadratura kruhu). Zdůvodněte, proč není možné kvadraturovat kruh eukleidovským pravítkem a kružítkem. 26 podzim 2013 Obrázek 14. Do této skupiny problémů patří ještě 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) a s ním související problém konstrukce pravidelného n-úhelníku... Zdvojení krychle je obecně nemožné a pokud rozumíme úloze 57, pak zdůvodnění je nabíledni. Zbylé dva problémy jsou poněkud subtilnější, protože někdy řešitelné jsou a jindy ne! S problémem trisekce úhlu souvisí následující úloha: Úloha 58. Libor narýsoval kružnici se středem S a body A, B, C, D, viz obr. 15. Zjistil, že úsečky SC a BD jsou stejně dlouhé. V jakém poměru jsou velikosti úhlů ASC a ABC? [MO, 60. ročník] Konstrukce pravidelného n-úhelníku evidentně souvisí s problémem trisekce úhlu, akorát jsme podstatně redukovali množinu ú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ší. Obecná charakterizace sestrojitelných mnohoúhelníků je známá teprve z přelomu 18. a 19. století: Věta 13 (Gaussova-Wantzelova). 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 Ferma-tových prvočísel. Fermatovo prvočíslo je prvočíslo tvaru Fk — 22 + 1. K dnešnímu dni14 je známo pouze pět Fermatových prvočísel: F0 — 3, Fi — 5, F2 — 17, F3 — 257 a F4 — 65537. Úloha sestrojitelnosti pravidelného n-úhelníku tedy není řešitelná pro n — 7,9,11,13,14,18,19, 21,... Úloha 59. Sestrojte co nejvíc různých pravidelných mnohoúhelníků. * * * 22. listopadu 2013 ma2mp.smr2 27 Objemy hranolů a jehlanů. Trojrozměrná analogie věty 12 pro mnohostěny a jejich objemy obecně neplatí! Pro rovnoběžnostěny sice taková analogie platí, ale třeba pro jehlany ne. Obecná charakterizace takových dvojic těles, pro která to platí, je netriviální a tudíž potenciálně zajímavá! Tento problém najdeme na výše zmiňovaném Hilbertově seznamu pod číslem 3... Úloha 60. Dokažte, že rovnoběžnostěny se stejnou základnou a stejnou výškou mají stejný objem. [E, XI.30] Obrázek 16. Problém s analogickým tvrzením pro jehlany spočívá v tom, že obecně nelze dokázat bez nějaké formy infinitezimálních úvah, viz [E, XII.5]. Na úvod můžeme vyřešit následující přípravnou úlohu: Úloha 61. V trojbokém jehlanu ABCD jsou body E, F, G, H, K a L po řadě středy hran AB, BC, AC, AD, B D a CD, viz obr. 17. Dokažte, že hranoly EBFGHK a GFCHKL mají stejný objem. [E, XII.3] D Obrázek 17. Objem koule. Odpověď na otázku, jak by se měl vyučovat objem koule, najdeme u Archiméda: Věta 14 (Archimedova). Objem koule je roven dvěma třetinám objemu opsaného válce. Po několika přípravných a velice zajímavých úvahách se v důkaze tohoto tvrzení nakonec objevuje následující jednoduchá planimetrická úloha: 28 podzim 2013 Úloha 62. Na obrázku obr. 18 dělí úsečka AC fialový obdélník na dva stejné čtverce, bod S je libovolný bod na AC a bod Q, resp. O označuje průsečík S M s modrou úhlopříčkou, resp. s červenou kružnicí. Dokažte, že platí \MS\2 ■ \SA\ = (\OS\2 + \QS\2) ■ \CA\. M Obrázek 18. * * * Další diofantické rovnice. Úloha 63. Dokažte, že libovolná diofantická rovnice typu (26) má jen konečně mnoho kladných celočíselných řešení. Úloha 64 (Pythagorejské trojice). Najděte všechna kladná celočíselná řešení rovnice x2+y2 — z2. Upíná charakterizace všech řešení je následující: Trojice x, y, z je řešením diofantické rovnice právě tehdy, když x — 2mn, y — n2 — m2, z — n2 + m2, pro nějaká přirozená čísla m < n. Navíc čísla x,y,z jsou navzájem nesoudělná právě tehdy, když to, n jsou nesoudělná a mají opačnou paritu... □ Varianta předchozí úlohy: Úloha 65. Dokažte, že rovnice x2 + y2 — zn má kladné celočíselné řešení pro libovolné n — 1,2,3,... [L] Podobně vyhlížející, mnohem těžší a taky nejslavnější ze všech diofantických rovnic:15 Úloha Jí 66 (Fermatova). Dokažte, že pro n > 2 nemá rovnice xn + yn — zn řešení v oboru přirozených čísel. * * * 'http://cs .wikipedia.org/wiki/Velky,C3y,Al_Fermatova_vy,C4y,9Bta ma2mp.smr2 29 Úlohy s pohybem. Úloha 67. Dva turisté strávili čas mezi třetí a devátou hodinou odpolední na procházce. Nejprve šli kus cesty po rovině, pak do kopce. Na vrcholu kopce se obrátili a po stejné cestě se vrátili zpět. Po rovině šli rychlostí čtyři míle za hodinu, do kopce tři míle za hodinu, z kopce šest mil za hodinu. Určete vzdálenost, kterou urazili. Dále určete s přesností plus minus půl hodiny čas, kdy stanuli na vrcholu kopce. [C] Všimněte si, že hodnoty v zadání nemohou být libovolné, aby se úloha dala dořešit... Úloha 68. Franta si vyrazil na výlet do Olomouce. Z hlavního nádraží se vydal pěšky do města. Po cestě si všiml, že v protisměru jej míjí tramvaje s intervalem 10 min 4-8 s a tramvaje jedoucí ve směru chůze jej míjí s intervalem 13 min 30 s. Později Franta zjistil, že tramvaje vyjížděly v obou směrech ve stejných intervalech a pohybovaly se stejnými, a to konstantními, rychlostmi. Vzhledem k tomu, že se Franta také celou dobu pohyboval konstantní rychlostí, snadno spočítal interval, v jakém tramvaje vyjížděly. Zjistěte, co Frantovi vyšlo. [V] * * * Poctivci, padouši a další. Poctivci mluví vždy pravdu, padouši vždy lžou, ... Úloha 69. Na ostrově poctivců a padouchů se ocitnete na rozcestí — jedna cesta vede ke zdroji pitné vody, druhá vede do záhuby. Po chvíli se objeví dva domorodci. Zjistěte pomocí jediné otázky, která cesta je ta pravá. [Smi] Taky se může stát, že domorodci sice rozumí naší řeči, ale odpovídají tak, že nerozumíme my. Vůbec nejhorší je, když jsou mezi původním obyvatelstvem také tzv. normální lidé, kteří mohou odpovídat jakkoli bez ohledu na to, zda mluví pravdu nebo ne......... * * * Další nezařazené úlohy. Úloha 70. Dva kolegové, A a B, hledají celá čísla, x a y, obě větší než 1. A zná součin x ■ y a ví, že B zná součet x + y, B zná součet a ví, že A zná součin. Podle předchozích informací a následujícího rozhovoru, určete čísla x a y. A: „Nevím, která to jsou čísla." B: „ To jsem věděl. " A: „ Tak já už vím!" B: „ Tak já už taky!" Úloha 71 (Archimedova). Dvě menší kružnice se navzájem dotýkají zvenku a každá z nich se dotýká zevnitř třetí, větší kružnice, přičemž středy všech tří kružnic leží na jedné přímce, viz obr. 19. Známe délku tětivy velké kružnice, která prochází společným bodem dvou menších kružnic. Určete obsah plochy, která je ohraničena těmito třemi kružnicemi. [Po] Úloha 72. Napište několik čísel tak, že každou z deseti číslic použijete právě jednou a součet těchto čísel bude právě 100. [Po] 30 podzim 2013 Obrázek 19. Reference [A] B. Artmann, Euclid: The Creation of Mathematics, Springer, 1999 [C] L. Carroll, Zamotaný příběh, Dokořán, 2009 [D] H. Dôrrie, 100 Great Problems of Elementary Mathematics, Dover, 1965 [E] Eukleidés, Základy, Alexandrie, —300 [G] D. Gleicli, Finite Calculus: A Tutorial for Solving Nasty Sums, 2005 [H] R. Hartsliorne, Teaching geometry according to Euclid, AMS, 2000 [HKS] J. Herman, R. Kučera, J. Simša, Metody řešeni matematických úloh I, MU Brno, 1997 [Ko] S. Kowal, Matematika pro volné chvíle, SNTL, 1975 [Ku] F. Kuřina, Umění vidět v matematice, SPN, 1989 [L] L.C. Larson, Problem-solving through problems, Springer, 1983 [N] R.B. Nelsen, Proofs without words, MAA, 1993 [Pe] J.I. Perelman, Zajímavá geometrie, Mladá fronta, 1954 [Po] G. Pólya, Mathematical Discovery, Wiley, 1981 [Smi] R. Smullyan, Jak se jmenuje tahle knížka?, Mladá fronta, 1986 [Sni2] R. Smullyan, Satan, Cantor a nekonečno, Mladá fronta, 2008 [Stí] I. Stewart, Jak rozkrájet dort a další matematické záhady, Dokořán, 2009 [St2] I. Stewart, Professor Stewart's Cabinet of Mathematical Curiosities, Perseus Books, 2009 [F] Feature Column, Monthly essays on mathematical topics, AMS (http://www.ams.org/samplings/feature-column/fc-current.cgi) [MKS] Matematický korespondenční seminář (http://mks.mff.cuni.cz/) [MO] Matematická olympiáda (http://math.muni.cz/mo/) [V] Výfuk (http://vyfuk.fykos.cz/) [?] Úlohy z neznámých zdrojů od studentů tohoto kurzu Některé zdroje a další odkazy lze najít na http://is.muni.cz/el/1441/podzim2013/MA2MP_SMR2/op/index.html ma2mp.smr2 31 Seznam obrázků 1 http://www.ams.org/samplings/feature-column/fc-2013-08 6 2 Š. Křehlík 7 3 Š. Křehlík 8 4 http://imgur.com/HDWOT 9 5 http://demonstrations.wolfram.com/ProofWithoutWordsl2NlNChoose2/ 13 6 [N] 13 7 [N] 13 8 [N] 14 9 http://en.wikipedia.org/wiki/The_Quadrature_of_the_Parabola 15 10 http://en.wikipedia.org/wiki/Harmonic_number 16 11 www.oswego.edu/~baloglou/103/crystal.html 24 12 [Ko] 25 13 K. Nedvědová 25 14 http://mathworld.wolfram.com/Lune.html 26 15 [MO] 26 16 http://alephO.clarku.edu/~djoyce/java/elements/bookXI/propXI30.html 27 17 http://alephO.clarku.edu/~dj oyce/j ava/elements/bookXII/propXII3.html 27 18 http://www.ams.org/samplings/feature-column/fcarc-archimedes4 28 19 30 Achilles, 14 Archimedes, 15, 26, 27, 29 Bezout, E., 2 Bolyai, F., 25 Diofantos, 1-6, 28 Dirichlet, P.G.L., 6 Doppler, Ch., 29 Eukleides, 2, 26, 27 Euler, L., 4, 5, 8 Fermat, P., 4, 11, 26, 28 Fibonacci, 10, 12, 18, 20-23 Frobenius, F.G., 5 Gauss, C.F., 26 Gerwien, P., 25 Hilbert, D., 1, 27 Hippokrates, 25 Lagrange, J.-L., 4 Leibniz, G.W., 15, 17, 19 Newton, I., 15, 19 Pythagoras, 25, 28 Riemann, B., 17 Wallace, W., 25 Wantzel, P.L., 26