Diamantová suma - řešení příkladů 1.kola 1. Dokažte, že pro každé přirozené číslo n platí
√1 1.n
+
√1 2.n
+ ··· +
√1 n.n
< 2.
Postupujeme matematickou indukcí. Levou stranu nerovnosti označme sn . Nejmenší n, pro než má smysl něco dokazovat, je n = 1 a pro toto n tvrzení očividně platí. Nechť tedy naše nerovnost platí pro n = k, dokazujeme ji pro n = k + 1. Nejprve musíme nahlédnout, že ! 1 1 1 1 p sk+1 = +p + ··· + p +p 1.(k + 1) 2.(k + 1) k.(k + 1) (k + 1).(k + 1) r k 1 sk+1 = sk + k+1 k+1 √ Vzhledem k tomu, že pro každé x ≤ 1 platí 1 − x ≤ 1 − x2 (stačí tuto nerovnost umocnit na druhou), můžeme provést úpravu r r k 1 1 1 1 1 sk+1 = sk + = sk 1 − + <2 1− + =2 k+1 k+1 k+1 k+1 2(k + 1) k+1 Tím je důkaz hotov. 2. Na stole tvaru čtverce 1 × 1 metr je umístěno několik (kruhových) koláčků. Koláčky se mohou překrývat, ale nesmí přesahovat okraj stolu. Celkový obvod všech koláčků je 10 metrů. Ukažte, že je možné jedním řezem (tj. jednou přímkou) protnout alespoň 4 koláčky. Součet průměrů všech koláčků je
10 π
metrů, tedy více než tři metry. Zvolme jednu hranu
stolu a všechny koláčky na ni (kolmo) promítněme. Koláček o průměru d se zjevně promítne na úsečku o délce d. Celkem tedy na hraně stolu dlouhé jeden metr máme několik úseček, jejichž celková délka je více než tři metry, tudíž nějakým bodem musí procházet alespoň čtyři úsečky (Dirichletův princip). Kolmice k hraně stolu vztyčená v tomto bodě tedy protíná alespoň čtyři koláčky a tím je důkaz hotov. 3. Je číslo 1 +
2 10
+
3 100
+
4 1000
+
5 10000
+ · · · racionální nebo iracionální?
Snadno ukážeme, že zadaná řada absolutně konverguje, tudíž můžeme libovolně zaměňovat pořadí jednotlivých členů součtu. Řadu si tedy rozdělíme na nekonečně mnoho dílčích řad: 1+
1 1 1 1 + + + + ··· 10 100 1000 10000 1 1 1 1 + + + + ··· 10 100 1000 10000 1 1 1 + + + ··· 100 1000 10000 atd.
1 10
· 10 , 9
a tak dále. Tato čísla opět tvoří geometerickou řadu, jejíž součet je
100 , 81
Všechny tyto řady jsou geometrické. Součet první řady je třetí řady
1 100
·
10 9
1 1 1− 10
=
10 , 9
druhé řady pak
což je racionální číslo. 4. Král se chce rozhodnout, kterou ze 100 dívek si vezme za ženu. Pochopitelně chce tu nejhezčí, jenže ony k němu chodí postupně a král musí nápadnici hned říct, zda ji chce nebo ne. Král zvolil následující strategii: odmítne prvních padesát a z dalších padesáti si vybere první, která bude hezčí než všechny předchozí (nebo si, pokud takto odmítne dalších 49, vybere tu poslední). (a) Jaká je pravděpodobnost, že si král vybere tu nejošklivější? (b) Jaká je pravděpodobnost, že si král vybere tu nejhezčí? (a) Král si bude muset vzít nejošklivější princeznu jedině tehdy, když nejkrásnější bude mezi prvními padesáti a ta nejošklivější půjde právě jako poslední. Pravděpodobnost, že nejošklivější půjde poslední, je
1 . 100
že bude mezi prvními padesáti, je
Na nejhezčí pak zbývá 99 míst, a tedy pravděpodobnost, 50 . 99
Výsledná pravděpodobsnot je pak
1 100
·
50 99
=
1 . 198
(b) Pravděpodobnost, že si král vybere nejhezčí princeznu, je součtem pravděpodobností, že si vybere tu nejhezčí za předpokladu, že půjde 1., 2., 3., . . . , 100., násobených
1 100
(což
je pro každé k pravděpodobnost, že nejhezčí princezna půjde jako k-tá). Pravděpodobnost, že si ji král vybere, když jde 1., 2., 3., . . . , 50., je nula. Aby si ji vybral, pokud půjde jako k-tá (kde 50 < k ≤ 100), musí nejkrásnější z těch, co jdou před ní, jít v první padesátce. Tedy musí být na některém z 50 míst z celkových k − 1, pravděpodobnost je
50 . k−1
Celková
pravděpodobnost je rovna 100 99 100 X 50 1 X 1 1 X1 1 · = · = · 100 k − 1 2 k=51 k − 1 2 k=50 k k=51
Tento výsledek již nelze nijak hezky upravit, nicméně jeho hodnotu lze docela přesně odhad100 R 1 . nout integrálem 21 · dx = 12 · ln2 = 0.35. x 50
5. Jsou dány různoběžné přímky p, q, které se protínají mimo nákresnu v bodě A. Dále je dán bod B, který na těchto přímkách neleží. Sestojte střed úsečky AB. Nejprve je třeba najít přímku AB. Sestrojíme libovolný trojúhelník BP Q, kde P ∈ p a Q ∈ q. Dále sestrojíme libovolný jiný trojúhelník B 0 P 0 Q0 který má s původním trojúhelníkem rovnoběžné odpovídající si strany, přičemž opět P 0 ∈ p a Q0 ∈ q. Tyto trojúhelníky jsou stejnolehlé a spojnice odpovídajících si vrcholů musí procházet středem stejnolehlosti, což je bod A. Tedy A ∈↔ BB 0 . Nyní zvolme libovolně bod C ∈ p a přímku r, která je rovnoběžná s přímkou AB. Označme D ∈ r ∩ BC a E ∈ r ∩ p. Trojúhelníky CBA a CDE jsou opět stejnolehlé, přičemž středem
stejnolehlosti je bod C. Zobrazíme-li teď bod S 0 jako střed úsečky DE v této stejnolehlosti, dostaneme na úsečce AB hledaný střed S. 6. Pro jaká a, c ∈ R má rovnice x3 + ax2 + 2008x + c = 0 tři různá celočíselná řešení, z nichž každé dává jiný zbytek po dělení třemi? Sporem ukážeme, že taková a, c neexistují. Nechť má tedy polynom 3 celočíselné kořeny x1 , x2 a x3 . Pak x3 + ax2 + 2008x + c = (x − x1 )(x − x2 )(x − x3 ) = = x3 − (x1 + x2 + x3 )x2 + (x1 x2 + x2 x3 + x1 x3 ) − x1 x2 x3 BÚNO položme x1 = 3i, x2 = 3j +1 a x3 = 3k+2, kde i, j, k ∈ Z. Podívejme se na koeficient u lineárního členu: x1 x2 + x2 x3 + x1 x3 = . . . = 3(3ij + i + 3jk + k + 2j + 3ik + 2i) + 2 To však znamená, že 2008 má po dělení třemi zbytek 2, což je evidentně spor. 7. V mytologii lovců lebek z ostrova Borneo lze najít následující představy posmrtného života: po své smrti přijde bojovník do jeskyně, kde v kruhu okolo gigantického ohně sedí 642 démonů. Do rukou jednoho z nich (démona příjemce) složí bojovník lebky všech nepřátel, které získal během svého života. Poté je bojovník uveden do rajské zahrady a v jeskyni probíhá rituál zatracení. Jeden z démonů, který má alespoň 2 lebky, předá po jedné lebce svým dvěma sousedům. Pak totéž učiní jiný démon, který má alespoň 2 lebky, a tak dále. Pokud žádný z démonů nemá 2 lebky, rituál končí a bojovník je unesen z rajské zahrady a svržen do propasti zatracení. (a) Ukažte, že bojovník, který přemůže alespoň 642 nepřátel, nebude zatracen. (b) Co se stane s bojovníkem, který přemůže méně než 642 nepřátel? (a) Pokud bojovník přemohl více než 642 nepřátel, je tvrzení zřejmé (Dirichletův princip). Situace je tedy zajímavá tehdy, pokud bojovník přemohl právě 642 nepřátel. Nejprve si démony očíslujme (v pořadí, v němž sedí v kruhu) čísly 0, 1, . . . , 641 (démona příjemce označíme 0). Nyní můžeme v každém okamžiku spočítat tzv. lebkové číslo: pro každou lebku vezmeme démona, který ji drží, těchto 642 čísel sečteme a spočítáme zbytek po dělení 642. Všimněme si, že lebkové číslo je invariant - tj. nezmění se, když nějaký démon předá oběma svým sousedům po jedné lebce. Na počátku je lebkové číslo rovno 0 a musí tedy být rovno 0 stále. Kdyby rituál někdy skončil, tak by každý z démonů měl přesně jednu lebku. Lebkové číslo by tedy bylo: (0 + 1 + 2 + · · · + 641) mod 642 =
642 · 641 mod 642 = 321 2
To však není možné, takže bojovník zatracen nebude. (b) Bojovník určitě bude zatracen, tj. i kdyby démoni nechtěli, rituál musí skončit. Toto dokážeme sporem. Předpokládejme tedy, že rituál nikdy neskončí. Lebky si označíme: když poprvé putuje nějaká lebka mezi démonem a a démonem b, tak tuto lebku označíme jako ab-lebku. Dále démony požádáme, aby ab-lebku nedostal nikdy jiný démon, než a či b. To na rituálu nic nezmění, pouze si démon a, drže ab-lebku a předávaje ji, musí dát pozor, aby ji předal démonu b a ne druhému svému sousedu (a analogicky musí být opatrný démon b). Toto označení provedeme pro všechny dvojice sousedních démonů. Díky tomu, že se ab-lebka nedostane k jinému démonu než a nebo b, je každá lebka označena maximálně jednou. Protože lebek je méně než dvojic sousedních démonů, tak existuje dvojice sousedních démonů, kteří si žádnou lebku nepředali. Tudíž existuje démon (dokonce dva takoví), kteří lebky předali jen konečněkrát (dokonce ani jednou, tj. nulakrát). Na druhou stranu rituál trvá nekonečně dlouho, takže existuje nějaký démon, který lebky předal nekonečněkrát. Musí tedy existovat dva sousední démoni k, n takoví, že k předal lebky jen konečněkrát, zatímco n nekonečněkrát. To ovšem znamená, že se lebky hromadí u démona k (od n jich dostane nekonečně mnoho, ale jen konečně mnoho z nich vydá), což je spor, protože lebek je konečně mnoho. 8. Zjistěte, zda je číslo 210 + 512 prvočíslem. Zadané číslo lze rozložit, tudíž o prvočíslo se nejedná: 210 + 512 = (25 )2 + (56 )2 = (25 )2 + 2 · 25 · 56 − 2 · 25 · 56 + (56 )2 = = (25 + 56 )2 − 26 · 56 = (25 + 56 )2 − (103 )2 = (25 + 56 + 103 ) · (25 + 56 − 103 ) 9. Rozhodněte, zda pro spojité periodické funkce f, g : R → R musí být také jejich součet f + g periodická funkce. Ukážeme, že součet dvou spojitých periodických funkcí nemusí být periodická funkce. Uvaž√ me například funkce f1 (x) = cos x a f2 (x) = cos (x 2). Obě jsou spojité a periodické (první √ s periodou 2π, druhá s periodou π 2). Jejich součet f = f1 + f2 však periodický není. Tuto skutečnost ukážeme sporem. Předpokládejme, že f je periodická funkce s periodou √ t > 0. Jelikož f (0) = 2, je také f (t) = 2. Pak ale cos t + cos (t 2) = 2, takže zjevně √ cos t = cos (t 2) = 1. Pak ale nutně existují celá kladná čísla k1 a k2 taková, že platí √ t = 2πk1 a t 2 = 2πk2 (pouze pro čísla tvaru x = 2πk, kde k je celé číslo, platí cos x = 1). √ √ Odtud však snadnou úpravou plyne 2 = kk12 , což je spor, protože 2 je iracionální číslo. 10. Na stole je rozložena obdélníková mapa a celá je překryta druhou mapou stejného území v pětkrát větším měřítku. (a) Předpokládejte navíc, že odpovídající si strany jsou rovnoběžné. Dokažte, že vždy existuje
takové místo v daném území, že jeho obraz na větší mapě leží přesně nad obrazem v mapě menší. (b) Platí předchozí tvrzení i bez podmínky rovnoběžnosti stran? (a) V tomto případě se jedná o stejnolehlost obou map. Bodem, který je v nich nad sebou, je jistě jediný samodružný bod této stejnolehlosti, a to její střed. Stačí tedy proložit přímky sobě odpovídajícími rohy velké a malé mapy. V jejich průsečíku se nachází hledaný bod. (b) Tvrzení opět platí. Nyní máme mapy v obecné poloze. Pro lepší představu se na situaci budeme dívat jakoby zpod stolu, na němž máme mapy rozloženy (menší mapa je tedy navrchu). Námi hledaný bod bude jistě (existuje-li) ležet v té části velké mapy, která je překryta mapou menší. Označme tento obdélník na velké mapě V1 . Obraz oblasti V1 vyřezává na malé mapě obdélník M1 , který leží nad nějakým obdélníkem V2 (mimochodem pětkrát menším než V1 ), jehož obraz v malé mapě označme M2 , . . . Takto můžeme pokračovat libovolně dlouho a postupně budeme dostávat obdélníky V1 , V2 , V3 , V4 , . . . Bod, který hledáme, musí ležet ve všech těchto obdélnících současně. Z toho, že každý další obdélník leží vždy celý uvnitř předchozího obdélníku, a z úplnosti roviny plyne, že průnik těchto obdélníků je neprázdný. Zřejmě také obsahuje právě jeden bod: pokud by v něm totiž ležely dva různé body (které tedy mají nenulovou vzdálenost), snadno bychom našli obdélník Vk , do kterého už by se oba nevešly. Tento jednobodový průnik obdélníků V1 , V2 , V3 , V4 , . . . je tedy tím jediným bodem, který leží v obou mapách nad sebou.
