12
Studentský matematicko-fyzikální časopis Ročník Číslo XIX 1
Matematika
Fyzika S obsahem časopisu M&M je možné nakládat dle licence Creative Commons Attribution 3.0. Dílo smíte šířit a upravovat. Máte povinnost uvést autora. Autory textů jsou organizátoři M&M.
Informatika
Adresa redakce: M&M, OVVP, UK MFF Ke Karlovu 3 121 16 Praha 2 Telefon: +420 221 911 235 E-mail:
[email protected] WWW: http://mam.mff.cuni.cz Časopis M&M je zastřešen Oddělením pro vnější vztahy a propagaci Univerzity Karlovy, Matematicko-fyzikální fakulty a vydáván za podpory středočeské pobočky Jednoty českých matematiků a fyziků.
Časopis M&M a stejnojmenný korespondenční seminář je určen pro studenty středních škol, kteří se zajímají o matematiku, fyziku či informatiku. Během školního roku dostávají řešitelé zdarma čísla se zadáním úloh a témat k přemýšlení. Svá řešení odesílají k nám do redakce. My jejich příspěvky opravíme, obodujeme a pošleme zpět. Nejzajímavější řešení otiskujeme.
2
Milý příteli matematiky, fyziky a informatiky, chtěli bychom ti představit časopis a korespondenční seminář M&M určený především pro studenty středních škol. V jeho rámci se snažíme zábavnou formou prezentovat nejrůznější problémy z matematiky, fyziky a programování. Důraz přitom klademe na to, aby mohl každý o problémech sám uvažovat a potom společně s ostatními sdílet své závěry. V průběhu školního roku vychází zpravidla sedm čísel časopisu, ve kterých nabízíme nejrůznější úlohy a témata k zamyšlení i všelijaké články. První číslo držíš právě v ruce.
Úlohy V prvních šesti číslech uveřejňujeme samostatné úlohy. Tyto úlohy bývají trochu těžší než obvyklé školní, jejich řešení často vyžaduje nějaký trik. Středoškolské znalosti by k jejich vyřešení ale měly stačit. Pokud některou z úloh vyřešíš, pošli nám její řešení. My ho opravíme a zašleme zpět. V některém z dalších čísel vždy uveřejníme vzorová řešení zadaných úloh.
Témata Témata jsou obecněji zadané problémy. Vždy obsahují nějakou otázku a náměty, jak téma dále rozvíjet. Jsou především příležitostí hlouběji se ponořit do určitého problému a zkusit vymyslet něco vlastního. To je postup podobný skutečné věděcké práci. Můžeš nám poslat cokoli, co tě k tématu napadne. Zajímavé příspěvky otiskneme v některém z dalších čísel. Protože nad složitějšími problémy se lépe přemýšlí ve skupině, může příspěvek k tématu společně zaslat i více autorů, jako tomu je u skutečné vědecké práce.
Články Od druhého čísla budou v časopise vycházet redakční články, které se budou snažit přiblížit nějaké konkrétní odvětví matematiky, fyziky či informatiky. Pokud znáš něco, o čem si myslíš, že by ostatní mohlo zajímat, můžeš o tom sepsat článek i ty a zaslat nám ho. Pokud se nám bude líbit, rádi ho otiskneme.
Soutěž M&M není jen časopis, ale i soutěž. Za všechny vyřešené úlohy, příspěvky k tématům i články udělujeme body. U každé úlohy je uveden počet bodů za správné řešení. Přiměřenou část z těchto bodů lze získat i za neúplné řešení. U témat a článků žádná horní hranice stanovena není. Za dobrý příspěvek lze získat i 20 bodů. Na základě získaných bodů sestavujeme výsledkovou listinu. Nejlepší řešitele čekají knižní ceny. Především ale 20 až 25 nejúspěšnějších řešitelů zveme dvakrát do roka na soustředění.
Soustředění Vždy na jaře a na podzim připravujeme pro naše nejlepší řešitele týdenní soustředění, obvykle někde na horách. Soustředění je částečně odborné – máme pro
XIX/1
11
Zkuste zjistit, jaká všechna slova přijímají tyto automaty: 1
a 0
b
b
1
0
0
1
1
1
0
a
0
0
c
automat č. 1
0 1
1
c
0
c
b
a
1
automat č. 2
0 1
automat č. 3
Naším úkolem je navrhnout automat, který přijímá přesně ta slova, která chceme, aby přijímal. To si můžete vyzkoušet například na následujících příkladech. Navrhněte konečný automat nad abecedou Σ = {a, b}, který • přijímá pouze slova začínající abb, • přijímá pouze slova obsahující podřetězec baba, • přijímá pouze slova začínající abb nebo obsahující podřetězec baba. Zkuste vymyslet konečný automat nad abecedou Σ = {1, 0}, který přijímá právě slova reprezentující čísla • dělitelná třemi zapsaná v desítkové soustavě, • dělitelná pěti zapsaná v desítkové soustavě, • dělitelná třemi zapsaná v desítkové soustavě pozpátku, • dělitelná třemi zapsaná ve dvojkové soustavě, • dělitelná pěti zapsaná ve dvojkové soustavě. Malinko náročnější úkol pak je navrhnout konečný automat, který přijímá slova nad abecedou Σ = {1, 0} začínající znaky 11 následovanými dvojicemi znaků 00 nebo 11 (libovolně mnoha v libovolném pořadí), která mají počet jedniček dělitelný třemi. Zamysleme se nad automaty obecněji. Existuje vždy konečný automat, který přijímá požadovanou množinu slov (tuto množinu nazýváme jazyk)? Pokud bude jazyk konečný (obsahuje konečně mnoho slov), uměli byste příslušný automat sestrojit? Může existovat více různých konečných automatů, které přijímají stejný jazyk? Kuba
10 Konečný automat je „myšlený strojÿ, který o každém slovu, jež mu zadáme, rozhodne, jestli vyhovuje předem stanoveným kritériím. Pokud slovo vyhovuje, automat ho přijme, jinak nikoli. Automat postupně čte po znacích zadané vstupní slovo a podle přečtených znaků upravuje svůj vnitřní stav. Zajímá nás, v jakém stavu se automat nachází po přečtení celého slova. Zkusme se podívat na konečné automaty trochu podrobněji a formálněji. Vstupem do automatu je konečná (případně i prázdná) posloupnost znaků předem zvolené abecedy (množiny znaků) Σ. Této posloupnosti říkáme vstupní slovo. Automat je pak tvořen množinou stavů Q a popisem, ze kterého stavu má přejít do kterého, pro každý znak, jenž může dostat na vstupu. K tomu slouží přechodová funkce δ, které zadáme aktuální stav a znak ze vstupu. Funkce nám vrátí nový stav. Některé stavy jsou označeny jako koncové. Pokud automat skončí výpočet v koncovém stavu, je vstupní slovo přijato. V opačném případě nikoli. Na začátku výpočtu se automat nachází v pevně daném počátečním stavu q0 ∈ Q. Pak si vždy přečte jeden znak ze vstupního slova a přejde do příslušného stavu dle přechodové funkce. Když narazí na konec slova, skončí. Jestli dané slovo přijme, záleží na tom, jestli stav, ve kterém se aktuálně nachází, je koncový. U konečného automatu potřebujeme popsat především jeho stavy a přechodovou funkci. To můžeme udělat dvěma způsoby – stavovým diagramem nebo tabulkou . Stavový diagram je orientovaný ohodnocený graf, jehož vrcholy tvoří jednotlivé stavy, hrany pak přechody. Počáteční stav značíme šipkou k vrcholu. Koncové stavy šipkou z vrcholu ven. Následující automat pracuje nad abecedou Σ = {0, 1} a přijímá všechna slova, která končí 101. Celkem má čtyři stavy, z nichž jeden je počáteční (stav a) a jeden koncový (stav d).
1 0
a
1
1
b 0
0
c
1
d
0
Automat zadaný stavovým diagramem.
0
1
→a
a
b
b
c
b
c
a
d
←d
c
b
Tentýž automat zadaný tabulkou.
XIX/1
3
vás připraveny přednášky z nejrůznějších oblastí matematiky, fyziky i informatiky. Dost času je věnováno i rozmanitým hrám. Především je ale soustředění příležitost, jak potkat lidi s podobnými zájmy. Letošní podzimní soustředění se bude konat 13.–21. 10. 2012. Budeme na něj zvát nejlepší řešitele z minulého ročníku, ale i ty, kteří pošlou pěkná řešení úloh a témat z tohoto čísla. Budeme rádi, pokud nám společně se svými řešeními napíšeš, jestli bys na soustředění případně chtěl(a) jet.
Přijímací zkoušky na MFF Matematicko-fyzikální fakulta Univerzity Karlovy se rozhodla nejúspěšnějším řešitelům našeho korespondenčního semináře odpustit přijímací zkoušky. Konkrétně se to týká těch řešitelů, kteří získají za rok alespoň 85 bodů. Ti od nás dostanou „osvědčení úspěšného řešiteleÿ, které pak mohou předložit fakultě.
Jak se zapojit Pokud tě M&M zaujalo, stačí se pokusit vyřešit nějakou úlohu či téma a poslat nám své řešení. K řešení přilož prosím také své jméno, adresu, e-mail, školu a rok, kdy budeš maturovat. Pokud chceš jet na soustředění, uveď prosím i telefon. Tyto údaje budeme využívat pouze pro potřeby M&M. Mimo údajů na výsledkové listině (jméno, škola, ročník) je nebudeme nikde uveřejňovat. Svá řešení můžeš poslat buď elektronicky na náš e-mail
[email protected], nebo poštou na adresu M&M uvedenou na zadní straně. Každé řešení prosím piš na samostatný list (resp. pošli jako samostatný soubor), aby si úlohy mohli rozdělit různí opravující, a uveď své jméno a číslo úlohy či tématu. Na tvou poštovní adresu ti pak budou zdarma chodit další čísla našeho časopisu. Pokud by ses chtěl o M&M dozvědět více, podívej se na naše webové stránky http://mam.mff.cuni.cz, kde mimo jiné najdeš podrobná pravidla a archiv všech vydaných čísel za uplynulých 18 ročníků. Těšíme se na tvá řešení! organizátoři M&M
4
Zadání úloh Termín odeslání první série: 22. 10. 2012 (24. 9. 2012 pro účast na podzimním soustředění) Lidé, mužští i ženští, malí i velcí. Poslyšte dnes svůj příběh, jenž jste sami psali do historie světa. Když jste přišli na svět, ještě docela primitivní a chlupatí, žili jsme na zemi už tisíce let.
Úloha 1.1 – Tisíc
(1+3b)
(i) Součet několika (nejméně dvou) po sobě jdoucích přirozených čísel je 1000. Jaké největší číslo mezi nimi může být? (ii) Která všechna celá čísla lze zapsat jako součet dvou a nebo více po sobě jdoucích přirozených čísel?
XIX/1
9
jakou cestovní rychlostí (tzn. včetně zastavování) jezdí autobusy či tramvaje a jakou třeba vy na kole či koloběžce. Bydlíte-li mimo město, zkuste zjistit, jakou cestovní rychlost má autobus či vlak do blízkého města. Každý nápad se cení, pokud vám přijde, že byste napsali něco, co je úplně jasné, a přece to tedy nebudete psát, přesto to zkuste. Někdo to napsat musí a vy za to dostanete body. A třeba to nebude tak jasné, jak to vypadá. Pokud vás napadl způsob měření rychlosti, na který nemáte prostředky, popište nám ho. Pokud na něj budeme mít prostředky my, zrealizujeme ho a pošleme vám výsledky. Nebojte se využití moderních technik jiných než GPS s tím, že se to dá změřit snáze GPS. Nejen v metru, ale i v některých vlacích vám GPS nepomůže, zatímco jiné techniky by mohly. Přejeme vám hodně štěstí při měření a těšíme se na vaše výsledky. Jethro
Naučili jsme se tomu v souladu s přírodou. Namísto ustavičného spěchu jsme zakotvili v zemi. Naučili jsme se žít ze slunce a naši matku zemi neobírat o nic, využívajíce jen vodu a navracejíce ji do věčného koloběhu. Jen žlutému slunci a modré vodě vděčí naše zelené koruny za poklidný život, který nám umožnily. Vy, legračně se hemžící všude pod námi, jste zprvu kráčeli podobnou cestou. Využívali jste dary naší matky jen nakolik jste potřebovali a přeměňovali je na živiny, pro nás tolik potřebné. Tehdy jsme si rozuměli. Ale pak jste se změnili. Snad to bylo tím, že jste dennodenně spatřili veliký kus světa, o němž vaše hlavy přemýšlely, že se v nich začly rodit všelijaké nápady. Začali jste chtít. My neznáme „chtítÿ; vždyť co bychom chtěli, majíce vše, co potřebujeme? Vy jste chtěli „vícÿ. Naučili jste se ovládat nás, abychom rostli jen tam, kde si přejete. Naučili jste se ovládat druhé lidi a moc vám zachutnala. Vymysleli jste si věci nevídané: Po staletí jste hráli krutou, krvavou hru na krále a poddané (později na bohaté a chudé).
Úloha 1.2 – Kulatý stůl
(4b)
Mějme les, definovaný jako množina bodů v rovině (zadaný bod je středem stromu) a jejich poloměrů (poloměr může být u různých stromů různý). Uprostřed lesa stojí kulatý stůl krále Artuše (stejně jako stromy je zadán svým středem a poloměrem). Zajímá nás, jak dostat tento stůl z lesa ven, aniž bychom přitom museli pokácet nějaké stromy. Stůl není možné naklánět, aby se nepřevrhl Svatý grál postavený uprostřed. Navrhněte proto algoritmus, který ze zadaného lesa a stolu určí cestu, kudy dokážeme stůl z lesa vymanipulovat. Pokud to také bude cesta nejkratší, odměna navíc vás nemine.
Téma 3 – Konečné automaty V tomto tématu bychom vás chtěli seznámit s jedním teoretickým konceptem hojně využívaným v informatice, kterým jsou konečné automaty. Na automaty obecně můžeme narazit v mnoha odvětvích. Využívají se při zpracování přirozeného jazyka, při tvorbě překladačů programovacích jazyků, při tvorbě komunikačních protokolů, pro vyhledávání v textu, ale i pro simulaci růstu v biologii.
8 Pokud se vám zdá, že se tyto problémy nedají moc kreslit na papír (protože při přechodu na vyšší úroveň se stavby mažou a už máte zgumovaný celý papír), pak na našich webových stránkách1 najdete základní simulátor stavby. Projektování zdar!
XIX/1
5
Naučili jste se podívat dovnitř člověka (mnohé jste tak zabili a mnohé zachránili). Naučili jste se popsat svět rovnicemi, abyste ho uměli předvídat a spočítat (ale přesto o něm nevíte skoro nic).
Úloha 1.3 – Jablko nepadá daleko od stromu (3b)
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 1 0
0 0 0 0 2 0 0 0 0
Jak nejdál může dopadnout jablko, které spadne ze stromu o výšce 3 m? Strom se nachází na rovném trávníku, tedy ani na kopci, ani v dolíku. Předpokládejte, že při odrazu jablka od země se na deformace spotřebuje 1/4 kinetické energie jablka. Nebojte se zavést nějaká vlastní zjednodušení, pokud to budete považovat za nutné (ale nezapomeňte je v řešení popsat), máte přece počítat ideální případ. . .
Příklad stavby věže výšky 2.
xlfd
Téma 2 – Měření rychlostí Určitě jste někdy cestovali vlakem, autobusem, tramvají či jiným hromadným dopravním prostředkem. A zamysleli jste se někdy, jak rychle takovéto dopravní prostředky jezdí? Pokud jedete autem, je to jednoduché, podívate se na tachometr a rychlost víte. Ovšem v autobuse to může být těžší, ve vlaku, pokud nejedete vagonem, ve kterém se rychlost zobrazuje, tachometr vůbec nemáte a v metru nemáte ani krajinu, vůči které byste mohli rychlost odhadovat. A o těchto odhadech bude právě letošní téma.
A naučili jste se počítat úplně všechno v řeči peněz. Cenu jídla, vody, země, štěstí, života i lásky.
Úloha 1.4 – Ruleta Zkuste se zamyslet nad tím, jak měřit rychlost různými způsoby podle toho, co máte zrovna k dispozici. Máte-li GPS, hodinky, nebo ani ty ne. Jak měřit rychlost prostředku, kterým jedete, a jak měřit rychlost toho, který kolem vás projíždí? Umíte využít toho, když projíždějící vlak troubí? Další oblastí není odhad rychlosti okamžité, ale průměrné. Bydlíte-li ve městě, zkuste změřit, 1
http://mam.mff.cuni.cz/vez_stoleti
(1+1b)
Riki vymyslel strategii, jak vyhrávat v ruletě. Na začátku vsadí určitou částku na červenou barvu. Pokud vyhraje, vrátí se mu její dvojnásobek, pokud nevyhraje, v dalším kole její dvojnásobek vsadí opět na červenou. A tak dále. Pravděpodobnost, že by ani jednou nepadla červená je nulová. Po nějaké době tedy zákonitě musí vyhrát. Když sečte své vklady a výhry, tak zjistí, že vyhrál více než vložil. Tento postup může neustále opakovat.
6 (i) Bude tato strategie opravdu fungovat? (ii) Riki má 100 Kč a chce hrát pomocí své strategie tak dlouho dokud nezíská 200 Kč nebo vše neprohraje. Poraďte mu, kolik má postupně do hry vsázet, aby měl co nejvyšší pravděpodobnost výhry. Do rulety lze vsázet pouze celé koruny. Zapomněli jste při tom ale na jednu důležitou věc, totiž cítit. Spěcháte, abyste měli „vícÿ, a nevnímáte ani, jak chutná pokrm, který jíte, jak chladí čistá voda v horské bystřině, jak hladí láska. . . Zapomněli jste, že i vy jste součástí světa, přírody, života. Svoji matku jste spoutali do asfaltových okovů, vyrvali jste jí vnitřnosti, drancujete ji a špiníte. Jako každá matka je trpělivá, protože má ráda své děti. Ale nemá už žádné „vícÿ, co by vám dala. Zní to jako smutný příběh, leč nemusí tak tomu být. Ten příběh zatím nemá konec. . . a píšete ho vy.
XIX/1
7
Zadání témat Téma 1 – Stavba století
A už je to tady! Bylo vypsáno výběrové řízení na stavbu století. Proto oslovujeme vás, nadějné projektanty a konstruktéry, abyste přišli se svými návrhy, zvítězili a vaše nádherná stavba byla postavena k oslavám 20. ročníku studentského matematicko-fyzikálního semináře a časopisu M&M. Předpokládáme, že práce dělníkům půjde pěkně od ruky, ale také, že vámi navržená stavba bude tak megalomanská, že musíme začít už teď. Vaším úkolem bude navrhnout způsob, jak zkonstruovat co nejvyšší věž. Stavět se bude na čtvercové mřížce a jedna věž bude vždy zabírat jedno její políčko. Nemáme ovšem k dispozici lešení, takže jen tak na zelené louce umíme postavit jenom věž výšky 1. Na to, abychom postavili věž výšky 2, musíme nejprve postavit alespoň tři věže výšky jedna, které v mřížce tvoří souvislou oblast (na to, aby dvě věže tvořily souvislou oblast, musí mít stejnou výšku a společnou hranu). Jakmile vznikne souvislá oblast alespoň tří věží stejné výšky, musí se podle stavebních předpisů postavit věž větší. Na věž, kterou jsme postavili jako poslední, přidáme další patro, a protože ostatní věže ze souvislé oblasti byly použity, tak je musíme všechny úplně zbourat. Věž výšky k zkonstruujeme podobně – nejprve postavíme alespoň tři věže výšky k − 1 (opět tak, aby tvořily souvislou oblast), poslední z nich potom zvýšíme o 1 a zbylé zboříme. Zatím ještě není jasné, jaký stavební pozemek budeme mít k dispozici. Nejlepší je být přípraven na všechno, a proto by nás zajímalo, jakou nejvyšší věž je možné postavit • • • • •
v „nekonečné uliciÿ (pozemek má rozměr 1 × ∞), na pozemku 3 × 3, na pozemku 5 × 5, na pozemku 10 × 10. Jak by to vypadalo, kdybychom měli neomezenou stavební plochu? Můžeme postavit nekonečně vysokou věž? • Co když budeme mít předepsáno konkrétní místo na parcele, kde má stát výsledná věž (uprostřed, v rohu, . . . )? • Vítány jsou i vaše vlastní návrhy na tvar parcely a umístění věže na ní.
Součástí stavební dokumentace by měl vždy být přesný popis konstrukce, jak věž dané výšky postavit. Vítány jsou též důkazy, že na daném pozemku už nelze postavit žádnou vyšší věž. Protože stavební předpisy se mohou měnit a my chceme být připraveni opravdu na všechno, zajímalo by nás také, jaká by na tyto otázky byla odpověď, pokud bychom požadovali, aby byly všechny tři věže použité na výstavbu vyšší věže vždy buď ve stejném řádku, nebo ve stejném sloupci.
