Úvodem k novému ročníku Rozhledů matematicko-fyzikálních

ÚVODEM Úvodem k novému ročníku Rozhledů matematicko-fyzikálních Otevřeli jste první číslo 84. ročníku Rozhledů matematicko-fyzikálních, jednoho z nejstarších časopisů v naší republice. První ročník časopisu se datuje do roku 1921, kde začal vycházet ještě pod názvem Rozhledy matematicko-přírodovědné . Časopis zpočátku nevycházel samostatně, byl pouze přílohou Časopisu pro pěstování matematiky a fyziky, časopisu vydávaného Jednotou československých matematiků a fyziků. Název časopisu se pak změnil v roce 1957. Za dobu existence časopisu docházelo ke změnám formátu, počtu stran, počtu čísel vycházejících v jednom roce, někdy první číslo vycházelo k začátku školního roku, někdy k začátku kalendářního roku. V nadcházejícím ročníku Rozhledů matematicko-fyzikálních dochází opět ke třem základním změnám. První, a to dosti zásadní změnou je navýšení počtu stran časopisu. Doposud měl časopis 56 stran, ale máme k dispozici dostatečný počet kvalitních článků, takže od tohoto čísla má již 64 stran. Tím chceme ještě zkvalitnit obsahovou nabídku vesměs pozitivně hodnoceného časopisu. Ke čtenáři se dostane více informací z matematiky, fyziky, informatiky, historie těchto vědních disciplín a více informací o soutěžích v těchto oborech. Slibujeme si od toho nárůst počtu čtenářů, a to hlavně z řad žáků středních škol a jejich učitelů, pro něž je tento časopis převážně určen. Druhou změnou, která má také zvýšit atraktivitu časopisu, je návrat k jedné tradici časopisu. Jde o zařazení interní soutěže, která též podle tradice nese název Naše soutěž . V ní se budou objevovat problémy z matematiky a fyziky, které čtenáři mohou vyřešit a své řešení poslat do redakce. Více o této soutěži najdete na stránce, která je jí přímo věnována. Třetí důležitá změna má vést k zařazení časopisu mezi uznávané recenzované časopisy v matematice, fyzice a informatice. Měníme tedy formu časopisu tak, aby jednotlivé články odpovídaly požadavkům kladeným na odborné články. V našem případě dodáváme ke každému článku na Ročník 84 (2009), číslo 1

1

ÚVODEM

jeho začátek krátkou anotaci v anglickém jazyce a na konec článku literaturu, na kterou je uvnitř článku odkaz. Dále zvyšujeme počet recenzentů každého článku o dalšího recenzenta, který není z redakční rady časopisu. Doufáme, že uvedené změny zpříjemní chvíle strávené při čtení časopisu Rozhledy matematicko-fyzikální, a přispějí tak k jeho popularizaci. To vám přeje redakční rada časopisu a Jednota českých matematiků a fyziků. Za redakční radu Jaroslav Zhouf

∗ ∗ ∗ ∗ ∗ M – POZDRAV PRE ROK 2009 Vyriešte v množine všetkých prvočísiel diofantovskú rovnicu 33x + 29y = 2009. Koľko prvočísiel menších než 2009 má ciferný súčet dve? Stanovte hodnotu výrazu

1 1+ 2

1 1 1 · 1+ · 1+ · ... · 1 + . 3 4 2009

Nech p(n) znamená súčin číslic prirodzeného čísla n. Stanovte súčet p(1) + p(2) + p(3) + · · · + p(2009).

Koľko existuje štvoríc prirodzených čísiel x, y, z, t, pre ktoré platí x < y < z < t a zároveň x · y · z · t + 7 = 2009. Dušan Jedinák

2

Rozhledy matematicko-fyzikální

ROK ASTRONOMIE Galileo, Kepler a letošní Mezinárodní rok astronomie – 2009 Alena Šolcová, Stavební fakulta ČVUT, Praha Abstract. The year 2009 has been proclaimed the International Year of Astronomy. The paper describes the activities taking place both in the Czech Republic and abroad; and it presents related websites.

Vesmír je tvůj — objevuj!

Rok 2009 vyhlásila Mezinárodní astronomická unie (IAU – International Astronomical Union) spolu s OSN a UNESCO Mezinárodním rokem astronomie. Letošní rok byl vybrán proto, že před 400 lety Galileo Galilei použil již dříve objevený přístroj – dalekohled k nočnímu pozorování oblohy. Ve stejný rok 1609 vydal také Johannes Kepler, tehdy žijící v Praze, důležitý spis pro vývoj nebeské mechaniky Astronomia nova, v němž vyslovil dva zákony, které popisují pohyb těles v naší planetární soustavě a jsou dnes známy jako první a druhý Keplerův zákon. Galileovo pozorování a Keplerovy výpočty a odvození zákonů podstatně přispěly na počátku 17. století k našemu porozumění okolnímu světu. Ročník 84 (2009), číslo 1

3

ROK ASTRONOMIE

Slavnostní zahájení Mezinárodního roku astronomie se konalo v Praze ve středu 7. ledna na Staroměstském náměstí v blízkosti orloje. Zahájil jej evropský komisař pro vědu a výzkum Janez Potočnik a předsedkyně IAU Catherine Cesarsky spolu s profesorem Janem Paloušem z Astronomického ústavu AV ČR. Na náměstí byly vystaveny různé druhy dalekohledů a za pražským poledníkem, který je vyznačen trvale v dlažbě náměstí, stál stan, v němž si návštěvníci mohli prohlížet fotografie těles sluneční soustavy i vzdálenějšího vesmíru pořízené Evropskou jižní observatoří (ESO). Bylo to vhodně zvolené místo k takové oslavě pod věžemi Týnského chrámu, kde navždy pod kamenem odpočívá vynikající pozorovatel nebes Tycho Brahe, a v dohledu orloje, který před téměř 600 lety navrhl mistr pražské univerzity Johannes Šindel a zkonstruoval hodinář Mikuláš z Kadaně. Bohatý program je připravován i pro celý rok. Např. v květnu se chystá otevření Keplerova muzea v Praze v Karlově ulici č. 4 nedaleko od Karlova mostu. Poznamenejme, že Johannes Kepler strávil v Praze celých 12 let a vydal zde více než 30 spisů. Na srpen 2009 se připravuje mezinárodní konference Keplerův odkaz v kosmickém věku. Jiná konference připomene padesáté výročí pádu tzv. příbramského meteoritu, prvního meteoritu na světě, jehož dopad na zemi byl pozorován a z něj vypočtena dráha jeho pohybu ve Sluneční soustavě. Do konce března můžete navštívit výstavu Vesmír – dobrodružství objevů v prostoru mezi Národním divadlem a Novou scénou na Národní třídě v Praze. Návštěvníci mohou zdarma procházet vesmírem od našeho Slunce, Měsíce a planet až k objektům vzdáleným miliardy světelných let. Na 48 panelech uvidíte planety, hvězdy, naši Galaxii – Mléčnou dráhu, vzdálené galaxie a mlhoviny na rozměrných snímcích z Hubbleova kosmického teleskopu, družice Chandry a významných pozemních observatoří. Obrazy jsou doplněny stručným výkladem a je velmi působivé, že se s pohledem do vesmíru můžete zamyslet nad verši Jana Nerudy, Jaroslava Seiferta, Otokara Březiny a dalších. Rozhodně si zařaďte tuto vesmírnou procházku do svého diáře. Druhá slavnost k zahájení Mezinárodního roku astronomie se konala 15.–16. ledna 2009 v Paříži. Sešlo se tu přes 800 zájemců, odborníků astronomů, studentů i amatérů. Mezi mnoha odborníky promluvili ke shromážděným prof. Martin Rees z Cambridge, prof. Joselyn Burnell z Oxfordu, objevitelka pulsarů, a prof. R. Wilson, nositel Nobelovy ceny za fyziku, který se věnoval historii objevu reliktního záření, vysvětloval, proč je ve vesmíru tma. Ve 136 zemích, které se připojily k Mezinárodním 4


ROK ASTRONOMIE

roku astronomie, jsou připravovány projekty, jak přiblížit astronomické výsledky veřejnosti v duchu hesla roku Vesmír je tvůj – objevuj (the Universe Yours to Discover). Ve všech těchto zemích jsou ustaveny organizační výbory. Český výbor vede RNDr. Jiří Grygar, CSc. Informace o českém programu najdete na stránkách České astronomické společnosti ([1], [2]) anebo přímo na stránce Mezinárodního roku astronomie ([3]). Jedním z témat je např. konstrukce Galileova dalekohledu a pozorování s ním nebo ochrana temné oblohy. Najdete zde i soutěže pro mladé astronomy. Dalšími projekty se můžete inspirovat na oficiální stránce IYA2009 ([4]). Např. NASA zve učitele a studenty k účasti v soutěži školních tříd o sestavení koláže vybraného snímku z Hubbleova teleskopu nebo k účasti v akci 100 hodin astronomie, která se bude konat v době od 2. do 5. dubna. Před čtyřmi sty lety nám Galileo svým pozorováním otevřel vesmír. Pozoroval krátery na Měsíci, fáze planety Venuše, čtyři měsíce (satelity) Jupitera. Kepler bez počítače vykonal mnoho výpočtů, než odvodil eliptickou dráhu Marsu. České motto Mezinárodního roku astronomie 2009 Kouzlo objevů je pro nás výzvou k následování Galilea a Keplera k pozorování, studiu pozorovaných jevů, hledání vhodných matematických metod k jejich popisu, k radosti z poznání. Literatura [1] http://www.astro.cz [2] http://www.astronomie2009.cz/userfiles/file/download /iya2009 letak TISK.pdf

[3] http://www.astronomie2009.cz [4] http://www.astronomy2009.org/highlights

Ročník 84 (2009), číslo 1

5

MATEMATIKA Lineární funkce a rekurentně zadané posloupnosti Pavel Pražák, FIM UHK, Hradec Králové Abstract. The paper demonstrates a way how to find a formula for the nth term of a sequence that is given recursively. We concentrate only on a special case when the sequence is given by a linear recurrence relations of the first order with constant coefficients. There are given two applications of the derived formula at the end of the paper. Particularly we formulate and solve a problem of mortgage of loans and a problem of Towers of Benares which is also known as a problem of Towers of Hanoi.

Úvod Jeden z prvních poznatků studentů středních škol o posloupnostech je, že posloupnost lze zadat buď předpisem pro n-tý člen posloupnosti nebo rekurentně, viz např. [3]. Významnými příklady rekurentního zadání posloupností jsou definice aritmetické a geometrické posloupnosti. V některých případech je možné zadat posloupnost oběma způsoby. Také tato skutečnost je studentům středních škol demonstrována na příkladech aritmetické posloupnosti a geometrické posloupnosti. Ve sbírce [5, str. 66] je uvedeno několik úloh, které požadují, aby se na základě znalosti rekurentního zadání posloupnosti, případně znalosti konečného počtu počátečních členů posloupnosti, odhadl předpis pro n-tý člen dané posloupnosti; podobné úlohy i s ukázkou možného řešení lze nalézt v učebnici [3, str. 15 a 16]. Více se v současných učebnicích matematiky o možném vztahu vzorce pro n-tý člen posloupnosti a jeho rekurentního zadání nepíše. Rádi bychom se proto v tomto článku věnovali určité třídě úloh, pro kterou lze z rekurentního zadání posloupnosti stanovit předpis pro n-tý člen této posloupnosti. Budeme uvažovat pouze rekurentně zadané posloupnosti v následujícím tvaru: Nechť f je reálná funkce reálné proměnné a (yn )∞ n=1 je posloupnost; je-li dán první člen y1 této posloupnosti a předpis yn+1 = f (yn ), n ∈ N, (1) budeme říkat, že je posloupnost (yn )∞ n=1 zadána rekurentně. Uveďme však, že takto lze charakterizovat pouze některé rekurentně zadané po6


MATEMATIKA

sloupnosti. Např. známé rekurentní zadání Fibonacciho posloupnosti, viz např. [1], uvedené charakteristice nevyhovuje. Příklad 1. Je-li b ∈ R a f : y = x + b, je předpisem (1) určena aritmetická posloupnost s diferencí b, tj. je dáno y1 a platí yn+1 = yn + b, n ∈ N. Příklad 2. Je-li a ∈ R a f : y = a · x, je předpisem (1) určena geometrická posloupnost s kvocientem a, tj. je dáno y1 a platí yn+1 = a · yn , n ∈ N. Funkce, které jsme použili v předchozích dvou příkladech, jsou speciálními případy lineární funkce f : y = ax + b s koeficienty a ∈ R a b ∈ R. U lineární funkce se navíc požaduje, aby a = 0, pak tato funkce není konstantní. Pomocí lineární funkce lze získat rekurentní předpis posloupnosti ve tvaru (2) yn+1 = a · yn + b, kde a ∈ R \ {0} a b ∈ R. Uvažujme dále. Vzorce pro n-tý člen aritmetické i geometrické posloupnosti, tj. pro speciální případy zadání (2), jsou dobře známy, viz např. [3]. Okamžitě se tedy nabízí také otázka, jak vypadá předpis pro n-tý člen posloupnosti, která je zadána rekurentním předpisem (2). Prozatím jsme korektně nezdůvodnili, že rekurentní předpis opravdu určuje posloupnost. Zodpovězme tedy nejdříve otázku, zda posloupnost zadaná rekurentně pomocí vztahu (2) existuje a zda je určena jednoznačně. Je-li předpisem určena právě jedna posloupnost, jsou jednoznačně určeny hodnoty jednotlivých členů této posloupnosti. Těchto členů je nekonečně mnoho, takže použijeme matematickou indukci. Počáteční člen y1 rekurentně zadané posloupnosti (2) je jednoznačně zadán, tedy tvrzení o existenci a jednoznačnosti platí pro n = 1. Předpokládejme dále, že v posloupnosti je jednoznačně určen člen pro n = k, tj. člen yk . Použijeme-li nyní předpis (2), je funkcí f : y = ax + b, kde a ∈ R \ {0} a b ∈ R, jednoznačně určen i člen yk+1 , takže tvrzení o existenci a jednoznačnosti platí i pro n = k + 1. Oba kroky matematické indukce jsou splněny, tedy (2) určuje právě jednu posloupnost a úloha hledat předpis pro její n-tý člen je opodstatněná. Lineární rekurentní rovnice prvního řádu s konstantními koeficienty Dříve než se pustíme do řešení formulované úlohy, podívejme se na rekurentní zadání posloupnosti jiným způsobem. Vztah (2) lze považovat za rovnici, v níž jako neznámá figuruje posloupnost (yn )∞ n=1 , jejíž předpis Ročník 84 (2009), číslo 1

7

MATEMATIKA

pro n-tý člen je třeba nalézt. Popišme tuto situaci podrobněji. Abychom mohli v závěru uvést některé aplikace rekurentních posloupností, je užitečné rozšířit definiční obor posloupnosti. Označme N0 = N ∪ {0} a libovolnou funkci n → yn , kde n ∈ N0 , a yn ∈ R nazývejme posloupnost s počátečním členem y0 . Je-li p ∈ R, pak vztah yn+1 = a · yn + b,

y0 = p, n ∈ N0 ,

(3)

nazýváme lineární rekurentní rovnice prvního řádu s konstantními koeficienty a ∈ R \ {0} a b ∈ R. Prvek p nazýváme počáteční hodnota rekurentní rovnice. Řešením této rovnice je jakákoliv posloupnost s počátečním členem y0 , pro kterou platí (3). Popsanou terminologii budeme používat. Řešení problému Hledejme předpis pro n-tý člen posloupnosti, která řeší lineární rekurentní rovnici (3). Protože y0 je v zápisu (3) dáno, lze použít rekurentní předpis a určit člen y1 , pro který platí y1 = a · y0 + b. Známe-li člen y1 , lze opět pomocí rekurentního vztahu určit člen y2 , pro který získáme y2 = a · y1 + b = a · (a · y0 + b) + b = a2 y0 + b · (a + 1). Člen y2 je tedy známý, takže lze analogickým způsobem určit i člen y3 , pro který y3 = a · y2 + b = a3 · y0 + b · (a2 + a + 1). Na základě uvedených pozorování lze pro n-tý člen posloupnosti, kde n ∈ N0 , navrhnout vztah yn = an y0 + b(an−1 + an−2 + . . . + 1).

(4)

Takový vztah není příliš přehledný, ale zápis lze zkrátit. Všimněme si, že součet v závorce lze zapsat pomocí vztahu pro součet prvních n členů geometrické posloupnosti s prvním členem 1 a kvocientem a, viz např. [3, str. 52]. Získáme tak 1−an 2 n−1 1−a , je-li a = 1, = 1+ a + a + ··· + a n, je-li a = 1. 8


MATEMATIKA

Pomocí tohoto vztahu lze (4) přepsat ve tvaru yn =

an y0 + b · y0 + bn,

1−an 1−a ,

je-li a = 1, je-li a = 1.

(5)

Všimněme si, že pro a = 1 získáme vztah pro n-tý člen aritmetické posloupnosti s počátečním členem y0 . Položíme-li dále b = 0, získáme vztah pro n-tý člen geometrické posloupnosti s počátečním členem y0 . Vztah (4) jsme víceméně uhodli a bude třeba ukázat, že upravená verze tohoto vztahu, tj. (5), je skutečně řešení lineární rekurentní rovnice (3). Dříve než to uděláme, uveďme alespoň dva příklady. Příklad 3. Pro rekurentní posloupnost yn+1 = 3yn + 2, y0 = 1, kde n ∈ N0 , je 1 − 3n = −1 + 2 · 3n . yn = 3n + 2 · 1−3 Příklad 4. Pro rekurentní posloupnost yn+1 = yn + log 2, y0 = 0, kde n ∈ N0 , je yn = 0 + n · log 2 = log 2n . Důkaz Chceme ukázat, že posloupnost (yn )∞ n=0 zadaná předpisem (5) je jediným řešením lineární rekurentní rovnice (3). To, že existuje právě jedna posloupnost, která splňuje rekurentní vztah, jsme ukázali již v úvodu. Soustředíme se tedy pouze na to, že předpisem (5) je skutečně určeno hledané řešení rovnice (3). Důkaz provedeme pro případ a = 1, případ a = 1 je snažší a provádí se analogicky. Jak ukázat, že (5) splňuje rovnici (3)? Stačí, když ukážeme, že pro každé n ∈ N0 je člen yn+1 rovný hodnotě ayn + b. Počítejme tedy. Použijeme-li (5), pak pro každé n ∈ N0 platí 1 − an 1 − an n n+1 +1 = y0 + b a · a · yn + b = a a y0 + b · +b=a 1−a 1−a = an+1 y0 + b ·

a − an+1 + 1 − a 1 − an+1 = an+1 y0 + b · = yn+1 , 1−a 1−a

takže posloupnost splňuje požadovaný rekurentní vztah a jsme hotovi. Ročník 84 (2009), číslo 1

9

MATEMATIKA

Aplikace Rekurentní zadání posloupností lze výhodně využít pro řešení některých problémů. Nejdříve ukážeme jednu aplikaci z finanční matematiky, srv. též [6]. Příklad 5. Banky nebo různé finanční společnosti poskytují půjčky, aby svým klientům umožnily nákup finančně nákladného zboží. Předpokládejme, že hodnota půjčky je D a sjednaná doba, za kterou je třeba půjčku splatit, je T ∈ N jednotkových období. Označíme-li Dt hodnotu půjčky v čase t ∈ {0, 1, 2, . . . , T }, je D0 = D a DT = 0. Nechť úroková míra, za kterou banka půjčku poskytne, je r ∈ (0, 1), tj. např. r = 0,08 znamená 8% úrok, a přepokládejme, že banka si připisuje úroky z dlužné částky Dt vždy na konci každého úrokovacího období. Dále uvažujme, že klient splácí svůj dluh tempem s. Toto tempo je třeba určit. Jako jednotku tempa splátek lze uvažovat např. Kč za měsíc. Na konci časového intervalu t, t + 1 se dlužná částka Dt zmenší o splátku s a zvětší se o připsané úroky r · Dt z dlužné částky Dt . To může být vyjádřeno vztahem Dt+1 = Dt − s + r · Dt , viz též obr. 1.

s

rD(t)

D(t)

t

D(t + 1)

t+1 Obr. 1. Splácení půjčky

Úpravíme-li získaný vztah, obdržíme lineární rekurentní rovnici Dt+1 = (1 + r)Dt − s,

D0 = D, DT = 0.

(6)

Jak uvidíme, koncovou podmínku DT = 0 bude třeba použít pro stanovení hledaného tempa splátek s. Protože (1 + r) = 1, je podle (5) Dt = (1 + r)t · D − s · 10

1 − (1 + r)t 1 − (1 + r)t = (1 + r)t · D + s · . 1 − (1 + r) r Rozhledy matematicko-fyzikální

MATEMATIKA

Použijeme-li koncovou podmínku DT = 0, tj. dosadíme-li do předchozího vztahu t = T , získáme rovnici (1 + r)T · D + s ·

1 − (1 + r)T =0 r

s neznámou hodnotou tempa splátek s. Jejím řešením získáme odpověď na položenou otázku ve tvaru s=r·

(1 + r)T D · (1 + r)T − 1

V další ukázce se seznámíme s problémem, který v roce 1883 formuloval francouzský matematik Edouard Lucas. Použil k tomu vymyšlenou báji, viz [2]. Příklad 6. Pod kupolí největší svatyně ve městě Benares, která představuje střed světa, je umístěna bronzová deska se třemi diamantovými jehlicemi. Při stvoření světa navlékl Bůh na jednu z jehlic 64 disků z čistého zlata. Největší je dolní disk a nejmenší je horní. Průměr disků se rovnoměrně zmenšuje od dolního k hornímu. To je Brahmova věž. Dnem i nocí kněží přemísťují disky z jedné diamantové jehlice na druhou podle zákonů, které Bůh stanovil: (1) je možno přenášet vždy jeden disk, (2) přenesený kroužek lze na jehlici umístit pouze tak, že menší nesmí ležet pod větším. Až kněží přemístí všech 64 disků z jehlice, na kterou je umístil Bůh, na některou jinou jehlici a vytvoří novou věž, nastane konec světa. Kolik přemístění je třeba k vytvoření věže na jiné jehlici? Místo 64 disků předpokládejme zpočátku, že věž má pouze 3 disky. Nejdříve nejmenší disk přemístíme na nejvzdálenější jehlici a disk prostřední velikosti přemístíme na prostřední jehlici. Pak umístíme nejmenší disk na prostřední jehlici. Největší disk přeneseme na nejvzdálenější jehlici. Nyní lze přemístit nejmenší disk na počáteční jehlici a následně prostřední disk na nejvzdálenější jehlici. Přeneseme-li nakonec nejmenší disk na nejvzdálenější jehlici, je úkol splněn. Všimněme si, že řešení spočívalo v tom, že se v určité fázi 2 menší disky ocitly na prostřední jehlici a vytvořily tak menší věž. Toto pozorování nám umožní sestavit rekurentní vztah pro počet přemístění dvou věží disků, které se počtem liší o jeden disk. Označme Tn+1 počet přemístění n+1 disků z první jehlice na poslední. Jak bylo uvedeno v předchozí úvaze, pro přenesení těchto n + 1 disků je Ročník 84 (2009), číslo 1

11

MATEMATIKA

třeba provést toto: nejdříve přenést n menších disků na prostřední jehlici – to je Tn přemístění, pak přenést největší disk na poslední jehlici – to je 1 přemístění a nakonec přenést všechny menší disky z prostření jehlice na jehlici poslední – to je opět Tn přemístění. Mezi počty přemístění tedy platí vztah Tn+1 = Tn + 1 + Tn . Pokud na jehlicích není žádný disk, není třeba provádět žádné přemístění, tj. T0 = 0. Celkem jsme tak získali lineární rekurentní rovnici Tn+1 = 2Tn + 1,

T0 = 0.

Připomeňme, že v posloupnosti nás zajímá člen T64 . Pro řešení odvozené rekurentní rovnice použijeme vztah (5), podle něhož pro každé n ∈ N0 platí 1 − 2n = 2n − 1. Tn = 2n · 0 + 1 · 1−2 To znamená, že T64 = 264 − 1 = 18 446 744 073 709 551 615. Pokud by přemístění jednoho disku trvalo pouze jednu sekundu, pak by přemístění všech 64 disků podle stanovených pravidel z jedné jehlice na druhou trvalo více než 500 miliard let. Vzhledem k tomu, že stáří naší Země je asi 4,6 miliard let, nemusíme se této báje zatím bát. Poznamenejme na závěr, že lze řešit i lineární rekurentní rovnice prvního řádu, které místo konstantních koeficientů a ∈ R \ {0} a b ∈ R obsahují proměnné koeficienty an a bn . Některé z těchto úloh, včetně jejich aplikací, lze nalézt v [4].

Literatura [1] Bečvář, J.: Leonardo Pisánský – Fibonacci, v Matematika ve středověké Evropě, Prometheus, Praha, 2001.

[2] Kowal, S.: Matematika pro volné chvíle, SNTL, Praha, 1986. [3] Odvárko, O.: Matematika pro gymnázia, Posloupnosti a řady, Prometheus, Praha, 1995.

[4] Gavalcová T., Pražák P.: Základy matematiky 2, Gaudeamus, Hradec Králové, 2004.

[5] Petáková, J.: Matematika, příprava k maturitě a k přijímacím zkouškám na vysoké školy, Prometheus, Praha, 1998.

[6] Pražák, P.: Splácení půjčky, Rozhledy matematicko-fyzikální 77 (2000), s. 212–216.

12


MATEMATIKA

Odmocniny z přirozených čísel Jaromír Šimša, PřF MU Brno Abstract. The article deals with the irrationality of square roots of integers. Linear independence of these values over the field of rationals is discussed from an elementary point of view. Finally, a set of five problems with answers and solutions is presented.

√ √ √ Čísla 2, 3, 5 apod. jste poznali již na základní škole. Potřebujeme je zejména při geometrických výpočtech. Tak například čtverec√ o straně √ délky 1 cm má úhlopříčku dlouhou 2 cm. Zapsat přesně číslo 2 v desítkové soustavě je prakticky nemožné, protože jeho zápis √ 2 = 1,414 213 562 373 095 048 801 688 724 . . .

má za desetinnou čárkou nekonečně mnoho nenulových číslic, které se od žádného místa periodicky neopakují. Takovým číslům říkáme iracionální; jejich nevyjádřitelnost“ nám však při praktických užitích mate” matiky tolik nevadí. Pro situace, ve kterých s nimi počítáme (rozměry fyzických objektů, jejich vzdálenosti, časové údaje apod.), totiž vystačíme (při zvolených jednotkách) s přibližnými hodnotami na několik málo platných číslic. Přesto je zajímavé a užitečné o těchto číslech rozvíjet matematickou teorii výpočtů. V ní iracionální čísla (nikoliv pouze hodnoty odmocnin) popisujeme jako ta reálná čísla x, která nelze vyjádřit zlomkem, přesněji zapsat jako podíl x=

a b

celého čísla a a přirozeného čísla b. Zdůrazněme, že takové negativní vymezení má pouze teoretický význam bez možnosti praktického testování. Například na většině obyčejných kalkulaček (vyzkoušejte, máte-li √ nějakou po ruce) se hodnota 2 rovná hodnotě zlomku 665 857 = 1,414 213 562 374 . . . 470 832 √ (podtrženy jsou číslice shodné s číslicemi čísla 2).√Uvedený zlomek patří do (nekonečné) skupiny zlomků, které hodnotu 2 přibližují opravdu Ročník 84 (2009), číslo 1

13

MATEMATIKA

výjimečně dobře. Při takovém hodnocení zlomků přirozeně porovnáváme počet číslic jejich jmenovatele s počtem platných √ číslic výsledku; pro zajímavost uveďme ještě nejlepší přiblížení čísla 2 zlomkem s desetimístným jmenovatelem: 10 812 186 007 = 1,414 213 562 373 095 048 795 . . . 7 645 370 045 Matematikové již ve středověku vymysleli postup, jak takové zlomky efektivně vyhledávat. Nebudeme se ovšem touto otázkou, která měla velký význam při navrhování ozubených soukolí pro mechanismy orlojů, dále v tomto článku zabývat.1) I bez hledání podtržené skupiny číslic je hned jasné, proč nemůže platit (přesná) rovnost 10 812 186 007 √ = 2. 7 645 370 045 Z ní bychom totiž po umocnění a odstranění zlomku dostali rovnost dvou přirozených čísel 10 812 186 0072 = 2 · 7 645 370 0452 , která zřejmě neplatí. Na její levé straně totiž stojí liché číslo, zatímco číslo na pravé straně je sudé. Možná jste si při této √ úvaze vzpomněli, že nějak podobně jste ve škole kdysi dokazovali, že číslo 2 je skutečně iracionální. Zobecníme to následujícím základním poznatkem, který bychom si měli zapamatovat. √ √ √ √ √ Tvrzení 1 Kromě hodnot 1, 4, 9,√ 16, 25 atd., což jsou celá čísla, pro ostatní přirozená n jsou hodnoty n iracionální čísla. Jinak řečeno: odmocnina z přirozeného čísla je buď číslo přirozené, nebo iracionální.2) Abychom uvedené tvrzení dokázali, předpokládejme, že pro nějaké přirozené číslo n existují celá čísla a a b splňující rovnost √ 1) 2)

n=

a . b

(1)

Zvídavý čtenář nalezne poučení v brožuře z řady kdysi vydávané Školy mladých matematiků P. Vít: Řetězové zlomky, Mladá fronta, Praha 1982. Přirozenými čísly míníme pouze celá kladná čísla, tedy nikoliv číslo 0.

14


MATEMATIKA

√ Protože hodnota n je kladná, mají čísla a a b stejné znaménko, takže můžeme předpokládat, že jsou to dvě kladná čísla. Naším √ cílem je ukázat, že zlomek ab lze zkrátit na celé číslo, které se pak rovná n, takže samo n je rovno jednomu z čísel 1, 4, 9, 25, . . . . Můžeme jistě od začátku předpokládat, že zlomek v rovnosti (1) je v základním tvaru, a vysvětlit jen, proč potom b = 1. K tomu rovnost (1) upravíme do tvaru rovnosti dvou přirozených čísel (2) n · b2 = a2 a provedeme tuto úvahu: kdyby se číslo b nerovnalo 1, bylo by dělitelné některým prvočíslem p, takže číslo na levé straně (2) by bylo dělitelné číslem p2 . Pak by i číslo a2 z pravé strany (2) bylo dělitelné číslem p2 , takže samo číslo a by bylo dělitelné číslem p.3) To by ovšem znamenalo, že zlomek v rovnosti (1) je možné ještě zkrátit prvočíslem p. My jsme však už od začátku vzali zlomek v základním tvaru. Musí tedy platit b = 1 a důkaz je hotov. Nyní přejdeme k některým rovnostem, ve kterých vystupují iracionální hodnoty odmocnin z přirozených čísel. Příkladem je rovnost √ √ √ 12 + 27 − 75 = 0. Jistě chápete, proč numerický test na kalkulačce nám v takových případech nezaručí jistotu absolutně přesné rovnosti. Místo toho můžeme zadaný výraz snadno upravit částečným odmocněním √ √ √ √ √ √ 12 + 27 − 75 = 2 3 + 3 3 − 5 3 = 0 a rovnost tím máme ověřenou. Podobné rovnosti můžete sestavovat jako na běžícím pásu, vzniká ovšem zajímavá otázka, zda některá vzhledově ” podobná“ rovnost nemá hlouběji skrytou příčinu, takže ji nelze dokázat uvedeným jednoduchým postupem. Zabývejme se tímto problémem ve zbytku příspěvku. Než popíšeme obecný případ, vyřešme jeden konkrétní úkol: určíme, pro která celá čísla a, b, c je splněna rovnost √ √ a 2 + b 6 + c = 0. (3) 3)

Toto klíčové místo důkazu vysvětlíme podrobněji: kdyby prvočíslo p nevystupovalo v rozkladu na prvočinitele čísla a, nevystupovalo by ani v rozkladu na prvočinitele čísla a2 , který dostaneme tak, že za sebou dvakrát napíšeme stejný rozklad čísla a. Pomocí rozkladů na prvočinitele lze zdůvodnit rovněž i kratší důkaz celého tvrzení plynoucí z rovnosti (2): protože b2 | a2 , platí i b | a, takže zlomek v (1) je roven celému číslu.


15

MATEMATIKA

Je tomu tak pouze v triviálním případě a = b = c = 0? Zkoumanou rovnost upravíme nejprve tak, že osamostatníme jednu z odmocnin na jedné straně rovnice a pak se jí zbavíme umocněním: √ √ √ a 2 = −c − b 6 =⇒ 2a2 = c2 + 2bc 6 + 6b2 . √ Nyní už můžeme uplatnit, co známe: musí být 2bc = 0, jinak by číslo 6 šlo zapsat ve tvaru √ 2a2 − c2 − 6b2 , 6= 2bc takže by bylo racionální. Proto platí rovnost 2bc = 0, jež znamená, že b = 0 nebo √ c = 0. V případě b = 0 by původní rovnost √ (3) přešla do tvaru a 2 + c = 0, a tak by bylo a = c = 0, neboť 2 je iracionální. √ √ V případě c = 0 bychom měli a 2 + b 6 = 0, neboli 2a2 = 6b2 , tedy a2 = 3b2 . Kdyby neplatilo a = b = 0, v rozkladu čísla 3b2 na prvočinitele by bylo prvočíslo 3 zastoupeno v lichém počtu, zatímco v čísle a2 v sudém počtu, takže by rovnost a2 = 3b2 platit nemohla. Zjistili jsme, že žádná hluboká“ rovnost (3) s celými čísly a, b, c neexistuje, pouze trivialita ” a = b = c = 0. Máte-li chuť něco vyzkoušet sami, můžete se pokusit předchozí postup zobecnit na hledání rovností s větším počtem odmocnin, jako je například rovnost √ √ √ a 2+b 3+c 6+d=0 s neznámými celými čísly a, b, c, d. Zjistíte patrně, že upravit předchozí postup je velmi nesnadné a pro rovnosti s ještě větším počtem odmocnin žádné přímočaré zobecnění neexistuje. Budete však dobře připraveni ke čtení toho, co bude následovat. Předpokládejme, že pro nějaká přirozená čísla n1 , n2 , . . . , nk a celá čísla a1 , a2 , . . . , ak , ak+1 platí rovnost √ √ √ a1 n1 + a2 n2 + · · · + ak nk + ak+1 = 0 (4) a že žádná zjednodušující úprava výrazů (částečné odmocnění některého čísla nebo sečtení členů se stejnou odmocninou) neexistuje. I v takové obecné situaci platí následující výsledek. Tvrzení 2 Předpokládejme, že přirozená čísla n1 , n2 , . . . , nk jsou navzájem různá a žádné z nich nelze ani částečně odmocnit. Pak pro celá čísla a1 , a2 , . . . , ak , ak+1 platí rovnost (4) jedině v případě, kdy a1 = a2 = . . . = ak = ak+1 = 0. 16


MATEMATIKA

Poznamenejme, že žádný jednoduchý důkaz uvedeného tvrzení patrně není znám. Jeho platnost vyplývá ze složité tzv. Kummerovy teorie popisující Galoisovy grupy rozšíření číselných těles.4) Její výklad bohužel v žádné elementárnější literatuře patrně nenajdete. Místo toho vám teď nabízíme k samostatné práci několik zajímavých úloh o odmocninách, které lze řešit bez složitých teorií. Jejich řešení naleznete na str. 64. 1. Najděte všechny dvojice přirozených čísel a, b, pro něž platí √ √ b a − 3 a − 4b + 12 = 0. √ √ √ √ 2. Jsou-li a, b, a + b tři přirozená čísla, pak i čísla a a b jsou přirozená. Dokažte. 3. Najděte všechny trojice celých čísel a, b, c, pro něž √ a+b 5 √ a+c 5 je racionální číslo. 4. Určete všechny dvojice (a, b) přirozených čísel, pro něž platí √ √ a + 5 b = b + 5 a. (MO 55, C-I-1) 5∗ . Dokažte, že pro každé přirozené číslo n a) číslo (7 + b) číslo

√ n √ 48) + (7 − 48)n je celé a pro liché n je dělitelné 14,

√ √ √ √ n n 3+ 2+ 3 − 2 je iracionální.

Literatura [1] Flannery, D.: The Square Root of 2, A Dialogue Concening a Number and a Sequence, Copernicus Books, Springer Science + Business Media, in Association with Praxis Publishing, Ltd., New York, 2006. [2] Rychlík, K.: Úvod do elementární číselné theorie, JČMF, Praha, 1950. 4)

Francouz Evariste Galois (1811–1832) a Němec Ernst Kummer (1810–1893) patří k zakladatelům algebraické teorie čísel, do které posuzovaná otázka patří. Galois zejména proslul vyřešením otázky, které algebraické rovnice mají kořeny vyjádřitelné ze svých koeficientů pomocí aritmetických operací a operace odmocňování, Kummer například dokázal tzv. velkou Fermatovu větu o rovnici xn + y n = z n pro všechny exponenty n ≤ 100.


17

FYZIKA Zázrak mnoha sluncí na nebi Ivan Větvička, Hvězdárna a planetárium hl. m. Prahy, ČVUT, Praha Abstract. The atmosphere sometimes trifles with light in such a way that anybody who looks at the sky must wonder. Halos are ranked among the most interesting visual spectacles. Moreover, some of them have not been explained yet. It is no wonder as people may have a chance to see them only once in a century. Don’t miss the opportunity, watch the sky!

Sluneční paprsky interagují se zemskou atmosférou – s plyny i s jinými částicemi, kapičkami vody, krystalky ledu či prachem. Mnohé úkazy bereme tak samozřejmě, že o nich (ke své škodě) mnozí lidé ani nepřemýšlejí. Občas si atmosféra se světlem zahraje tak, že přivede v úžas každého, kdo pozvedne oči k obloze. Některé jevy se dodnes nepodařilo vysvětlit. Není divu, vždyť je lidé spatří třeba jedenkrát za století. Mezi nejzajímavější atmosférické úkazy patří halové jevy, vznikající lomem, odrazem a rozkladem světelných paprsků na krystalcích ledu ve výškách 6–10 km nad zemí. Stejné obrazce se mohou vytvořit kolem Slunce i Měsíce. Měsíční haló jsou slabší v důsledku nižší intenzity paprsků. Aby mohly nastat příznivé podmínky pro vznik halových jevů, musejí ledové krystalky na obloze tvořit průsvitnou jednotvárnou vrstvu – mrak cirrostratus. Krystalky ledu mají nejčastěji tvar šesterečných sloupků, pravidelných mnohostěnů vztyčených nad šestiúhelníkovou bází. Plášť tohoto tělesa se nazývá hexagonální prisma. Když sluneční paprsky vstoupí do krystalu skrz jednu ze stěn prismatu a opustí ho objednu plochu dále, odchýlí se o 22◦ a kolem Slunce vznikne jasný kruh tohoto poloměru – malé haló (obr. 1 a obr. 2). Je to nejčastější halový jev. Bednář (1989) odkazuje na výsledky dlouhodobého pozorování v Holandsku, kde se malé haló průměrně objevovalo 200 dnů v roce. Asi desetkrát vzácněji se vyskytuje velké haló, zářící kruh kolem Slunce o poloměru 46◦ . Vzniká lomem světla přes prisma a bázi. Častěji se objevuje světelný sloup nad a pod Sluncem vzniklý odrazem paprsků od vnějších ploch krystalků. Šesterečné krystaly často srůstají do dvojic. Na obloze se to může projevit vznikem horizontálního kruhu, světlého pruhu, který vychází 18


FYZIKA

ze Slunce a obepíná oblohu ve vodorovném směru. Právě na něm září všechna falešná slunce“ včetně parhelií, proto se mu říká také parhe” lický kruh. Na průsečíku s malým halem vznikají vedlejší slunce – parhelie. Kombinace části horizontálního kruhu se světelnými sloupy vytváří efektní kříž. Asi jedenkrát do roka se na horizontálním kruhu objeví paranthelia – vedlejší slunce vzdálená 120◦ od středu slunečního disku a na opačné straně oblohy než Slunce může zářit protislunce, antihelium. Za příznivých podmínek může být halový jev doplněn četnými obloukovitými zářícími obrazci. K malému halu se shora přimyká horní dotykový oblouk, zdola spodní dotykový oblouk. Je-li Slunce dostatečně vysoko nad obzorem, mohou se oblouky spojit. Vzniklý obrazec je k malému halu přivěšen jako sloní uši, ale s rostoucí výškou Slunce nad obzorem se více podobá kružnici a jeho poloměr se blíží malému halu. V prostoru mezi horním dotykovým obloukem malého hala a velkým haló se může vzácně objevit ještě Parryho oblouk a od spodní části malého hala k parheliím mohou mířit Lowitzovy oblouky.

Obr. 1. Vznik malého hala v atmosféře. V mraku chaoticky se vznášejících krystalků se na tvorbě hala podílejí jen některé ledové sloupky. Pro výskyt některých vzácnějších halových jevů je nezbytné, aby většina ledových krystalků v mraku měla přednostní orientaci, a proto se objevují ojediněle (dle www.atoptics.co.uk, upraveno)

Obrazec na obloze začíná být složitý, a to ještě zdaleka není konec nebeského představení. Na velké haló shora a zdola nasedají cirkumzenitální oblouky, ze stran se k němu druží čtyři dotykové oblouky (obr. 3). Uvedený výčet optických úkazů vyčerpává čtenáře, ale nikoli možnosti halových jevů. Unikátní pozorování 1. 11. 1999 v Antarktidě zdokumenRočník 84 (2009), číslo 1

19

FYZIKA

tovalo další obrazce (obr. 4) a počítačové simulace například předpovídají výskyty haló o průměrech 9◦ , 18◦ , 20◦ , 23◦ , 24◦ a 35◦ . Pro jejich vznik je nezbytný výskyt ledových krystalků s dobře vyvinutými pyramidálními plochami.

Obr. 2. Lom světla v ledových krystalcích způsobující malé (r = 22◦ ) a velké haló (r = 46◦ ) (převzato od Příhody a Holovské, 1995)

Obr. 3. Idealizovaný náčrt typických halových jevů. 1 – Slunce, 2 – malé haló (r = 22◦ ), 3 – halový sloup, 4 – horizontální kruh, 4 – část horizontálního kruhu zářící na nebeské klenbě naproti Slunci, 5 – parhelie malého hala, 6 – Lowitzovy oblouky, 7 – stodvacetistupňová slunce, 8 – protislunce, 9 – horní a dolní dotykový oblouk malého hala, 10 – Parryho oblouk, 11 – dotykové obouky velkého hala, 12 – horní cirkumzenitální oblouk velkého hala, 13 – velké haló (r = 46◦ ), 14 – obzor, 15 – nebeská klenba (dle Bednáře (1989), kresba Větvička)

20


FYZIKA

Obr. 4. Náčrt halového jevu z 1. 11. 1999 pozorovaného v Antarktidě ukazuje krásu a složitost halových jevů. Vnější kružnice obepínající obrázek značí obzor, S – skutečné Slunce (dle expedičních poznámek Jarmo Moilanena na http://tea.armadaproject.org/bowman/1.11.1999.html, kresba Větvička)

Halové jevy pozorovatele informují o možných krystalových tvarech, které mohou narůst v cirrostratech. V roce 1981 otiskl časopis Science článek E. Whalleyho se zajímavou úvahou. Autor se zaměřil na Scheinerovo haló, zářivý kruh o poloměru 28◦ obepínající Slunce. Proč ho nenabízejí počítačové simulace? Odpověď může být překvapivá. Podmínky ve vysoké atmosféře se od situace na povrchu Země mohou natolik lišit, že led vykrystalizuje v soustavě krychlové, místo obvyklé šesterečné symetrie. Scheinerovo haló by mohlo vznikat lomem světla při průchodu krystaly kubického ledu ve tvaru osmistěnů (obr. 5).

Obr. 5. Vznik Scheinerova hala průchodem paprsků světla skrz osmistěnné krystaly kubického ledu (dle Whalleyho (1981), upraveno) Ročník 84 (2009), číslo 1

21

FYZIKA

Osmadvacetistupňové haló popsal Christophe Scheiner na základě pozorování z 20. 3. 1629 v Římě (obr. 6). Následovala pozorování v letech 1677, 1726 a 1747, pak přišlo 158 let bez jediného záznamu, aby se Scheinerovo haló objevilo třikrát během patnácti roků: 1905, 1915 a 1920. Od té doby po něm opět není ani vidu. Zvláštní pozornost si zaslouží anonymní pozorování z pařížské Observatoire Royale z 20. 5. 1677. Tehdy se 35◦ od Slunce objevila jasná skvrna, která by mohla být náznakem dotykového oblouku Scheinerova hala. Jedná se o jediné zaznamenané pozorování takového jevu. Je zřejmé, že profesionální pozorovatelé mohou čekat i staletí, než se podobný úkaz objeví v zorném poli nějaké observatoře či terénní expedice. Zde se nabízí příležitost pro kohokoli, kdo se ve správnou chvíli podívá na nebe, protože se vzrůstajícím počtem pozorovatelů roste naděje, že se haló podaří zdokumentovat. Přitom právě výskyt lépe vyvinutých oblouků Scheinerova hala by mohl prozradit mnoho nejen o tvarech, v jakých se mohou krystaly krychlového ledu v atmosféře vyskytovat, ale vypovídal by i o jejich případné přednostní orientaci. Netřeba zdůrazňovat, že o takové informace by měly zájem nejen uznávané odborné časopisy, ale možná i tiskové agentury.

Obr. 6. Scheinerovo pozorování z 20. 3. 1629: 1 – Slunce, 2 – malé haló (r = 22◦ ), 3 – Scheinerovo haló (r = 28◦ ), 4 – horizontální kruh, 5 – parhelie malého hala, které shodou okolností v okamžiku pozorování svítily na průsečíku Scheinerova hala s horizontálním kruhem, 6 – stodvacetistupňová slunce, 7 – nadhlavník, 8 – Christophe Scheiner (dle pozorovatelova náčrtu, kresba Větvička)

22


FYZIKA

Literatura [1] Bednář, J.: Pozoruhodné jevy v atmosféře. Academia, Praha, 1989. [2] Příhoda, P., Holovská, H.: Průvodce astronomií. Hvězdárna a planetárium hl. m. Prahy, Praha, 1995. [3] Whalley, E.: Scheiners Halo: Evidence for Ice Ic in the Atmosphere, Science 211, 4480 (1981), s. 389–390. [4] Whalley, E.: Cubic Ice in Nature, Journal of Physical Chemistry 87, 21 (1983), s. 4174–4179. [5] http://tea.armadaproject.org/bowman/1.11.1999.html [6] www.atoptics.co.uk

Rozměrnost fyzikálního prostoru Jan Horský, Vladislav Navrátil, Pedagogická fakulta MU Brno Abstract. Physics teaching for secondary schools has to be schifted to be dealing with more modern and more actual living problems. Practically no information is presented obout one of a very fundamental problem of dimensions. We are trying to do so in the sense of a very nice book of Einstein and Infeld [1].

Otázka rozměrnosti prostoru je nejen velmi aktuální a živá, ale má také bohatou i poučnou historii. V pythagorejském obrazu světa se bod ztotožnil s jedničkou, dvojka s křivkou, trojka s rovinou a čtyřka s tělesem. Z komentáře Simplitia k Aristotelovu traktátu O nebi víme, že talentovaný Ptolemaios ukázal, že není více než tří rozměrů, nelze najít ” více než tři přímky svírající vzájemně pravý úhel, dvě z nich určují plochu, třetí pak hloubku. Kdyby byl další rozměr za třetím, byl by zcela neměřitelným a neurčeným.“ Galileo Galilei dokonce svoji knihu Dialog o dvou systémech světa začíná úvahami o třírozměrnosti prostoru. Salviati, hovořící zde za Galilea, navrhuje experimentálně vyjasnit, jaký je rozměr prostoru. Slovo experimentálně“ v sobě odráží, že pro Galilea ” je třírozměrnost prostoru faktem fyzikálním. Fyzikům tedy nestačí, že je představa o třírozměrnosti prostoru intuitivně jasná. I. Kant dal poprvé do souvislosti třírozměrnost prostoru s tvarem Newtonova gravitačního zákona. Známý holandský fyzik Paul Ročník 84 (2009), číslo 1

23

FYZIKA

Ehrenfest ukázal, jaké důsledky by měl jiný počet rozměrů prostoru na samotný pohyb planet, galaxií a tím i na stavbu celého vesmíru. Ehrenfest též prokázal, že spektrum a stavba vodíku by přinášely nesrovnatelnosti s experimentem v jiných prostorech než právě v prostorech třírozměrných. Bouřlivý rozvoj vědy začátkem minulého století přinesl další nové pohledy na zkoumaný problém. Francouzský matematik a fyzik H. Poincaré především velmi pečlivě propracoval samotný pojem dimenze (rozměrnosti) prostoru. H. Minkowski a A. Einstein velmi přirozenou cestou zavedli a jasně propracovali matematickou a fyzikální představu čtyřrozměrného prostoročasu. Vývoj se v tomto směru nezastavil ani po vzniku speciální teorie relativity, ani po vzniku obecné teorie relativity. Einstein stále věřil, že i když příroda doslova hýří bohatostí nejrůznějších struktur a jevů, že je velmi úsporná na základní principy. Až do své smrti pracoval na tzv. unitárních (jednotných) teoriích pole. Myšlenka unitární teorie pole je nicméně velmi přitažlivá. Podle ní by mělo existovat jediné základní, všezahrnující fyzikální pole, jehož projevem by byla všechna pole pozorovaná v přírodě – pole elektromagnetická, pole slabých i silných interakcí i pole gravitační. Cesta k takovýmto sjednocovacím snahám všech čtyř interakcí však byla a je dodnes hodně složitá. Začátkem dvacátých let minulého století T. Kaluza a O. Klein vytvořili jednotnou teorii elektromagnetického a gravitačního pole. V jejich teorii se vychází z představy, že ve fyzikálních základech popisu světa leží zakřivený prostoročas s jednou časovou a čtyřmi prostorovými souřadnicemi. Podařilo se odvodit rovnice, které zároveň popisovaly jak pole elektromagnetické, tak pole gravitační. Nepodařilo se však hlouběji objasnit podstatu páté souřadnice, její zavedení se jevilo jako umělé. Jak se dá například souřadnice (dimenze) navíc“ s jistou názorností ” zavést? Představte si, že žijete ve dvourozměrné ploše (jste dvourozměrní). Když se v ní pohybujete a dostanete se k nějaké čáře, nemůžete ji ani přelézt ani podlézt, musíte ji roztrhnout nebo obejít. V obklopujícím třírozměrném prostoru budiž umístěna žárovka a nit, která vrhá na vaši plochu stín. Protože v této ploše žijete, vnímáte jen to, co je v ní. Nevíte tedy nic o niti ani o žárovce. Víte však o existenci stínu, který je součástí vašeho světa, ale chová se jinak než ona čára“ přes cestu. Stín ” a jeho vlastnosti si můžeme prozkoumat a třeba vás napadne, že vznikl projekcí“ ze světa vyšší dimenze. ” 24


FYZIKA

Přejděme ke zmíněnému světu pětirozměrnému. Skutečnost že v běž” ných“ situacích se závislosti na páté souřadnici neprojevují, lze opět názorně objasnit například takto: křivka je jednorozměrný objekt tvořený body. Pod pojmem křivka si představíme například vlas. Vlas je ale ve skutečnosti třírozměrný objekt, třírozměrný pokřivený váleček. To, co je v naší představě o vlasu bod, je ve skutečnosti kroužek a když budeme uvažovat jen o plášti vlasu, je to kružnice. Plášť vlasu je dvojrozměrný objekt, který díky jeho malosti vnímáme jako jednorozměrný. Po plášti ale tak malého vlasu“, který by měl průměr třeba 10−33 cm, se už ale ” nemůže částice pohybovat, nemůžeme tedy z ničeho usoudit, že křivka má i svůj plášť, a že tedy není pouze objektem jednorozměrným. Lze tvrdit, že výsledky Kaluzových a Kleinových prací tvoří počátek nového přístupu k realizaci unitární teorie pole na základě prostoročasu s rozměrností (dimenzí) vyšší než čtyři. Takovému vyššímu rozměru se často říká dimenze skrytá, zkompaktifikovaná. Další stimulující roli sehrály výsledky práce řady fyziků, například F. Kleina, V. Foka, W. Heisenberga a dalších, a to v letech sedmdesátých. Zcela soudobá fyzika spočívá na dvou základních pilířích, na kvantové teorii a na obecné teorii relativity. První teorie v sobě nezahrnuje tak důležitou interakci – gravitační, druhá teorie není teorií kvantovou. Snaha o sjednocení obou teorií, snaha o vypracování jednotné teorie všech čtyř interakcí je posilována obrovskou touhou astrofyziků hlouběji porozumět stavu a vývoji vesmíru těsně kolem Velkého třesku. K požadavku takzvané supersymetrie užívanému již v předchozí části unifikační cesty se připojila myšlenka, že fundamentální stavební prvky hmoty nejsou bodové elementární částice, ale spíše jednodimenzionální struny, hovoří se o superstrunách kmitajících ve více než čtyřrozměrných prostorech (například v prostoru jedenáctirozměrném). Nutno ovšem dodat, že teorie superstrun není jedinou soudobou teorií kvantové gravitace, to by ale vyžadovalo samostatný příspěvek. Pokud by čtenář měl hlubší zájem o komplexní a fantastický výklad i soudobého spektra zmiňovaných otázek, doporučujeme dílo R. Penrose [2]. Literatura [1] Einstein, A., Infeld, L.: Fyzika jako dobrodružství poznání. Aurora, Praha, 2000. [2] Penrose, R.: The Road to Reality. Vintage books, London, 2004.


25

INFORMATIKA Recepty z programátorské kuchařky Korespondenčního semináře z programování, VIII. část*) Zdeněk Dvořák, Martin Mareš, David Matoušek, MFF UK Praha Abstract. We present several well-known applications of Divide and Conquer Method (dividing the problem to smaller subproblems and composing their solutions to a solution of the original problem): a linear-time algorithm for finding the median of a sequence, and a subquadratic algorithm for multiplication of long numbers.

V tomto dílu programátorské kuchařky se budeme zabývat algoritmy založenými na metodě Rozděl a panuj. A tak by se slušelo začít tím, jaká je myšlenka této metody: Často se setkáme s úlohami, které lze snadno rozdělit na nějaké menší úlohy a z jejich výsledků zase složit výsledek původní velké úlohy. Přitom menší úlohy můžeme řešit opět stejným algoritmem (zavoláme ho rekurzivně), jestliže nejsou dostatečně malé, abychom jejich výsledek nalezli triviálně bez jakéhokoliv počítání. Zkrátka jak říkali staří římští císaři: Divide et impera. Uveďme si pro začátek jeden staronový příklad. 1. QuickSort QuickSort je algoritmus pro třídění posloupnosti prvků. Už o něm byla jednou řeč ve druhém dílu kuchařky [4]. Tentokrát se na něj podíváme trochu podrobněji a navíc nám poslouží jako ingredience pro další algoritmy. QuickSort v každém svém kroku zvolí nějaký prvek (budeme mu říkat pivot) a přerovná prvky v posloupnosti tak, aby napravo od pivota byly pouze prvky větší než pivot a nalevo pouze menší. Pokud se vyskytnou prvky rovné pivotu, můžeme si dle libosti vybrat jak levou, tak pravou stranu posloupnosti, funkčnost algoritmu to nijak neovlivní. *) Informace o Korespondečním semináři z programování pořádaného Matematicko-fyzikální fakultou Univerzity Karlovy v Praze lze nalézt na webové stránce http://ksp.mff.cuni.cz.

26


INFORMATIKA

Tento postup pak rekurzivně zopakujeme zvlášť pro prvky nalevo a zvlášť pro prvky napravo od pivota, a tak získáme setříděnou posloupnost. Implementací QuickSortu je mnoho a mimo jiné se liší způsobem volby pivota. My si předvedeme jinou, než jsme ukazovali ve druhém dílu kuchařky (hlavně proto, že se nám z ní budou snadno odvozovat další algoritmy), a pro jednoduchost budeme jako pivota volit poslední prvek zkoumaného úseku: {budeme třídit takováto pole} type Pole=array[1..MaxN] of Integer; {přerovnávací procedura pro úsek a[l..r]} function prer(a:Pole; l,r:Integer):Integer; var i,j,x,q:Integer; begin {pivotem se stane poslední prvek úseku} x:=a[r]; {hodnota pivota} i:=l-1; {a[i] bude vždy poslední <= pivotovi} {samotné přerovnávání} for j:=l to r-1 do if a[j]<=x then {právě probíraný prvek} begin {menší/rovný hodnotě pivota} Inc(i); {pak zvyš ukazatel} {a proveď přerovnání prvku} q:=a[j]; a[j]:=a[i]; a[i]:=q; end; {nakonec přesuneme pivota za poslední <=} q:=a[r]; a[r]:=a[i+1]; a[i+1]:=q; prer:=i+1; {vrátíme novou pozici pivota} end; {hlavní třídící procedura, třídí a[l..r]} procedure QuickSort(a:Pole; l,r:Integer); var m:Integer; begin if l
Bohužel volit pivota právě takto je docela nešikovné, protože se nám snadno může stát, že si vybereme nejmenší nebo největší prvek v úseku (rozmyslete si, jak by vypadala posloupnost, ve které to nastane pokaždé), takže dostaneme-li posloupnost délky N , rozdělíme ji na úseky délek N − 1 a 1, načež pokračujeme s úsekem délky N − 1, ten rozdělíme Ročník 84 (2009), číslo 1

27

INFORMATIKA

na N −2 a 1 atd. Přitom pokaždé na přerovnání spotřebujeme čas lineární s velikostí úseku, celkem tedy O(N +(N −1)+(N −2)+. . .+1) = O(N 2 ). Na druhou stranu pokud bychom si za pivota vybrali vždy medián z právě probíraných prvků (tj. prvek, který by se v setříděné posloupnosti nacházel uprostřed; pro sudý počet prvků zvolíme libovolný z obou prostředních prvků), dosáhneme daleko lepší složitosti O(N log N ): Přerovnávací část algoritmu běží v čase lineárním vůči počtu prvků, které máme přerovnat. V prvním kroku QuickSortu pracujeme s celou posloupností, čili přerovnáme celkem N prvků. Následuje rekurzivní volání pro levou a pravou část posloupnosti (obě mají délku nanejvýš N/2); přerovnávání v obou částech dohromady trvá opět O(N ) a vzniknou tím části dlouhé nejvýše N/4. Zanoříme-li se v rekurzi do hloubky k, pracujeme s částmi dlouhými nejvýše N/2k a součet jejich délek je nejvýše N (všechny části dohromady dají prvky vstupní posloupnosti bez těch, které jsme si už zvolili jako pivoty). V hloubce log2 N už jsou všechny části nejvýše jednoprvkové, takže se rekurze zastaví. Celkem tedy máme log2 N hladin (hloubek) a na každé z nich trávíme lineární čas, dohromady O(N log N ). V tomto důkazu jsme se ale dopustili jednoho podvodu: Zapomněli jsme na to, že také musíme medián umět najít. Jak z této nepříjemné situace ven? • Naučit se počítat medián. Ale jak? • Spokojit se se lžimediánem“. Kdybychom si místo mediánu vybrali ” libovolný prvek, který bude v setříděné posloupnosti v prostřední polovině (čili alespoň čtvrtina prvků bude větší a alespoň čtvrtina menší než on), získáme také složitost O(N log N ): Úsek délky N rozložíme na úseky, které budou mít délky nejvýše 3/4 · N , takže na k-té hladině budou úseky délek ≤ (3/4)k · N . Hladin proto bude maximálně log4/3 N = O(log N ). Místo 1/4 by fungovala i libovolná jiná konstanta, ale ani to nám nepomůže k tomu, abychom uměli lžimedián najít. • Recyklovat pravidlo typu vezmi poslední prvek“ a jen ho trochu vy” lepšit (například si pivot zvolit jako medián z prvního, prostředního a posledního prvku posloupnosti). To bohužel nebude fungovat, protože pokud budeme při výběru pivota testovat jen konstantní počet prvků, budou existovat vstupy, pro které toto pravidlo bude dávat kvadratickou složitost. Obvykle však lze dokázat, že takových vstupů je málo“, proto se toto řešení prakticky často používá. ” 28


INFORMATIKA

• Volit pivota náhodně ze všech prvků zkoumaného úseku. K náhodné volbě samozřejmě potřebujeme náhodný generátor a s těmi je to svízelné, ale zkusme na chvíli věřit, že jeden takový máme nebo alespoň že máme něco s podobnými vlastnostmi. Jak nám pomůže? Náhodně zvolený pivot nebude sice přesně uprostřed, ale s pravděpodobností 1/2 to bude lžimedián, takže po průměrně dvou hladinách se ke lžimediánu dopracujeme. Proto časová složitost takovéhoto randomizovaného QuickSortu bude v průměru nanejvýš dvakrát větší, než lžimediánového QuickSortu, čili také O(N log N ). Zatímco fixní pravidlo nám dalo dobrý čas pro průměrný vstup, ale existovaly vstupy, na kterých bylo pomalé, randomizování nám dává dobrý průměrný čas pro všechny možné vstupy. 2. Hledání k-tého nejmenšího prvku Nad QuickSortem jsme zvítězili, ale současně jsme při tom zjistili, že neumíme rychle najít medián. Zkusíme nyní vyřešit obecnější problém: Najít k-tý nejmenší prvek (medián dostáváme pro k = N/2). První řešení této úlohy se nabízí samo. Načteme posloupnost do pole, prvky pole setřídíme nějakým rychlým algoritmem a kýžený k-tý nejmenší prvek nalezneme na k-té pozici v nyní již setříděném poli. Nicméně, jestliže prvky, které máme na vstupu, umíme pouze porovnat, pak nedosáhneme lepší časové složitosti (a to ani v průměrném případě) než O(N log N ) – rychleji třídit nelze, důkaz můžete najít opět ve druhé kuchařce. O něco rychlejší řešení (Hoare [2]) je založeno na výše zmíněném algoritmu QuickSort (často se mu proto říká QuickSelect). Opět si vybereme pivota a posloupnost rozdělíme na prvky menší než pivot, pivota a prvky větší než pivot (pro jednoduchost budeme předpokládat, že žádné dva prvky posloupnosti nejsou stejné). Jestliže je právě k − 1 prvků menších než pivot, pak pivot je hledaný k-tý nejmenší prvek posloupnosti. Zbývají dva případy, kdy tomu tak není. Jestliže je pozice pivota v posloupnosti větší než k, pak rekurzivně nalezneme k-tý nejmenší prvek mezi prvky menšími než pivot. V opačném případě, kdy je pozice pivota menší než k, je hledaný prvek větší než pivot. Mezi těmito prvky však nebudeme hledat k-tý nejmenší prvek, ale (k − p)-tý nejmenší prvek, kde p je pozice pivota v posloupnosti (počet prvků menších než pivot + 1). Časovou složitost rozebereme podobně jako u QuickSortu. Nešikovná volba pivota dává opět v nejhorším případě kvadratickou složitost. PoRočník 84 (2009), číslo 1

29

INFORMATIKA

kud bychom naopak volili za pivota medián, budeme nejprve přerovnávat N prvků, pak jich zbude nejvýše N/2, pak nejvýše N/4 atd., což dohromady dává složitost O(N + N/2 + N/4 + . . . + 1) = O(N ). Pro lžimedián dostaneme rovněž lineární složitost a stejně jako u QuickSortu můžeme nahlédnout, že náhodnou volbou pivota dostaneme v průměru stejnou časovou složitost jako se lžimediánem. S použitím přerovnávací procedury QuickSortu je program velmi jednoduchý: function kty(var a:Pole; l,r,k:Integer):Integer; var x,z:Integer; begin x:=prer(a,l,r); {přerovnej, x je pozice pivota} z:=x-l+1; {pozice pivota vzhledem k [l..r]} if k=z then kty:=a[x] {k-tý nejmenší je pivot} else if k
3. k-tý nejmenší podruhé, tentokrát lineárně a bez náhody Existuje i algoritmus (Blum at al. [1]), který řeší naši úlohu lineárně, a to i v nejhorším případě. Je založený na ďábelském triku: Zvolit vhodného pivota (jak ukážeme, bude to jeden ze lžimediánů) rekurzivním voláním téhož algoritmu. Podrobněji: 1. Pokud jsme dostali méně než 6 prvků, použijeme nějaký triviální algoritmus, například si posloupnost setřídíme a vrátíme k-tý prvek setříděné posloupnosti. 2. Jinak rozdělíme prvky posloupnosti na pětice; pokud není počet prvků dělitelný pěti, poslední pětici necháme nekompletní. 3. Spočítáme medián každé pětice (v konstantním čase), například opět jejich setříděním. 4. Máme tedy nanejvýš N/5 mediánů pětic. V nich rekurzivně najdeme medián m (označíme mediány pětic za novou posloupnost a začneme pro ni opět od prvního bodu). 5. Použijeme m jako pivota a rozdělíme vstupní posloupnost na prvky menší než m a prvky větší než m. Nechť je z počet prvků s menší hodnotou, než má pivot. 6. Stejně jako u předchozího algoritmu, jestliže k = z + 1, pak pivot m je k-tým nejmenším prvkem posloupnosti. V případě, že tomu tak není a k < z + 1, budeme hledat k-tý nejmenší prvek mezi prvními z členy 30


INFORMATIKA

posloupnosti, které jsou menší než m, a jestliže k > z + 1, budeme hledat (k − z − 1)-ní nejmenší prvek mezi prvky většími než m. V Pascalu: {potřebujeme přerovnávací funkci, která} {dostane hodnotu pivota jako parametr} function prerp(var a:Pole; l,r,m:Integer):Integer; var q,p:Integer; begin {nalezneme pozici pivota} p:=l; while a[p]<>m do inc(p); {pivota prohodíme s posledním prvkem} q:=a[p]; a[p]:=a[r]; a[r]:=q; {a zavoláme původní přerovnávací fci} prerp := prer(a,l,r); end; {hledání k-tého nejmenšího prvku z a[l..r]} function kth(var a:Pole; l,r,k:Integer):Integer; var medp:Pole; {pole pro mediány pětic} i,j,q,x,pocet,m,z:Integer; begin pocet:=r-l+1; {s kolika prvky pracujeme} if pocet<=1 then {pouze jeden prvek?} kth:=a[l] {výsledek nemůže být jiný} else if pocet<6 then begin {méně než 6 prvků} QuickSort(a,l,r); kth:=a[l+k-1]; end else begin {mnoho prvků, jde to tuhého, rozdělíme je do pětic} q:=1; {zatím máme jednu pětici} i:=l; {levý okraj první pětice} j:=i+4; {pravý okraj první pětice} while j<=r do begin {procházíme celé pětice} QuickSort(a,i,j); medp[q]:=a[i+2]; {medián pětice} Inc(q); {zvyš počet pětic} Inc(i,5); {nastav levý okraj pětice} Inc(j,5); {nastav pravý okraj pětice} end; {případnou neúplnou pětici můžeme ignorovat} {najdeme medián mediánů pětic} m:=kth(medp,1,q-1,q div 2); {přerovnej a zjisti, kde skončil pivot} x:=prer(a,l,r,m); z:=x-l+1; {pozice vzhledem k [l..r]} Ročník 84 (2009), číslo 1

31

INFORMATIKA if k=z then kth:=m {k-tý nejmenší je pivot} else if k
Zbývá dokázat, že tato dvojitá rekurze má lineární složitost. Zkusme se proto podívat, kolik prvků posloupnosti po přerovnání je větších než prvek m. Všech pětic je N/5 a alespoň polovina z nich (tedy N/10) má medián menší než m. V každé takové pětici pak navíc najdeme dva prvky menší než medián pětice, takže celkem existuje alespoň 3/10 · N prvků menších než m. Větších tedy může být maximálně 7/10 · N . Symetricky ukážeme, že i menších prvků může být nejvýše 7/10 · N . Rozdělení na pětice, hledání mediánů pětic a přerovnávání trvá lineárně, tedy nejvýše cN kroků pro nějakou konstantu c > 0. Navíc algoritmus dvakrát rekurzivně volá sám sebe: Nejprve pro N/5 mediánů pětic, pak pro nanejvýš 7/10 · N prvků před/za pivotem. Pro celkovou časovou složitost t(N ) našeho algoritmu tedy platí t(N ) ≤ cN + t(N/5) + t(7/10 · N ). Nyní zbývá tuto rekurzivní nerovnici vyřešit, což provedeme drobným úskokem: uhodneme, že výsledkem bude lineární funkce, tedy že t(N ) = dN pro nějaké d > 0. Dostaneme dN ≤ (c + 1/5 · d + 7/10 · d) · N. To platí například pro d = 10c, takže t(N ) = O(N ). 4. Násobení dlouhých čísel Dalším pěkným příkladem na metodu rozděl a panuj je násobení dlouhých čísel – tak dlouhých, že se už nevejdou do integeru, takže s nimi musíme počítat po číslicích (ať už v jakékoliv soustavě – my volíme desítkovou, často se hodí třeba 256-ková). Klasickým školním“ algoritmem ” pro násobení na papíře to zvládneme na kvadratický počet operací, zde si předvedeme efektivnější způsob (Karatsuba a Ofman [3]). Libovolné 2N -ciferné číslo mužeme zapsat jako 10N A + B, kde A a B jsou N -ciferná. Součin dvou takových čísel pak bude: (10N A + B) · (10N C + D) = 102N AC + 10N (AD + BC) + BD 32


INFORMATIKA

Sčítat dokážeme v lineárním čase, násobit mocninou deseti také (dopíšeme příslušný počet nul na konec čísla), N -ciferná čísla budeme násobit rekurzivním zavoláním téhož algoritmu. Pro časovou složitost tedy bude platit t(N ) = cN + 4t(N/2). Nyní tuto rovnici můžeme snadno vyřešit, ale ani to dělat nebudeme, neboť nám vyjde, že t(N ) ≈ N 2 , čili jsme si oproti původnímu algoritmu vůbec nepomohli. Nicméně, místo čtyř násobení čísel poloviční délky nám stačí pouze tři: Spočteme AC, BD a (A + B) · (C + D) = AC + AD + BC + BD, přičemž pokud od posledního součinu odečteme AC a BD, dostaneme AD + BC, které jsme předtím počítali dvěma násobeními. Časová složitost nyní bude t(N ) = c N + 3t(N/2). Konstanta c je o něco větší než c, protože přibylo sčítání a odčítání. Zvolme si pro jednoduchost jednotku času tak, aby bylo c = 1. Jak tuto rovnici vyřešíme? Zkusíme ji dosadit do sebe samé a pozorovat, co se bude dít: t(N ) = N + 3(N/2 + 3t(N/4)) = N + 3/2 · N + 9t(N/4) = = N + 3/2 · N + 9/4 · N + 27t(N/8) = = N + 3/2 · N + . . . + 3k−1 /2k−1 · N + 3k t(N/2k ) Pokud zvolíme k = log2 N , vyjde N/2k = 1, čili t(N/2k ) = t(1) = d, kde d je nějaká konstanta. To znamená, že t(N ) = N · (1 + 3/2 + 9/4 + . . . + (3/2)k−1 ) + 3k d. Výraz v závorce je součet prvních k členů geometrické řady s kvocientem 3/2, čili: (3/2)k − 1 = O((3/2)k ) (3/2 − 1) Tato funkce však roste pomaleji než zbylý člen 3k d, takže ji můžeme zanedbat a zabývat se pouze oním posledním členem 3k = 2k log2 3 = 2log2 n·log2 3 = (2log2 n )log2 3 = nlog2 3 ≈ n1.58 . Konstanta d se nám schová do O-čka“, takže algoritmus má časovou ” složitost přibližně O(n1.58 ). Existují i rychlejší algoritmy (např. Sch¨ onhage–Strassenův algoritmus [6] s časovou složitostí O(n log n log log n)), ale jsou mnohem složitější a pro malá n se nevyplatí – zatímco popsaný algoritmus je rychlejší než jednoduchý kvadratický algoritmus Ročník 84 (2009), číslo 1

33

INFORMATIKA

pro n ≈ 100, Sch¨ onhage–Strassenův algoritmus je rychlejší až pro n ≈ 20 000. 5. Rozmyslete si • Při hledání k-tého nejmenšího prvku jsme předpokládali, že všechny prvky jsou různé. Prohlédněte si algoritmy pozorně a rozmyslete si, že budou fungovat i bez toho. Opravdu? • Proč jsme zvolili zrovna pětice? Jak by to dopadlo pro trojice? A jak pro sedmice? Fungoval by takový algoritmus? Byl by také lineární? • Ve výpočtu t(N ) jsme si nedali pozor na neúplné pětice a také jsme předpokládali, že pětic je sudý počet. Ono se totiž nic zlého nemůže stát. Jak se to snadno nahlédne? Proč nestačí na začátku doplnit vstup nekonečny“ na délku, která je mocninou deseti? ” • Kdybychom neuhodli, že t(N ) je lineární, jak by se na to dalo přijít? • Ještě jednou QuickSort: Představte si, že budujete binární vyhledávací strom (viz například čtvrtou kuchařku [5]) vkládáním prvků v náhodném pořadí. Obecně nemusí být vyvážený, ale v průměru v něm půjde vyhledávat v čase O(log N ). Žádný div: Stromy, které nám vzniknou, odpovídají přesně možným průběhům QuickSortu.

Literatura [1] Blum, M., Floyd, R. W., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. System Sci. 7 (1973), s. 448–461.

[2] Hoare, C. A. R.: Partition: Algorithm 63, Quicksort: Algorithm 64, Find: Algorithm 65. Comm. ACM 4, 7 (1961), s. 321–322.

[3] Karatsuba, A., Ofman, Yu.: Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR 145 (1962), s. 293–294. Translation in Physics–Doklady 7 (1963), 595–596. [4] Kráľ, D., Mareš, M., Valla, T.: Recepty z programátorské kuchařky Korespondenčního semináře z programování – II. část. Rozhledy matematickofyzikální 80, 2 (2005), s. 25–35. [5] Kráľ, D., Mareš, M., Straka, M.: Recepty z programátorské kuchařky Korespondenčního semináře z programování – IV. část. Rozhledy matematickofyzikální 82, 1 (2007), s. 22–35. [6] Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7 (1971), s. 281–292.

34


HISTORIE Johann Wolfgang Goethe kontra Isaac Newton Ivo Kraus, FJFI ČVUT, Praha Abstract. Johann Wolfgang Goethe is an author not only of poetry, fiction and drama, but of natural science as well. In his scientific work Theory of Colours (Zur Farbenlehre), Goethe rejects Newton’s Optics. Although Goethe’s physical observations are false, we have to agree with his statement that human emotional life is not always simply subjective and unexpected. The paper presents Goethe’s considerations on sensual-moral effect of colours, which claim the emotional reactions caused by individual colours to be regular and predictable.

Stejně jako před dvěma sty lety vítá i dnes návštěvníky Goethova bytu na výmarském náměstí Frauenplan pozdrav Salve. Až do vysokého věku tu básník přijímal hosty téměř každý den. Mnohem častěji než literáty si prý ale zval přírodovědce, historiky umění, politiky a cestovatele. Své práce z optiky, mineralogie, anatomie, morfologie rostlin a živočichů považoval totiž za stejně významné jako poezii, dramata nebo díla filozofická. Zatímco moudrým otevíral dveře ochotně a rád, o dotěrné obdivovatele nikdy nestál: Veřejné mínění zbožňuje člověka a rouhá se ” bohům; často vynáší chyby, nad nimiž se červenáme, a vysmívá se ctnostem, na než jsme hrdi.“

Obr. 1. Johann H. W. Tischbein (1786): Goethe v Kampanii Ročník 84 (2009), číslo 1

35

HISTORIE

Goethovo odborné curicullum vitae Narodil se 28. srpna 1749 ve Frankfurtu nad Mohanem, zemřel 22. března 1832 ve Výmaru. Studoval na právnických fakultách v Lipsku (1765–1769) a ve Štrasburku (1770–1771), po promoci působil u soudů ve Frankfurtu a Wetzlaru (1771–1775). V roce 1776 vstoupil do služeb sasko-výmarského vévody Karla Augusta. Prvními úkoly, které od něho ve Výmaru dostal, bylo připravit obnovení důlních prací v durynském Ilmenau a řídit komisi pro stavbu silnic. Právě tam jsou počátky Goethových pozdějších geologických a mineralogických zájmů.1) Velký počet exemplářů do své sbírky nerostů získal v Karlových Varech a Mariánských Lázních. Při sedmnácti návštěvách Čech navázal řadu odborných kontaktů s našimi přírodovědci, např. se spoluzakladatelem Národního muzea hrabětem Kašparem Šternberkem, legendární jsou i jeho cesty za Ulrikou von Leventzow. V druhé přírodovědné zálibě – biologii – chtěl Goethe dokázat spřízněnost všech živých bytostí. Už kolem roku 1787 vyslovil názor, že všechny části rostliny mají jediný základní orgán – list, z něhož pak postupnou přeměnou vzniká celá rostlina; různé druhy jsou důsledkem odlišných forem metamorfózy. Koncepci příbuznosti živých organizmů později podpořil objevem mezičelistní kosti člověka (až do té doby se její existence předpokládala pouze u zvířat) a důkazem, že stejně jako lidem vznikly lebeční kosti z metamorfovaných obratlů také zvířatům. Polemika s Newtonem V roce 1790 začal Goethe psát Nauku o barvách (Farbenlehre). Když však dílo o 1 400 stranách po dvaceti letech uveřejnil, reagovala odborná veřejnost na jeho fyzikální úvahy a zatracování Newtona (1642–1727) přinejmenším rozpačitě.2) 1)

Pyrrhosiderit, známý z příbramských dolů jako sametka, je uváděn také pod názvem goethit. 2) V únoru 1672 vyšla v časopise Philosophical Transactions první Newtonova samostatná práce Nová teorie světla a barev . Téhož roku začal připravovat Optiku; tiskem ji však vydal až za tři desetiletí (1704). Na základě vlastních experimentů s hranoly a čočkami došel k závěru, že bílé světlo je proud elementárních světelných částic vznikajících výronem (emanací) ze svítícího tělesa a lišících se podle barvy svým tvarem a velikostí; bíle světlo je tedy směsí všech druhů barev. Tyto částice se šíří nesmírnou rychlostí rovnoměrně a přímočaře na všechny strany, při dopadu na rozhraní se některé odrážejí, jiné postupují dál. Newtonův věhlas byl tak obrovský, že většina vědců považovala korpuskulární (emanační) teorii světla za správnou a nezpochybnitelnou stejně jako Písmo. Newtonova teorie byla sice od-

36


HISTORIE

Je jisté, že básník musel Newtonovu teorii znát. Jinak by nemohl napsat: Každé bezbarvé světlo, především světlo sluneční, obsahuje podle ” Newtona více světel různě zbarvených; jejich složením vzniká světlo bílé. Aby se barevná světla zviditelnila, je třeba bílému světlu klást do cesty všelijaké překážky, které mění jeho dráhu.“ Podle Goethových představ je barva vytvářena nejen světlem, ale i tím, co se mu staví do cesty: Po” kud se na hmotné prostředí díváme očima, je průhledné, neprůhledné nebo poloprůhledné (kalné). Jestliže světlo prochází kalným prostředím, takže se tam jeho původní síla zachytává, ale stále ještě jde dál, jeví se nám žluté nebo žlutočervené. Nemůže-li projít dál, protože je kalné prostředí ohraničeno tmou, vrací se světlo jako odlesk a má podobu modrou a modročervenou. Nekonečnost a nespočetnost barev vzniká jejich smíšením.“ (Připomeňme Aristotela, podle něhož je bílé světlo jednoduché, zatímco barevné tvoří směs světla a tmy.) Mnohem zajímavější než Goethovy fyzikální omyly jsou jeho některé charakteristiky Newtona a jeho stoupenců. Newtonova teorie je přirovnávána ke starému hradu, který stavitel zpočátku budoval s mladickou unáhleností a pak jej podle potřeb času rozšiřoval, zařizoval, upevňoval a zabezpečoval. Stejně postupovali i další majitelé hradu a dědici. Budovu zvětšovali, sem tam něco přistavěli vedle, něco nahoru, pokaždé tak, jak to vyžadovaly rostoucí vnitřní potřeby, dotěrnost vnějších protivníků i různé náhodné okolnosti. Všechny cizorodé části a přístavby musely být navzájem opět pospojovány nejpodivnějšími galeriemi, sály a chodbami. Každé poškození způsobené nepřítelem nebo zubem času bylo hned opraveno. Hrad odrazil mnoho útoků a zmařil nejedno obléhání. Své renomé nedobytnosti neztratil dodnes; stále se hovoří o jeho vynikající stabilitě i vybavenosti. Nikdo si však neuvědomuje, že stavba je dávno neobyvatelná. Hradu se chodí klanět poutníci, ve všech školách se ukazují jeho náčrty a vnímavé mládeži je doporučováno hrad uctívat, přestože je už prázdný a hlídá ho jen několik invalidů. Tento osmý div světa, toto staré hnízdo potkanů a sov je třeba bez otálení strhnout, pustit do něj slunce a odhalit oku žasnoucího poutníka labyrintovitě nestejnorodý styl a vyumělkovanost stavby. Není snadné vyjádřit jiný názor na barvy ” mítnuta Robertem Hookem (1653–1703), Christiaanem Huygensem (1629–1695), velkým matematikem Leonhardem Eulerem (1707–1783) i jinými učenci, přesto nad vlnovou teorií vítězila až do roku 1850. Tehdy Jean Foucault (1819–1868) zjistil, že světlo se šíří ve vodě pomaleji než ve vzduchu, tj. ve shodě s vlnovou teorií a v protikladu s teorií korpuskulární.


37

HISTORIE

než předkládá Newton. Žádný aristokratický domýšlivec nikdy nepohrdal těmi, co nepatřili do jeho cechu, jako pohrdá newtonovská škola vším, co vzniklo před ní nebo co se vytvářelo mimo ni.“ Goethův Newton byl zdravý a vyrovnaný muž, bez náruživostí a žádostí; matematika mu sloužila jako hlavní nástroj, kterým se snažil vybudovat svůj vnitřní svět a zvládnout svět vnější. Necítím se povolaný ” posuzovat tuto Newtonovu přednost,“ přiznává Goethe, protože jeho ” talent leží za mým vlastním horizontem. Jsem však přesvědčen, že s lehkostí pochopil a převzal to, co vykonali jeho předchůdci, a podivuhodným způsobem to dále rozvinul. V době, kdy žil, si ho průměrní lidé vážili a uctívali, nejlepší ho pokládali za sobě rovného nebo se s ním pro významné objevy a vynálezy dostávali do sporu.“ (Tím mohl myslet třeba Roberta Hooka a Gottfrieda Wilhelma Leibnize.) S takovou charakteristikou lze souhlasit. Méně už s hodnocením Newtonovy vědecké metody: Svou teorii prý budoval dogmaticky, pouhé představy předkládal jako bezesporná fakta a námitky, které nemohl popřít, jednoduše ignoroval. Svým kritikům stále opakoval: jděte na věc tak jako já, dejte se mou cestou; zařiďte všechno tak, jak jsem to zařídil i já; dívejte se stejně jako já; myslete stejně jako já a najdete totéž, co já; všechno ostatní je špatné. Každý omyl, který pochází bezprostředně z člověka a z podmínek, ” které ho obklopují, je omluvitelný, ba ctihodný,“ říká Goethe. Všechny ” ty, co ho v omylu následují, je třeba ovšem posuzovat přísněji. Opakovaná pravda ztrácí svůj půvab, opakovaný omyl je nechutný a směšný. Rozejít se s vlastním omylem je těžké, a jde-li o velkého člověka a velké talenty, leckdy téměř nemožné. Vytrvalost těch, kdo se mýlí originálně, nás může rozhněvat; tvrdošíjnost lidí, kteří omyl kopírují, vyvolává mrzutost a odpor.“ V čem měl Goethe pravdu V každé vědě je tolik vědy, kolik je v ní matematiky, prohlásil Immanuel Kant (1724–1804). Zdaleka ne všechno, co vnímáme ve světě, se ale dá popsat pojmy převoditelnými do číselných vztahů. K čemu je nám matematika při pozorování vůně květin, chuti ovoce nebo hledání odpovědi na otázku, jak působí různé barvy na naše vnitřní zážitky? Citový život nemusí být podle Johanna Wolfganga Goetha vždy jen něčím subjektivním, vyplývajícím z naší povahy, a tedy neočekávaným. V té části své Nauky o barvách, která pojednává o smyslově-morálním účinku barev, ukázal, že jednotlivé barvy vyvolávají zákonité a jednoznačně předvídatelné citové reakce. 38


HISTORIE

Kontroverzní Goethovo dílo vyšlo před dvěma stoletími (1810). Mnoho tvrzení ve zkoušce času neobstálo, s jinými budou naopak souhlasit i budoucí generace: • Barva působí na náš zrak a jeho prostřednictvím i na náš citový fond specifickým účinkem, jednak sama o sobě, jednak spolu s jinými barvami, jednou harmonicky, jednou charakteristicky, často také neharmonicky, vždycky však účinkem výrazným a významným, účinkem, jež je spjat bezprostředně s okruhem zážitků, jež nazýváme morálními. Proto je také možné využívat barvy, uvažujeme-li o ní jako o jednom z prvků umění, k tomu, abychom s její pomocí dosáhli nejvyšších estetických cílů. • Povšechně pociťují lidé z barev velkou radost. Oko je potřebuje, jako potřebuje světlo. Vzpomeňme, jak nás to osvěží, když za pošmourného dne slunce osvítí jednotlivou část krajiny a učiní barvy v ní viditelnými. Že lidé připisovali barevným drahokamům léčivé síly, povstalo snad z hlubokého pocitu tohoto nevýslovného uspokojení. • Zkušenost nás učí, že jednotlivé barvy poskytují zvláštní citová naladění. O kterémsi duchaplném Francouzovi se vypráví: Tvrdil, že tón jeho konverzace s onou dámou se změnil od té doby, co ona změnila barvu nábytku ve svém pokoji z modré na karmínovou. • Barvy na straně kladné jsou žlutá, oranžová, jasně červená. Ladí nás do čilosti, živosti, snaživosti. Žlutá barva je nejbližší světlu . . . Ve své nejvyšší čistotě má v sobě vždycky povahu jasu a je v ní něco veselého, čilého, jemně povzbudivého . . . Je to tedy v souhlase se zkušeností, řekneme-li, že žlutá na nás působí veskrze teple a přívětivě . . . Tento hřejivý účinek můžeme pozorovat nejživěji, když se zadíváme na krajinu, zejména v šerých zimních dnech, žlutým sklem. Oko je potěšeno, srdce se šíří, mysl se rozjařuje, je to, jako by nám vanulo vstříc bezprostřední teplo. Všechno, co jsme pověděli o žluté, platí i o oranžové, jenom ve vyšší míře. Oranžová dává oku pocit hřejivosti a slasti, představuje barvu vyššího žáru a mírnější odlesk zapadajícího slunce. Jako přechází čistá žlutá velmi snadno do oranžové, tak se oranžová stupňuje nezadržitelně do jasně červené. Příjemný pocit rozveselení, jaký nám poskytuje ještě oranžová, stupňuje se až k pocitu nesnesitelného násilí ve vystupňované jasné červeni. • Barvy strany záporné jsou modrá, modrofialová a fialová. Ladí nás do neklidného, měkkého a toužebného pocitu. Jako ve žluti je vždycky přítomno světlo, tak se dá říci, že v modři je vždycky přítomno něco temného . . . Modř nám vnuká pocit chladu, také nám připomíná stíny . . . Pokoje opatřené čistě modrou tapetou se zdají do jisté míry prostorné, Ročník 84 (2009), číslo 1

39

HISTORIE

ale vlastně prázdné a studené . . . Modré sklo ukazuje předměty ve smutném osvětlení. Modř se může stupňovat velice jemně směrem do červena . . . její dráždivost je však jiného rázu než u jasně červeně. Neoživuje, ale spíše zneklidňuje . . . , také odstín lila nebo šeříková má v sobě cosi živého bez veselosti. Fialová barva vyvolává neklid . . . Jestliže si ji oblíbilo vysoké duchovenstvo, dalo by se říci, že má namířeno po žebříku neutuchajícího stupňování nezadržitelně až ke kardinálskému purpuru. • Účinek červené barvy je stejně jedinečný jako její přirozená povaha. Působí dojmem jak vážnosti a důstojnosti, tak grácie a líbeznosti. Jedním ve svém tmavém, zhuštěném stavu, tím druhým ve stavu světlém a zředěném. A tak se může i důstojnost stáří i půvab mládí odívat jednou a touž barvou. • Když žlutou a modrou, jež považujeme za první a nejjednodušší barvy, spojíme hned při jejich prvním objevení, vznikne barva zelená . . . Naše oko v ní nachází reálné uspokojení. Proto se pro pokoje, v nichž stále pobýváme, volí pro tapetu nejčastěji právě zelená barva. Co řekl • Kdyby se moudří nikdy nemýlili, museli by si blázni zoufat. • Učenci jsou nejvíce nevraživí, když oponují; na toho, kdo se mýlí, pohlížejí jako na svého úhlavního nepřítele. • Vysvětlovat jednoduché pomocí složitého a lehké pomocí těžkého je neduh, který zachvátil celou vědu a který si moudří sice uvědomují, ale zřídkakdy přiznávají. • Člověk se skládá ze samých chyb. Některé z nich jsou pokládány za společensky prospěšné, jiné za škodlivé, některé za upotřebitelné, jiné za zcela zbytečné. První nazýváme ctnostmi, druhé špatnými vlastnostmi. • Na uchopení pravdy je třeba mnohem větší úsilí, než na obhajování omylu.

Obr. 2. Tzv. Goethovy barometry z 19. století; hladina vody ve výlevkovité části skleněných nádob při vysokém tlaku klesá, při nízkém naopak stoupá

40


HISTORIE

Listy z kalendára Dušan Jedinák, Trnavská univerzita v Trnave Jacob Robert OPPENHEIMER — (22. 4. 1904 – 18. 2. 1967) Udivoval odbornými znalosťami i rečníckym talentom. Čítal v origináli Homéra, Vergília, Seneku i Tacita, ovládal deväť jazykov. Rozumel fyzike, zaujímal sa o filozofiu a literatúru, písal básne. Z teoretickej fyziky publikoval 72 odborných prác, stal sa ústrednou postavou jadrovej fyziky USA. Získal Fermiho cenu a vytvoril v Princetone na Inštitúte pre pokročilé štúdiá centrum teoretickej a jadrovej fyziky. Zapojil sa do projektu Manhattan a jeho pričinením na výrobe atómovej bomby spolupracoval výkvet americkej modernej fyziky. Neďaleko Alamogorda 16. júla 1945 bol pri prvom výbuchu atómovej bomby. Aj keď organizačne a odborne prispel k uvoľneniu obrovských síl v atómovej bombe, uvedomil si, že to bolo diabolské dielo“. ” Zničenie Hirošimy a Nagasaki doľahlo na neho rozčarovaním a ľútosťou nad tým, čo spôsobil výtvor ním pripravovaný. Proti výrobe vodíkovej bomby sa už dokázal postaviť. Považoval sa za vedca – štátnika, organizátora výskumu. Dúfal, že môže dať do poriadku celý svet. Zmýlil sa. Zohral úlohu Hamleta atómového veku Z myšlienok • Fyzici sa naučili krutým spôsobom, čo je hriech. Na túto skúsenosť nezabudnú nikdy. • Už dávno malo byť nariadené jemnejšie pochopenie povahy ľudského poznania a vzťahov človeka k vesmíru. • V každom výskume, v každom rozšírení znalostí sme vtiahnutí k rozhodnutiu a v každom rozhodnutí je zahrnutá nejaká naša strata, strata toho, čo sme si nezvolili. • Zmysel spoznávame vždy tým, že niečo vynechávame. • Môžeme si navzájom pomáhať, pretože sa navzájom milujeme.


41

SOUTĚŽE Úlohy domácího kola 59. ročníku Matematické olympiády pro žáky středních škol Kategorie A 1. V oboru reálných čísel řešte soustavu rovnic x2 − y = z − 1, y 2 − z = x − 1, z 2 − x = y − 1. (Radek Horenský) 2. Kosočtverci ABCD je vepsána kružnice. Uvažujme její libovolnou tečnu protínající obě strany BC, CD a označme po řadě R, S její průsečíky s přímkami AB, AD. Dokažte, že hodnota součinu |BR| · |DS| na volbě tečny nezávisí.

(Leo Boček )

3. Na tabuli jsou napsána čísla 1, 2, . . . , 33. V jednom kroku zvolíme na tabuli dvě čísla, z nichž jedno je dělitelem druhého, obě smažeme a na tabuli napíšeme jejich (celočíselný) podíl. Takto pokračujeme, až na tabuli zůstanou jen čísla, z nichž žádné není dělitelem jiného. (V jednom kroku můžeme smazat i dvě stejná čísla a nahradit je číslem 1.) Kolik nejméně čísel může na tabuli zůstat? (Peter Novotný) 4. V libovolném ostroúhlém různostranném trojúhelníku ABC označme O, V a S po řadě střed kružnice opsané, průsečík výšek a střed kružnice vepsané. Dokažte, že osa úsečky OV prochází bodem S, právě když jeden vnitřní úhel trojúhelníku ABC má velikost 60◦ . (Tomáš Jurík ) 42


SOUTĚŽE

5. V kádi je r0 ryb, společný úlovek n rybářů. Přicházejí pro svůj díl jednotlivě, každý si myslí, že se dostavil jako první, a aby si vzal přesně n-tinu aktuálního počtu ryb v kádi, musí předtím jednu z ryb pustit zpět do moře. Určete nejmenší možné číslo r0 v závislosti na daném n ≥ 2, když i poslední rybář si aspoň jednu rybu odnese. (Dag Hrubý) 6. Pro dané prvočíslo p určete počet (všech) uspořádaných trojic (a, b, c) čísel z množiny {1, 2, 3, . . . , 2p2 }, které splňují vztah p2 + 1 [a, c] + [b, c] = 2 · c, a+b p +2 kde [x, y] značí nejmenší společný násobek čísel x a y. (Tomáš Jurík ) Kategorie B 1. Na stole leží tři hromádky zápalek: v jedné 2 009, ve druhé 2 010 a v poslední 2 011. Hráč, který je na tahu, zvolí dvě hromádky a z každé z nich odebere po jedné zápalce. Ve hře se pravidelně střídají dva hráči. Hra končí, jakmile některá hromádka zmizí. Vyhrává ten hráč, který udělal poslední tah. Popište strategii jednoho z hráčů, která mu zajistí výhru. (Ján Mazák ) 2. Na tabuli je napsáno čtyřmístné číslo, které má přesně šest kladných dělitelů, z nichž právě dva jsou jednomístní a právě dva dvojmístní. Větší z dvojmístných dělitelů je druhou mocninou přirozeného čísla. Určete všechna čísla, která mohou být na tabuli napsána. (Peter Novotný) 3. V rovině je dána úsečka AB. Sestrojte rovnoběžník ABCD, pro jehož středy stran AB, CD, DA označené po řadě K, L, M platí: body A, B, L, D leží na jedné kružnici a rovněž body K, L, D, M leží na jedné kružnici. (Jaroslav Švrček ) 4. Najděte 2 009 po sobě jdoucích čtyřmístných čísel, jejichž součet je součinem tří po sobě jdoucích přirozených čísel. (Radek Horenský) Ročník 84 (2009), číslo 1

43

SOUTĚŽE

5. Uvnitř kratšího oblouku AB kružnice opsané rovnostrannému trojúhelníku ABC je zvolen bod D. Tětiva CD protíná stranu AB v bodě E. Dokažte, že trojúhelník se stranami délek |AE|, |BE|, |CE| je podobný trojúhelníku ABD. (Pavel Leischner ) 6. Reálná čísla a, b mají tuto vlastnost: rovnice x2 − ax + b − 1 = 0 má v množině reálných čísel dva různé kořeny, jejichž rozdíl je kladným kořenem rovnice x2 − ax + b + 1 = 0. a) Dokažte nerovnost b > 3. b) Pomocí b vyjádřete kořeny obou rovnic. (Jaromír Šimša) Kategorie C 1. Erika a Klárka hrály hru slovní logik“ s těmito pravidly: Hráč A ” si myslí slovo složené z pěti různých písmen. Hráč B vysloví libovolné slovo složené z pěti různých písmen a hráč A mu prozradí, kolik písmen uhodl na správné pozici a kolik na nesprávné. Písmena považujeme za různá, i když se liší jen háčkem nebo čárkou (například písmena A, Á jsou různá). Kdyby si hráč A myslel například slovo LOĎKA a B by vyslovil slovo KOLÁČ, odpoví hráč A, že jedno písmeno uhodl hráč B na správné pozici a dvě na nesprávné. Zkráceně sdělí 1 + 2“, neboť se opravdu obě slova shodují pouze v písmenu O ” včetně pozice (druhé zleva) a v písmenech K a L, jejichž pozice jsou odlišné. Erika si myslela slovo z pěti různých písmen a Klárka vyslovila slova KABÁT, STRUK, SKOBA, CESTA a ZÁPAL. Erika na tato slova v daném pořadí odpověděla 0 + 3, 0 + 2, 1 + 2, 2 + 0 a 1 + 2. Zjistěte, jaké slovo si Erika mohla myslet. (Peter Novotný) 2. Vrcholem C pravoúhelníku ABCD veďte přímky p a q, které mají s daným pravoúhelníkem společný pouze bod C, přičemž přímka p má od bodu A největší možnou vzdálenost a přímka q vymezuje s přímkami AB, AD trojúhelník co nejmenšího obsahu. (Leo Boček ) 3. Určete všechna reálná čísla x, která vyhovují rovnici 4x − 2x = 5. (Symbol x značí největší celé číslo, které není větší než číslo x, tzv. dolní celou část reálného čísla x.) (Jaroslav Švrček ) 44


SOUTĚŽE

4. Kružnice k(S; r) se dotýká přímky AB v bodě A. Kružnice l(T ; s) se dotýká přímky AB v bodě B a protíná kružnici k v krajních bodech C, D jejího průměru. Vyjádřete délku a úsečky AB pomocí poloměrů r, s. Dokažte dále, že průsečík M přímek CD, AB je středem úsečky AB. (Leo Boček ) 5. Dokažte, že pro libovolná kladná reálná čísla a, b platí √ a+b 2(a2 + 3ab + b2 ) ≤ , ab ≤ 5(a + b) 2 a pro každou z obou nerovností zjistěte, kdy přechází v rovnost. (Ján Mazák ) 6. Najděte všechna přirozená čísla, která nejsou dělitelná deseti a která ve svém dekadickém zápisu mají někde vedle sebe dvě nuly, po jejichž vyškrtnutí se původní číslo 89krát zmenší. (Jaromír Šimša)

Úlohy 50. ročníku fyzikální olympiády, kategorie G – Archimédiáda Ivo Volf, Univerzita Hradec Králové a Ústřední komise FO FO50G1 Třikrát o zvuku a) Když blesk rozčísne večer oblohu, hluk hromu nás dostihne až po době 15 s. Navrhni způsob, jak jednoduše odhadnout vzdálenost elektrického výboje. b) Stojíš-li před skalní stěnou a křikneš-li HEJ!, po době 1,8 s uslyšíš HEJ!, slabší sice, ale přece. Tento jev se nazývá odborně echo. Popiš ho, vysvětli, nazvi česky a odhadni vzdálenost skalní stěny. c) Kdysi se hloubky v moři měřily spouštěním olovnice. Dnes se užívá tzv. sonaru. Vysvětli stručně jeho činnost (najdi si třeba v encyklopedii nebo na internetu) a urči hloubku v moři, vrátí-li se signál z lodi za dobu 0,28 s. Proč je sonar nepříjemný některým živočichům? Ročník 84 (2009), číslo 1

45

SOUTĚŽE

FO50G2 Trámy na chalupu Při opravě střechy chalupy bylo třeba přivézt trámy. Tesař požadoval 20 trámů o délce 9,6 m a o příčném řezu 14 cm × 16 cm, dále 32 trámů o délce 8,0 m a příčném řezu 14 cm × 8 cm. Hustota smrkového dřeva je 650 kg/m3 . a) Urči objem a hmotnost každého z uvedených dvou typů trámů. b) Jaká je celková hmotnost všech trámů, které naložíme na nákladní automobil? c) Uneseš lehčí nebo i těžší trám? Jakou silou musíš trám zvednout alespoň na jednom konci? d) Karel pozoroval, jak závozník nakládá trámy: zvedne jeden konec trámu na plošinu automobilu, a potom ho zasune celý na plošinu. Nakresli obrázek, vysvětli a posuď. FO50G3 Dvě sekundy Mezi řidiči se někdy hovoří o důležitém pravidle dvě sekundy“. V praxi ” to znamená, že řidič má udržovat od vozidla, jedoucího před ním, tak velkou vzdálenost, kterou by při dané rychlosti urazil právě za 2 s. Zvol rychlosti 36 km/h, 45 km/h, 54 km/h, 63 km/h, 72 km/h, 90 km/h, 108 km/h, 120 km/h, 126 km/h, 144 km/h, 180 km/h, 216 km/h. a) Urči požadovanou vzdálenost mezi po sobě jedoucími vozidly při zvolených rychlostech. b) Sestav tabulku, obsahující pro dané hodnoty: rychlost v km/h, tutéž rychlost v m/s, tutéž rychlost v britských či amerických jednotkách mph (mile per hour). c) Do posledního sloupce urči doporučenou vzdálenost od předchozího vozidla podle pravidla dvě sekundy“. ” FO50G4 Malý železný muž Na dětském táboře se vedoucí rozhodli, že uspořádají hru Malý železný ” muž“. Podle stejné soutěže pro dospělé se skládá ze tří částí – plavání, běh a jízda na kole, jen trasy byly zvoleny kratší. Našli si proto vhodné místo u nepříliš hlubokého rybníka, jehož šířka byla 600 m; poté mohli soutěžící běžet po polní cestě po trase o délce 1 200 m a konečně po silnici jeli na kole po trase 2,8 km. Soutěžící se přihlásili jenom tři – přes rybník přeplavali pod dozorem vedoucího za stejnou dobu 12,0 min, běh zvládli v časech 5,00 min, 5,20 min, 5,30 min a jízdu na kolech v časech 8,30 min, 8,10 min, 8,00 min. a) Sestav tabulku, do níž zaznamenáš příslušné časy. 46


SOUTĚŽE

b) Urči rychlost soutěžících v jednotlivých fázích pohybu. c) Urči průměrnou rychlost soutěžících po celé trase. d) Kdyby vás zajímalo, kde soutěž proběhla, najděte si místo podle údajů: 50◦ 16 s.š., 16◦ 08 v.d., nejlépe na adrese www.mapy.cz. FO50G5 Nedělní výlet s kamarádem (projekt pro sedmáky) Naplánuj trasu pro nedělní (polodenní nebo celodenní) výlet pěšky, na kole, vlakem, autobusem, autem aj. Pro přípravu použij mapu, autoatlas nebo internet – www.mapy.cz, kde najdeš různé mapy: základní, z leteckého snímkování, turistickou. Pro volbu trasy zvol buď svou fantazii nebo funkci Plánovač tras. Formuluj alespoň pět problémů o pohybu, které dovedeš vyřešit se svými znalostmi ze školní fyziky. FO50G6 Hmotnosti mincí a) Hodnota mince naší měnové soustavy je dána nominální (napsanou) hodnotou, pokud jde o mince běžné (starší mince nebo mince příležitostné mají hodnotu dánu trhem sběratelů). Dříve však se často používalo pravidlo: čím měla mince vyšší hmotnost, tím měla i vyšší hodnotu. Tvým úkolem proto bude porovnat hmotnosti mincí 1 Kč, 2 Kč, 5 Kč, 10 Kč, 20 Kč, 50 Kč. Aby to nebylo tak snadné, nebudeš mít zpočátku k dispozici přesné váhy a musíš určovat poměr hmotností jenom s použitím pravítka. Budeš moci využít špejle a režnou nit (nebo tenký provázek). Musíš vyřešit i to, že budeš porovnávat jen mince a na výsledek měření nesmí mít vliv hmotnost porovnávacího zařízení. b) Dokážeš metodou porovnávání hmotností stanovit plošný obsah rovinného obrazce nepravidelného tvaru? Pro ověření si vezmi nejprve lichoběžník, potom nepravidelný list. c) Je velmi obtížné stanovit plošný obsah vašeho kraje, kde žiješ, nebo naší republiky. Nešlo by ke stanovení použít také metody vážení?

Najdeš nás na Internetu: www.uhk.cz/fo http://fo.cuni.cz


47

PRO ŽÁKY ZÁKLADNÍCH ŠKOL Umíte sčítat přirozená čísla? Emil Calda, MFF UK Praha Abstract. In this article, the formula of the sum of the first n natural numbers is derived and then it is used in several examples which can be interesting not only for the pupils of basic school.

Co je to za otázku, říkáte si patrně, vždyť přirozená čísla umějí sčítat už děti v první třídě! Ano, dovedou, ale jen když počet sčítanců je konkrétní přirozené číslo, např. 2, 3, 4, 5 apod. Znáte snad nějakého prvňáka, který umí určit součet přirozených čísel, jejichž počet konkrétní přirozené číslo není? Kolik je žáčků, kteří dovedou určit součet všech přirozených čísel, která jsou větší než k a menší než m, kde k, m jsou přirozená čísla, k < m? Asi velmi málo, jsou-li vůbec takoví. Protože však vy už máte první třídu určitě za sebou, můžete se pokusit určit součty tohoto typu v následujících příkladech. Úloha 1. Určete součet prvních n přirozených čísel, tj. součet sn = 1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n. Řešení: Za tím účelem napíšeme pod tento řádek součet sn ještě jednou, ale v opačném pořadí sčítanců: sn = sn =

1 n

+ 2 + 3 + · · · + (n − 2) + (n − 1) + + (n − 1) + (n − 2) + · · · + 3 + 2 +

n 1

Sečteme-li sčítance stojící nad sebou, dostaneme 2sn = (n + 1) + (n + 1) + (n + 1) + · · · + (n + 1) + (n + 1) + (n + 1), neboli 2sn = n(n + 1), tj. sn =

n(n+1) . 2

Odvodili jsme tak, že platí

1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n = 48

n(n + 1) . 2


PRO ŽÁKY ZÁKLADNÍCH ŠKOL

Tento vzorec je zvláštní případ obecného vzorce pro součet prvních n členů aritmetické posloupnosti, který si odvodíte na střední škole. Zde se také možná dovíte, že výše popsaným způsobem (bez použití odvozeného vzorce) sečetl jako malý žáček prvních sto přirozených čísel budoucí slavný matematik Karl Friedrich Gauss (1777–1855). Poznámka: Chcete-li například určit součet prvních 2n přirozených čísel, což budeme zanedlouho potřebovat, nemusíte uvedený postup opakovat! Stačí v odvozeném vzorci nahradit číslo n číslem 2n a pro hledaný součet = n(2n+1). prvních 2n přirozených čísel dostanete, že je roven 2n(2n+1) 2 Úloha 2. Určete součet prvních n sudých přirozených čísel, tj. součet 2 + 4 + 6 + · · · + (2n − 4) + (2n − 2) + 2n. Řešení: Z tohoto součtu vytkneme číslo dvě a s použitím odvozeného vzorce pro součet prvních n přirozených čísel snadno dostaneme 2[1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n] =

2n(n + 1) = n(n + 1). 2

Tím jsme zjistili, že platí 2 + 4 + 6 + · · · + (2n − 4) + (2n − 2) + 2n = n(n + 1). Úloha 3. Určete součet prvních n lichých přirozených čísel, tj. součet 1 + 3 + 5 + · · · + (2n − 5) + (2n − 3) + (2n − 1). Řešení: Hledaný součet určíme tak, že od součtu prvních 2n přirozených čísel odečteme součet prvních n čísel sudých: 1 + 3 + 5 + · · · + (2n − 5) + (2n − 3) + (2n − 1) = = [1 + 2 + 3 + 4 + 5 + · · · + (2n − 4) + (2n − 3) + (2n − 2) + (2n − 1) + 2n]− − [2 + 4 + · · · + (2n − 4) + (2n − 2) + 2n] = = n(2n + 1) − n(n + 1) = n2 Odvodili jsme zajímavý výsledek: Součet prvních n lichých přirozených čísel je roven číslu n2 . Ročník 84 (2009), číslo 1

49


Úloha 4. Ukažte, že zlomek, v jehož čitateli je součet prvních n lichých přirozených čísel a ve jmenovateli součet n lichých přirozených čísel, která následují po posledním čísle čitatele, je pro všechna n roven jedné třetině. Řešení: Ověřme si nejprve toto tvrzení např. pro n = 4. Utvoříme-li uvedený zlomek, dostaneme 1+3+5+7 16 1 = = . 9 + 11 + 13 + 15 48 3 Ukážeme, že tento výsledek platí pro libovolné přirozené číslo n. Čitatele zkoumaného zlomku už znáte, je to číslo 1 + 3 + 5 + · · · + (2n − 3) + (2n − 1) = n2 . Určíme nyní jeho jmenovatele, kterým je součet n lichých přirozených čísel následujících po číslu 2n − 1. Jaký sčítanec tohoto součtu bude poslední, tj. n-tý? Protože první sčítanec je číslo 2n + 1, druhý je číslo 2n + 3, třetí 2n + 5 atd., bude n-tým sčítancem číslo 2n + (2n − 1). Ve jmenovateli uvažovaného zlomku bude tedy součet (2n + 1) + (2n + 3) + (2n + 5) + · · · + [2n + (2n − 1)] = = (2n + 2n + 2n + · · · + 2n) + [1 + 3 + 5 + · · · + (2n − 1)]. Uvědomte si dále, že číslo 2n se v součtu před hranatou závorkou vyskytuje celkem n-krát (neboť sčítáme n sčítanců) a že součet n stejných sčítanců rovných 2n je n · 2n = 2n2 . Snadno tak zjistíte, že hledaný jmenovatel zlomku je 2n2 + [1 + 3 + 5 + · · · + (2n − 1)] = 2n2 + n2 = 3n2 . Zjistili jsme tak, že uvažovaný zlomek má tvar přirozená čísla n je vskutku roven 13 .

n2 3n2 ,

takže pro všechna

Úloha 5. Určete součet všech přirozených čísel n, pro která platí n ≥ k a zároveň n ≤ m, kde k, m jsou přirozená čísla, k < m. Řešení: Hledanou hodnotu s určíme jako rozdíl dvou součtů, který jsme počítali v úloze 1, tedy s = k +(k +1)+· · ·+m = (1+2+3+· · ·+m)−[1+2+3+· · · +(k −1)] = = sm − sk−1 , 50



kde sm je součet všech přirozených čísel menších nebo rovných číslu m a sk−1 je součet všech přirozených čísel menších nebo rovných číslu k − 1. Pro hledaný součet s tak dostaneme m2 − k2 + (m + k) m(m + 1) − (k − 1)k = = 2 2 (m + k)(m − k + 1) (m + k)(m − k) + (m + k) = . = 2 2

s = sm − sk−1 =

Ověřme tento výsledek např. pro k = 5, m = 10. Součet čísel 5, 6, 7, = 45, což platí: 5 + 6 + 7 + 8 + 9 + 10 = 45. 8, 9, 10 má být (10+5)(10−5+1) 2 Úloha 6. Z čísel 12 , 22 , . . . , n2 jsme sestavili výraz 12 − 22 + 32 − 42 + 52 − · · · Určete jeho hodnotu pro a) n liché, b) n sudé. Řešení: a) Je-li n liché, má daný výraz tvar 12 − 22 + 32 − 42 + 52 − · · · − (n − 1)2 + n2 = = n2 − (n − 1)2 + · · · + 52 − 42 + 32 − 22 + 12 . Tento výraz upravíme tak, že ze sousedních členů vytvoříme dvojice, a protože n je liché, zůstane po jejich vytvoření osamocený“ člen 12 : ” 2 2 2 2 n − (n − 1) + · · · + (5 − 4 ) + (32 − 22 ) + 12 Po dalších úpravách dostaneme [n − (n − 1)][n + (n − 1)] + · · · + (5 − 4)(5 + 4) + (3 − 2)(3 + 2) + 1 = n(n + 1) = n + (n − 1) + · · · + 5 + 4 + 3 + 2 + 1 = . 2 Zjistili jsme, že pro všechna lichá n platí 12 − 22 + 32 − 42 + 52 − · · · − (n − 1)2 + n2 =

n(n + 1) . 2

= 28 Ověřme tento výsledek např. pro n = 7: 7(7+1) 2 1 − 22 + 32 − 42 + 52 − 62 + 72 = 1 − 4 + 9 − 16 + 25 − 36 + 49 = 28. 2


51


b) Je-li n sudé, má daný výraz tvar 12 − 22 + 32 − 42 + 52 − · · · + (n − 1)2 − n2 = = 12 + (32 − 22 ) + (52 − 42 ) + · · · + (n − 1)2 − (n − 2)2 − n2 . Jeho dalšími úpravami dostaneme 12 + (3 − 2)(3 + 2) + (5 − 4)(5 + 4) + · · · + + [(n − 1) − (n − 2)][(n − 1) + (n − 2)] − n2 = = 1 + (3 + 2) + (5 + 4) + · · · + [(n − 1) + (n − 2)] − n2 = = [1 + 2 + 3 + 4 + 5 + · · · + (n − 2) + (n − 1)] − n2 = =

n(n + 1) n(n − 1) − n2 = − . 2 2

Zjistili jsme tak, že pro všechna sudá n platí 12 − 22 + 32 − 42 + 52 − · · · + (n − 1)2 − n2 = −

n(n + 1) . 2

Ověřme tento výsledek např. pro n = 8: − 8(8+1) = −36 2 1 − 22 + 32 − 42 + 52 − 62 + 72 − 82 = 28 − 64 = −36. 2

Na závěr článku vám předkládáme problém na rozmyšlenou. Podotýkáme, že to není úloha jednoduchá. Pokud bude vaše počínání úspěšné, budeme rádi, když nám do redakce zašlete nějaký článek na toto téma. Úloha 8. Většina přirozených čísel je součtem dvou nebo více po sobě jdoucích přirozených čísel, například 24 = 7 + 8 + 9 nebo 51 = 25 + 26. Číslo 16 tuto vlastnost nemá. Která další čísla ji rovněž nemají?

Literatura [1] Calda, E.: Sbírka řešených úloh – Středoškolská matematika pod mikroskopem, Prometheus, Praha, 2006.

52


ZPRÁVY 49. Mezinárodní matematická olympiáda Karel Horák, MÚ AV ČR, Praha Hlavními organizátory 49. mezinárodní matematické olympiády, která se konala od 10. do 22. července v hlavním městě Španělska, Madridu, bylo španělské Ministerstvo školství a sociální politiky a Královská matematická společnost Španělska. Organizátoři připravili pro práci mezinárodní jury, jejímž hlavním úkolem je vybrat z připravených návrhů šestici soutěžních úloh, vynikající podmínky v kouzelném městečku San Ildefonso-La Granja v srdci Kastílie nedaleko Segovii (asi 80 km severozápadně od Madridu). Příjemnou nadmořskou výšku v blízkosti královského paláce a nádherných zahrad jsme dvojnásob ocenili po přesunu do rozpálených ulic Madridu, kam se mezitím sjel rekordní počet 535 soutěžících z 97 zemí celého světa (spolu s pozorovateli z Beninu a Sýrie a zástupci Pákistánu, jejichž studenti zůstali letos bohužel doma, když jim španělská ambasáda neposkytla včas víza, dosáhl počet formálně zúčastněných zemí stovky). Letošní olympiádu zahájila cirkusová show za zvuků Fučíkova Vjezdu gladiátorů. Úvodní hrozba moderátora, že dnes se spojí cirkusový svět ” se světem matematiky“, snad našla naplnění jen během úvodního defilé s národními vlajkami. České družstvo, které bylo vybráno na základě výsledků ústředního kola 57. ročníku MO v Českých Budějovicích a následné týdenní přípravy v Kostelci nad Černými lesy, tvořili Tomáš Hřebejk z 8. ročníku Gymnázia v Praze 4, Miroslav Klimoš z 3. ročníku Gymnázia Mikuláše Koperníka v Bílovci, Jan Matějka ze 7. ročníku Gymnázia v Českých Budějovicích v Jírovcově ulici, Samuel Říha ze 3. ročníku Gymnázia na tř. Kpt. Jaroše v Brně, Josef Tkadlec a Jakub Töpfer, oba ze 7. ročníku Gymnázia Jana Keplera v Praze 6. Vedoucím družstva byl RNDr. Karel Horák, CSc., z Matematického ústavu Akademie věd v Praze a studenty doprovázel RNDr. Martin Panák, Ph.D., z Přírodovědecké fakulty Masarykovy univerzity v Brně. Vlastní soutěž se odehrála v jedné obrovské aule 16. a 17. července, kdy soutěžící jako obvykle řešili vždy po trojici soutěžních úloh. Na to Ročník 84 (2009), číslo 1

53

ZPRÁVY

měli pokaždé vyhrazeno přesně 4,5 hodiny; za každou ze šesti úloh mohli získat nejvýše 7 bodů. Naši reprezentanti podali standardní výkon (až na jednoho vyřešili všichni nejlehčí první úlohu a skoro stejně dobře se vypořádali i s druhou z lehčích úloh – úlohou čtvrtou). Jediný, kdo si v každém soutěžním dnu poradil se dvěma úlohami, byl Miroslav Klimoš, který tak po bronzu ze 48. MMO rozšířil svou sbírku o stříbrnou medaili. Další medaili pro náš tým získal Josef Tkadlec, od něhož jsme však po vítězství v celostátním kole čekali trochu víc. Výsledky našich jsou shrnuty v následující tabulce: Body za úlohu Body Cena Umístění 1 2 3 4 5 6 424.–447. Tomáš Hřebejk 1 0 0 4 0 0 5 64.–70. Miroslav Klimoš 7 7 0 7 7 0 28 II. 268.–283. Jan Matějka 7 2 0 4 1 0 14 HM 368.–391. Samuel Říha 7 0 0 1 0 0 8 HM 212.–237. Josef Tkadlec 7 1 0 6 1 1 16 III. 268.–283. Jakub Töpfer 7 0 0 7 0 0 14 HM Celkem 36 10 0 29 9 1 85 Další tři naši studenti se museli spokojit pouze se základním oceněním, kterým je tzv. Honorary mention a které se uděluje studentům bez medaile za úplné vyřešení alespoň jedné z nelehké šestice soutěžních úloh; jejich obtížnost si konečně můžete ověřit sami. Pro srovnání uveďme i výsledky slovenských reprezentantů. Body za úlohu Body Cena Umístění 1 2 3 4 5 6 407.–423. Miroslav Baláž 2 0 0 4 0 0 6 346.–367. Albert Herencsár 5 0 0 4 0 0 9 284.–296. Tomáš Kocák 7 1 0 4 1 0 13 HM 238.–267. Filip Sládek 7 1 0 7 0 0 15 III. 199.–211. Michal Spišiak 7 2 0 7 1 0 17 III. 212.–237. Vladislav Ujházi 5 4 0 7 0 0 16 III. Celkem 33 8 0 33 2 0 76 V neoficiálním pořadí všech zúčastněných zemí jsme jen taktak obhájili pozici v první čtyřicítce (spolu s Argentinou a Řeckem jsme se podělili o 39.–41. příčku). Počet získaných cen a celkový bodový zisk jednotlivých zemí vyčtete z připojené tabulky (čísla v závorce označují nižší počet reprezentantů): 54


ZPRÁVY 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.–18. 19. 20.–21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33.–34. 35. 36. 37. 38. 39.–41.

42. 43. 44. 45. 46.–47. 48.–49.

ČLR Rusko USA Korea Írán Thajsko KLDR Turecko Tchaj-wan Maďarsko Japonsko Vietnam Polsko Bulharsko Ukrajina Brazílie Peru Rumunsko Austrálie Německo Srbsko Kanada Velká Británie Itálie Kazachstán Bělorusko Izrael Hongkong Mongolsko Francie Indie Singapur Nizozemsko Uzbekistán Litva Indonézie Mexiko Chorvatsko Argentina Česká republika Řecko Gruzie Španělsko JAR Kolumbie Slovensko Turkmenistán Ázerbájdžán Moldavsko

I 5 6 4 4 1 2 2 3 2 2 2 2 2 2 2 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


II 1 0 2 2 5 3 4 1 4 3 3 2 3 1 2 5 3 4 5 2 3 2 4 3 2 3 1 3 2 1 0 1 2 0 1 1 1 0 1 1 0 0 0 1 2 0 0 0 1

III 0 0 0 0 0 1 0 2 0 1 1 2 1 3 2 1 2 2 1 3 0 4 2 3 3 2 2 1 1 4 5 3 2 4 2 2 1 3 3 1 2 5 3 0 0 3 4 3 0

b. 217 199 190 188 181 175 173 170 168 165 163 159 157 154 153 152 141 141 140 139 139 135 133 132 128 125 120 107 106 104 103 98 94 94 92 88 87 86 85 85 85 84 82 79 77 76 76 74 74

50.–52. Bosna a Hercegovina Slovinsko Švýcarsko 53. Švédsko 54. Dánsko 55.–56. Kostarika Malajsie 57. Rakousko 58. Norsko 59.–60. Belgie Makedonie 61.–62. Lucembursko (5) Tádžikistán 63.–65. Lotyšsko Macao Maroko 66. Arménie 67. Portugalsko 68. Albánie 69. Chile (3) 70. Irsko 71.–72. Kypr Nový Zéland 73. Estonsko 74. Finsko 75. Bangladéš (4) 76.–77. Island (5) Salvador (4) 78. Srí Lanka 79.–80. Kirgizie (5) Trinidad a Tobago 81. Kuba (1) 82. Ekvádor 83. Kambodža 84.–85. Černá hora (3) Paraguay (4) 86. Filipíny (3) 87. Uruguay (5) 88. Tunisko (4) 89. Honduras (2) 90.–92. Guatemala (4) Lichtenštejnsko (2) Venezuela (2) 93. Portoriko (3) 94. Saudská Arábie 95.–96. Bolívie (5) SAE (4) 97. Kuvajt (5)

I 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

II 0 0 1 1 2 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

III 3 2 1 0 0 2 0 1 0 1 2 2 1 0 2 1 0 2 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0

b. 68 68 68 67 66 65 65 63 62 61 61 60 60 58 58 58 56 55 53 49 45 42 42 41 40 33 31 31 29 28 28 27 26 25 24 24 23 22 20 17 16 16 16 9 8 5 5 3

55

ZPRÁVY

Vynikající organizace se projevila i v bohaté náplni volného času jak studentů, tak jejich vedoucích. O tom svědčí zejména výlety do Segovii (která se kromě jiného může pochlubit i zbytky nádherného římského akvaduktu), El Escorialu a Toleda, v Aranjuez návštěva kulturního večera s vynikající představitelkou tradičního flamenca Mercedes Ruiz, pro studenty pak navíc možnost navštívit v Madridu světoznámou galerii Prado i dlouhá řada soutěží a dalších aktivit. Slavnostního zakončení olympiády v aule Univerzity Carlose III. se mimo jiné zúčastnilo i Jeho královské veličenstvo princ Felipe de Asturias se svou chotí princeznou Letiziou. Spolu s dalšími představiteli rozdali celkem 267 medailí všem, kteří v nelehkém klání získali alespoň 15 bodů. Mezi nimi bylo 100 studentů, kteří za 22–30 bodů získali stříbrnou medaili, a 47 nejúspěšnějších, kteří za zisk alespoň 31 bodu byli oceněni medailí zlatou. Mezi nimi vynikli tři Číňani, Xiaosheng Mu, Dongyi Wei (oba ČLR) a Alex Zhai (USA), kteří bezchybně vyřešili všech šest úloh. Hostitelskými zeměmi příštích olympiád budou Německo (jubilejní 50. ročník), Kazachstán, Holandsko a Argentina. Texty soutěžních úloh (v závorce je uvedena země, která úlohu navrhla) 1. V ostroúhlém trojúhelníku ABC označme H průsečík výšek. Kružnice procházející bodem H se středem ve středu strany BC protíná přímku BC v bodech A1 a A2 . Podobně kružnice procházející bodem H se středem ve středu strany CA protíná přímku CA v bodech B1 a B2 a kružnice procházející bodem H se středem ve středu strany AB protíná přímku AB v bodech C1 a C2 . Ukažte, že body A1 , A2 , B1 , B2 , C1 , C2 leží na jedné kružnici. (Rusko) 2. (a) Dokažte, že y2 z2 x2 + + ≥1 (x − 1)2 (y − 1)2 (z − 1)2 pro všechna reálná čísla x, y, z různá od 1 a splňující rovnost xyz = 1. 56


ZPRÁVY

(b) Dokažte, že v uvedené nerovnosti platí rovnost pro nekonečně mnoho trojic racionálních čísel x, y, z různých od 1 a splňujících rovnost xyz = 1. (Rakousko) 3. Dokažte, že existuje nekonečně mnoho kladných celých čísel n, pro √ (Litevsko) něž má číslo n2 + 1 prvočinitel větší než 2n + 2n. 4. Najděte všechny funkce f : (0, ∞) → (0, ∞) takové, že 2 2 f (w) + f (x) w 2 + x2 = f (y 2 ) + f (z 2 ) y2 + z2 pro všechna kladná reálná čísla w, x, y, z splňující rovnost wx = yz. (Jižní Korea) 5. Nechť n a k jsou kladná celá čísla, kde k ≥ n a k − n je sudé číslo. Je dáno 2n lamp označených čísly 1, 2, . . . , 2n, přičemž každá z nich může být zapnutá či vypnutá. Na počátku jsou všechny lampy vypnuté. Uvažujme posloupnosti kroků: v každém kroku jednu z lamp přepneme (vypnutou zapneme či zapnutou vypneme). Označme N počet všech takových posloupností k kroků, jež vedou do stavu, kdy všechny lampy 1 až n jsou zapnuté a všechny lampy n + 1 až 2n jsou vypnuté. Označme M počet všech takových posloupností k kroků, jež vedou do stavu, kdy všechny lampy 1 až n jsou zapnuté a všechny lampy n + 1 až 2n jsou vypnuté, přičemž žádná z lamp n + 1 až 2n nebyla nikdy zapnutá. Určete podíl N/M . (Francie) 6. Nechť ABCD je konvexní čtyřúhelník, v němž |BA| = |BC|. Označme ω1 a ω2 kružnice vepsané trojúhelníkům ABC a ADC. Předpokládejme, že existuje kružnice ω, jež se dotýká polopřímky BA za bodem A, polopřímky BC za bodem C a zároveň i obou přímek AD a CD. Dokažte, že společné vnější tečny kružnic ω1 a ω2 se protínají v bodě kružnice ω. (Rusko)


57

ZPRÁVY

Mezinárodní olympiáda v informatice IOI 2008 Daniel Kráľ, MFF UK Praha Loňský ročník Mezinárodní olympiády v informatice (IOI), který byl jubilejní dvacátý v pořadí, se uskutečnil ve dnech 16. – 23. srpna 2008 v egyptském hlavním městě Káhiře. Soutěže se zúčastnilo 283 soutěžících ze 78 zemí celého světa; většina zemí využila možnosti vyslat na IOI maximální povolený počet čtyř soutěžících. Výběr našich soutěžících pro IOI byl proveden na základě výsledků dosažených soutěžícími v ústředním kole 57. ročníku Matematické olympiády – kategorie P, které se uskutečnilo v březnu 2008 v Českých Budějovicích a o jehož průběhu jsme vás již na stránkách Rozhledů informovali. Naše družstvo pro IOI 2008 mělo následující složení: Miroslav Klimoš (student gymnázia M. Koperníka v Bílovci), Jan Matějka (student gymnázia Jírovcova v Českých Budějovicích), Roman Smrž (absolvent gymnázia E. Krásnohorské v Praze) a Vojtěch Tůma (absolvent gymnázia J. Masaryka v Jihlavě); vedoucími české delegace byli jmenováni RNDr. Daniel Kráľ, Ph.D. a Bc. Tomáš Gavenčiak , oba z Matematicko– fyzikální fakulty Univerzity Karlovy v Praze. Soutěže se též zúčastnil Mgr. Martin Mareš, Ph.D., rovněž pracovník MFF UK v Praze, a to jako člen Mezinárodního vědeckého výboru IOI. Oficiálními pořadateli letošního ročníku IOI bylo egyptské ministerstvo školství a ministerstvo informačních a komunikačních technologií. Čestnou záštitu nad soutěží převzal egyptský prezident Husny Mubarak. Ubytování a stravování soutěžních týmů bylo zajištěno ve vzdělávacím komplexu Mubarak Education City v nově budované čtvrti káhirské metropole 6 October City, kde též proběhla samotná soutěž i oficiální zahájení a ukončení soutěže. Soutěž IOI měla bohatý doprovodný kulturní a společenský program, který zahrnoval projížďku po Nilu, návštěvu pyramid v Gize a Egyptského muzea v Káhiře nebo výlet na pláž u Rudého moře. Jako zajímavost uveďme, že vyhlášení soutěže proběhlo již předposlední den soutěže, a to již ve čtvrtek 21. srpna 2008, neboť pátek je dle islámské tradice volným dnem. Mezinárodní olympiáda v informatice je soutěží jednotlivců a samotná soutěž probíhá ve dvou soutěžních dnech. V každém soutěžním dni je účastníkům předložena sada tří úloh, na jejichž vyřešení měl každý sou58


ZPRÁVY

těžící vymezen čas 5 hodin. Abychom naše studenty na soutěž dobře připravili, pořádáme každoročně přípravné soustředění společně s organizátory polské a slovenské olympiády v informatice. Letos se toto přípravné soustředění, jehož průběh odpovídá soutěžním standardům IOI, uskutečnilo ve slovenských Danišovcích. Letošní sada úloh byla velmi obtížná, o čemž svědčí fakt, že k získání bronzové medaile stačilo pouhých 127 bodů ze 600 možných a 26 soutěžících nezískalo vůbec žádný bod. Řešení odevzdaná soutěžícími byla testována pomocí softwaru vyvinutého pro polskou olympiádu v informatice na předem připravených testovacích datech se stanovenými časovými limity. Použití časových limitů umožňuje odlišit kvalitu (rychlost) použitého algoritmu. Zadání úloh zaručuje, že i neoptimální řešení získají jisté množství bodů. A jaké byly výsledky soutěže? Podle pravidel obdrží polovina soutěžících medaili a počty zlatých, stříbrných a bronzových medailí se určí tak, aby jejich počet byl v poměru 1 : 2 : 3. Letos bylo uděleno 24 zlatých, 47 stříbrných a 70 bronzových medailí. I přes zmiňovanou obtížnost úloh se dvěma našim soutěžícím podařilo získat stříbrné medaile. Výsledky našich studentů byly následující: 47. místo

Miroslav Klimoš

267 bodů

stříbrná medaile

71. místo

Roman Smrž

229 bodů

stříbrná medaile

197. místo

Jan Matějka

53 bodů

219. místo

Vojtěch Tůma

33 bodů

Protože IOI je soutěží jednotlivců, žádné oficiální pořadí zemí se neurčuje. Z hlediska počtu a kvality získaných medailí bychom se v hodnocení národních delegací umístili přibližně v druhé čtvrtině zúčastněných zemí; nejúspěšnějšími zeměmi byly již tradičně ČLR a Polsko (se 3 zlatými a 1 stříbrnou medailí) a Rusko a USA (se 2 zlatými a 2 stříbrnými medailemi). Soutěžícím ze Slovenska se tentokrát vedlo o něco lépe než nám a získali v soutěži dvě stříbrné a dvě bronzové medaile. Podrobnější informace o soutěži, včetně fotografií z průběhu soutěže, texty soutěžních úloh a celkové výsledky všech účastníků lze nalézt na Internetu na adrese http://www.ioi2008.org/. Následující ročník IOI se bude konat v srpnu 2008 v bulharském Plovdivu a další ročníky pak v Kanadě, Thajsku a Itálii. Ročník 84 (2009), číslo 1

59

ZPRÁVY

Na závěr si ještě uveďme jednu z úloh prvního soutěžního dne. Jedná se o středně obtížnou úlohu, která se na mezinárodních soutěžích v informatice vyskytuje. Ostrovy Rozhodli jste se navštívit zábavný zábavní park rozkládající se na N ostrovech. Při budování parku začali z každého ostrova stavět jeden most na některý jiný ostrov. Po dokončení stavby je tedy v parku N mostů a na některé ostrovy vede více mostů. Délka mostu stavěného z i-tého ostrova je Li . Každý z mostů lze používat v obou směrech. Kromě toho v parku také funguje mezi každou dvojicí ostrovů přívoz. Protože jste velmi rychle zjistili, že nejzábavnější atrakcí v parku je chůze po dlouhatánských mostech, rádi byste po nich v parku ušli co největší vzdálenost. Při vašem pohybu v parku se však chcete řídit následujícími pravidly: • Svou návštěvu můžete začít na vámi vybraném ostrově. • Žádný ostrov nenavštívíte více než jednou. • Z ostrova A se můžete (přímo) přesunout na ostrov B, který jste dosud nenavštívili, a to jedním ze dvou následujících způsobů: ◦ Chůzí po mostě , pokud mezi ostrovy A a B vede most. V tomto případě je délka tohoto mostu (v případě dvou souběžných mostů délka delšího z nich) přičtena k celkové vzdálenosti, kterou jste už ušli po mostech. ◦ Přívozem, pokud ostrov B není dosažitelný z ostrova A pomocí mostů a přívozů, které jste již během své návštěvy parku použili. (Při rozhodování o dosažitelnosti ostrova B z A uvažujte i cesty vedoucí přes již navštívené ostrovy.) Vaším úkolem není navštívit všechny ostrovy. Podobně nemusí být možné projít přes všechny mosty. Úkol Vaším úkolem je napsat program, který z popisu N mostů v parku určí nejdelší možnou vzdálenost, kterou lze po mostech ujít při dodržení výše uvedených podmínek. Omezení 2 ≤ N ≤ 1 000 000, 1 ≤ Li ≤ 100 000 000, 60

počet ostrovů v parku délka mostu vystavěného z i-tého ostrova Rozhledy matematicko-fyzikální

ZPRÁVY

Popis vstupu Váš program načte ze standardního vstupu data v následujícím tvaru: • První řádek obsahuje celé číslo N , které udává počet ostrovů v parku. Ostrovy jsou očíslovány čísly od 1 do N (včetně). • Každý z následujících N řádků popisuje jeden z mostů; i-tý z těchto řádků obsahuje dvě celá čísla oddělená jednou mezerou a popisuje most vystavěný z ostrova číslo i. První z těchto dvou čísel je číslo ostrova, kam most vede, druhé je jeho délka Li . Můžete předpokládat, že každý most spojuje dva různé ostrovy. Popis výstupu Váš program zapíše na standardní výstup (na jediném řádku) jedno číslo, které udává největší možnou vzdálenost, kterou můžete v parku po mostech ujít. Poznámka 1: Pro některé testovací vstupy výsledná hodnota překročí rozsah 32bitového celočíselného typu a k získání plného počtu bodů za tuto úlohu je nutné použít 64bitové typy (int64 v Pascalu a long long v C/C++). Poznámka 2: Programy v jazyce Pascal, které používají k načtení vstupu 64bitové datové typy, jsou výrazně pomalejší než stejné programy používající 32bitové typy, a to i tehdy, když načítané hodnoty nepřekročí rozsah 32bitových celočíselných typů. Doporučujeme tedy k načtení vstupu používat pouze 32bitové celočíselné typy. Bodování U testovacích vstupů v hodnotě alespoň 40 bodů hodnota N nepřekročí 4 000.


61

NAŠE SOUTĚŽ NAŠE SOUTĚŽ V letošním ročníku v Rozhledech matematicko-fyzikálních otvíráme rubriku Naše soutěž . Není to úplně nová rubrika, protože v minulých letech měli čtenáři možnost otvírat rubriku se stejným názvem. Byla dlouholetou součástí Rozhledů v podstatě od jejich vzniku, v roce 1991 se ale její kontinuita přerušila. V Naší soutěži budete nacházet dvojici úloh, většinou jedna bude matematická, druhá fyzikální. Budeme rádi, pokud některou z úloh vyřešíte a pošlete na adresu redakce její řešení. Řešení může být v elektronické či papírové podobě. Redakce vaše řešení opraví a opravené vám je zašle zpět. V některém z následujících čísel pak najdete úlohy vyřešené. Vaše řešení budeme bodovat – za každou úlohu můžete obdržet maximálně 5 bodů. Výsledky jednotlivých řešitelů budeme sčítat a povedeme průběžnou výsledkovou tabulku. Budeme sčítat výsledky za všechny úlohy, nebudeme tedy rozlišovat matematiku od fyziky. Vždy zveřejníme jména všech řešitelů a průběžné výsledky. Nejlepším řešitelům bude s roční periodou zaslána matematická literatura. Nyní vám tedy předkládáme první dvě úlohy. Její řešení pošlete do 30. května 2009 na adresu redakce. Úloha 1. V lichoběžníku ABCD je K střed základny AB a L střed základny CD. Dokažte, že lichoběžníku AKLD lze opsat kružnici, právě když tg α = 3 tg β, kde α a β jsou vnitřní úhly při vrcholech A a B lichoběžníku. (Jaroslav Zhouf ) Úloha 2. Na hladkém vodorovném ledě leží dva klíny o hmotnostech M1 a M2 , jejichž úhly sklonu jsou 45◦ (obr. 1). Na první klín dopadne volným pádem kulička o hmotnosti m z výšky h0 . Tato kulička se od klínu dokonale pružně odrazí a dopadne na druhý klín, kde opět dojde k dokonale pružné srážce s klínem. Kulička potom vystoupí do výšky h. a) Určete poměr výšek hh0 . b) Určete rychlost, s jakou se od sebe klíny vzdalují po odrazu kuličky od druhého klínu. 62


NAŠE SOUTĚŽ

m

h0

M2

h

M1 45◦

45◦ Obr. 1

Řešte nejprve obecně, potom pro hodnoty M1 = 10, m

M2 = 2, M1

h0 = 0,5 m,

Tření mezi ledem a klíny zanedbejte.

g = 10 m · s−2 . (Miroslava Jarešová)

∗ ∗ ∗ ∗ ∗ BINOMICKÁ VĚTA Setkal jsem se na Hradčanech před Dómem se svým starým dobrým známým binómem. Prohodili jsme spolu pár binomických vět, jak se nám od doby mládí značně změnil svět, že už dneska ženský nejsou, co bejvaly dřív, a že bude nejlíp zajít někam na pár piv. Na ten večer vzpomínám pln dojetí, jak jsme se tam umocnili na třetí! Emil Calda*)

*) Úvod do obecné teorie prostoru, Karolinum, Praha, 2003 Ročník 84 (2009), číslo 1

63

NÁVODY A ODPOVĚDI Odmocniny z přirozených čísel“ ” √ 1. Z rovnosti (b − 3) a = 4(b − 3) plyne b = 3 nebo a = 16. √ √ √ 2 2. Z √rovnosti a+ b = n upravené do tvaru 2n a = n +a−b plyne, že a je racionální, a tedy přirozené číslo (podle Tvrzení 1); analogicky √ pro číslo b. √ a+b 5 √ =x a+c 5 √ upravte na a(1−x) = (cx−b) 5, odkud cx−b = 0, a tedy a = 0 nebo x = 1. Řešením úlohy jsou trojice (a, b, c) tvaru (0, b, c), kde c = 0, a trojice tvaru (a, b, b), kde (a, b) = (0, 0).

3. Rovnost

4. Danou rovnost upravte na √ √ √ √ √

√

a+ b a− b =5 a− b , √ √ √ √ odkud plyne a − b = 0 (takže a = b) nebo a + b = 5. Poslední √ rovnost je (podle úlohy č. 2) splněna jedině v případech, kdy a, √ b je dvojice čísel 1, 4 nebo 2, 3 (v jakémkoliv pořadí). Řešením úlohy jsou tedy právě dvojice (a, b) tvaru (a, a), (1, 16), (16, 1), (4, 9) a (9, 4). √ √ 5. a) Ukažte, že pro čísla sn = (7 + 48)n + (7 − 48)n platí s0 = 2, s1 = 14 a sn+1 = 14sn − sn−1 pro každé n ∈ N. Odtud tvrzení úlohy již snadno plyne indukcí. √ √ √ √ √ √ n 3+ 2. Protože ( 3 + 2)( 3 − 2) = 1, b) Označme x = √ √ √ √ n n lze zkoumané číslo s = 3+ 2 + 3 − 2 zapsat ve tvaru s = x + x−1 . Připustíme-li, že číslo s je racionální, pak z rovností xk+1 + x−k−1 = xk + x−k x + x−1 − (xk−1 + x1−k ) pro k = 1, 2, . . . , n − 1 postupně dostaneme, že i čísla x2 + x−2 , x3 + což pro poslední z nich protiřečí x−3 , . . . , xn + x−n jsou racionální, √ zřejmé rovnosti xn + x−n = 2 3. 64


Úvodem k novému ročníku Rozhledů matematicko-fyzikálních

Recommend Documents