MATEMATICKÁ OLYMPIÁDA NA STŘEDNÍCH ŠKOLÁCH kategorie A, B, C a P 57. ROČNÍK, 2007/2008 http://math.muni.cz/mo
Studenti středních škol, zveme vás k účasti v matematické olympiádě, jejíž soutěžní kategorie A, B, C a P pořádáme právě pro vás. Kategorie A je určena žákům maturitních a předmaturitních ročníků, kategorie B žákům, kterým do maturity zbývá více než 2 roky, kategorie C žákům, kterým do maturity zbývá více než 3 roky, kategorie P je zaměřena na programování a je určena žákům všech ročníků. Podrobnější rozdělení uvádí následující tabulka: Předpokládaný školní rok ukončení studia maturitou kategorie MO 2007/2008 2008/2009 2009/2010 2010/2011
A A B C
Žáci nižších ročníků víceletých gymnázií soutěží v MO společně s žáky základních škol v kategoriích Z6 až Z9. Jim je věnován zvláštní leták. Průběh soutěže v kategoriích A, B, C: V kategorii A probíhá soutěž ve třech kolech (školním, krajském a ústředním), v kategoriích B a C probíhá ve dvou kolech (školním a krajském). Školní kolo má dvě části – domácí a klauzurní. V domácí části na vás čeká šest úloh, které najdete v tomto letáku. Jejich řešení (ne nutně všech) odevzdejte svému učiteli matematiky do 26. listopadu 2007 (kategorie A) a do 21. ledna 2008 (kategorie B, C). Ten je opraví, ohodnotí podle stupnice 1 – výborně, 2 – dobře, 3 – nevyhovuje. Pak je s vámi rozebere, vysvětlí vám případné nedostatky a seznámí vás se správným řešením, které také najdete na našich internetových stránkách. Jestliže budou vaše řešení alespoň čtyř úloh ohodnocena jako výborná nebo dobrá, budete pozváni do klauzurní části školního kola. Tam budete ve stanoveném čase samostatně řešit další tři úlohy. Nejlepší účastníci školního kola budou pozváni do krajského kola. Tam budou během čtyř hodin samostatně řešit čtyři úlohy. Při soutěži budou
moci používat školní MF tabulky a kalkulátory bez grafického displeje. O pořadí v krajských kolech soutěže rozhoduje součet bodů získaných za jednotlivé úlohy, a to 0 až 6 bodů za každou z nich. Pokud prvních n žáků dosáhne stejného počtu bodů, je jejich pořadí označeno shodně 1.– n. místem. Podobně se určí pořadí na dalších místech. Žádná jiná kritéria nejsou přípustná. V kategorii A budou ještě nejlepší řešitelé krajského kola z celé republiky soutěžit v ústředním kole, a to za podmínek podobných jako na mezinárodní matematické olympiádě, kde během soutěže lze používat pouze psací a rýsovací potřeby. Právě pro ni se z vítězů ústředního kola vybere družstvo České republiky. Průběh soutěže v kategorii P: Ve školním kole řešíte jen čtyři úlohy uvedené v tomto letáku. Svá řešení odevzdáte svému učiteli matematiky do 15. listopadu 2007. V kategorii P se nekoná klauzurní část školního kola, takže úspěšní řešitelé domácích úloh budou pozváni přímo do krajského kola. Stejně jako v kategorii A se i v kategorii P koná ústřední kolo, jehož vítězové se zúčastní každoroční mezinárodní olympiády v informatice. Předběžně byly stanoveny tyto termíny 57. ročníku MO:
Kategorie A Kategorie B, C Kategorie P
I. kolo (školní část)
II. kolo (krajské)
III. kolo (ústřední)
4.12. 2007 24.1. 2008 —
22.1. 2008 1.4. 2008 15.1. 2008
9.3.–12.3. 2008 — 12.3.–15.3. 2008
MO pořádají Ministerstvo školství, mládeže a tělovýchovy ČR, Jednota českých matematiků a fyziků a Matematický ústav Akademie věd České republiky. Soutěž organizuje ústřední komise MO a v krajích ji řídí krajské komise MO při pobočkách JČMF. Na jednotlivých školách ji zajišťují jednotliví učitelé matematiky, na které se můžete s otázkami kolem MO kdykoli obracet. Řešení soutěžních úloh vypracujte čitelně na listy formátu A4. Každou úlohu začněte na novém listě a uveďte vlevo nahoře záhlaví podle vzoru: Karel Smutný 2. D, gymnázium Kulaté nám. 9, 629 79 Lužany 2007/2008 B–I–4 Poslední údaj je označení úlohy podle tohoto letáku. Znění úloh nemusíte opisovat. Nevejde-li se vám řešení na jeden list, uveďte na dalších listech vlevo nahoře své jméno a označení úlohy a očíslujte stránky. Řešení pište jako výklad, v kterém jsou uvedeny všechny podstatné úvahy tak, aby bylo možno sledovat váš myšlenkový postup. 2
KATEGORIE A A–I–1 Najděte všechny trojice reálných čísel a, b, c s vlastností: Každá z rovnic x3 + (a + 1)x2 + (b + 3)x + (c + 2) = 0, x3 + (a + 2)x2 + (b + 1)x + (c + 3) = 0, x3 + (a + 3)x2 + (b + 2)x + (c + 1) = 0 má v oboru reálných čísel tři různé kořeny, celkem je to však pouze pět různých čísel. (Jaromír Šimša) A–I–2 V rovině je dána úsečka AV a ostrý úhel velikosti α. Určete množinu středů kružnic opsaných všem těm trojúhelníkům ABC s vnitřním úhlem α při vrcholu A, jejichž výšky se protínají v bodě V . (Pavel Leischner ) A–I–3 Množinu M tvoří 2n různých kladných reálných čísel, kde n ≧ 2. Uvažujme n obdélníků, jejichž rozměry jsou čísla z M, přičemž každý prvek z M je použit právě jednou. Určete, jaké rozměry mají tyto obdélníky, je-li součet jejich obsahů a) největší možný; b) nejmenší možný. (Jaroslav Švrček ) A–I–4 Určete počet konečných rostoucích posloupností přirozených čísel a1 , a2 , . . . , ak všech možných délek k, pro které platí a1 = 1, ai | ai+1 pro i = 1, 2, . . . , k − 1 a ak = 969 969. (Martin Panák ) A–I–5 Je dána kružnice k, bod O, který na ní neleží, a přímka p, která ji neprotíná. Uvažujme libovolnou kružnici l, která má vnější dotyk s kružnicí k a dotýká se i přímky p. Příslušné body dotyku označme A a B. Pokud body O, A, B neleží v přímce, sestrojíme kružnici m opsanou trojúhelníku OAB. Dokažte, že všechny takové kružnice m procházejí společným bodem různým od bodu O, anebo se dotýkají téže přímky. (Ján Mazák ) A–I–6 Dokažte, že pro každé přirozené číslo n existuje celé číslo a (1 < a < 5n ) takové, že platí 5n | a3 − a + 1. (Ján Mazák ) 3
KATEGORIE B B–I–1 Najděte všechna přirozená čísla k, pro něž je zápis čísla 6k · 72007−k v desítkové soustavě zakončen dvojčíslím a) 02; b) 04. (Eva Řídká) B–I–2 V pásu mezi rovnoběžkami p, q jsou dány dva různé body M a N . Sestrojte kosočtverec nebo čtverec, jehož dvě protější strany leží na přímkách p a q a body M a N leží po jednom na zbývajících dvou stranách. (Jaromír Šimša) B–I–3 Jsou-li x a y reálná čísla, pro něž platí x3 + y 3 ≦ 2, potom x + y ≦ 2. Dokažte. (Ján Mazák ) B–I–4 Najděte všechny pravoúhlé trojúhelníky s délkami stran a, b, c a délkami těžnic ta , tb , tc , pro něž platí a + ta = b + tb . Uvažujte oba případy, kdy AB je a) přepona, b) odvěsna. (Pavel Novotný) B–I–5 Určete všechny dvojice a, b reálných čísel, pro něž má každá z kvadratických rovnic ax2 + 2bx + 1 = 0,
bx2 + 2ax + 1 = 0
dva různé reálné kořeny, přičemž právě jeden z nich je oběma rovnicím společný. (Jaroslav Švrček ) B–I–6 Obdélník 2 005 × 2 007 je rozdělen na černé a bílé jednotkové čtverečky. Dokažte, že pak pro jednu z barev (černou nebo bílou) existuje více než 95 800 pravoúhelníků (složených z jednotkových čtverečků), jež se navzájem nepřekrývají a jejichž rohová políčka mají vesměs zvolenou barvu, přičemž každá z jejich stran obsahuje aspoň dva čtverečky. (Pavel Leischner )
4
KATEGORIE C C–I–1 √ √ √ Určete nejmenší přirozené číslo n, pro něž i čísla 2n, 3 3n, 5 5n jsou přirozená. (Jaroslav Švrček ) C–I–2 Čtyřúhelníku ABCD je vepsána kružnice se středem S. Určete rozdíl |ASD| − |CSD|, jestliže |ASB| − |BSC| = 40◦ . (Jaromír Šimša) C–I–3 Máme určitý počet krabiček a určitý počet kuliček. Dáme-li do každé krabičky právě jednu kuličku, zbyde nám n kuliček. Když však dáme právě n krabiček stranou, můžeme všechny kuličky rozmístit tak, aby jich v každé zbývající krabičce bylo právě n. Kolik máme krabiček a kolik kuliček? (Vojtech Bálint ) C–I–4 Tangram je skládačka, kterou lze vyrobit z papíru rozřezáním vystřiženého čtverce na sedm dílů podle čar vyznačených na obrázku. Předpo√ 2 2 1 √ 2 1 1 1
1 1
√ 2
1
1 √
√ 2
2
√ kládejme, že délka strany čtverce je 2 2 cm. Rozhodněte, zda lze z dílů tangramu složit: a) obdélník √ 2 cm × 4 cm, √ (Pavel Leischner ) b) obdélník 2 cm × 4 2 cm. C–I–5 Ve skupině n lidí (n ≧ 4) se někteří znají. Vztah „znát seÿ je vzájemný: jestliže osoba A zná osobu B, pak také B zná A a nazýváme je dvojicí známých. 5
a) Jestliže mezi každými čtyřmi osobami jsou aspoň čtyři dvojice známých, pak každé dvě osoby, které se neznají, mají společného známého. Dokažte. b) Zjistěte, pro která n ≧ 4 existuje skupina osob, v níž jsou mezi každými čtyřmi osobami aspoň tři dvojice známých a současně se některé dvě osoby neznají ani nemají společného známého. c) Rozhodněte, zda ve skupině šesti osob mohou být v každé čtveřici právě tři dvojice známých a právě tři dvojice neznámých. (Ján Mazák ) C–I–6 Klárka měla na papíru napsáno trojmístné číslo. Když ho správně vynásobila devíti, dostala čtyřmístné číslo, jež začínalo touž číslicí jako číslo původní, prostřední dvě číslice se rovnaly a poslední číslice byla součtem číslic původního čísla. Které čtyřmístné číslo mohla Klárka dostat? (Peter Novotný)
6
KATEGORIE P Řešení každého příkladu musí obsahovat podrobný popis použitého algoritmu, zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu). V úlohách P–I–1, P–I–2 a P–I–3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal, C nebo C++. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i elektronicky (na CD, na disketě, případně po dohodě lze i zaslat e-mailem), aby bylo možné otestovat jeho funkčnost. Slovní popis řešení musí být ovšem jasný a srozumitelný, aniž by bylo nutno nahlédnout do zdrojového textu programu. V úloze P–I–4 je nutnou součástí řešení úplný popis všech použitých překládacích strojů. Řešení úloh domácího kola MO kategorie P vypracujte a odevzdejte buď ve škole, nebo zašlete přímo vaší krajské komisi MO, nejpozději do 15. 11. 2007. Vzorová řešení úloh naleznete po tomto datu na Internetu na adrese http://mo.mff.cuni.cz/. Na stejném místě jsou stále k dispozici veškeré aktuální informace o soutěži a také archiv soutěžních úloh a výsledků minulých ročníků.
P–I–1 O zdánlivém kopci Franta a Pepík se chystali na výlet. Vymysleli si trasu, kudy spolu půjdou, potom každý vytáhnul svoji mapu a začal si v ní trasu prohlížet. Některé body, kterými trasa vedla, měly v mapách vyznačenu nadmořskou výšku. „To je zajímavé,ÿ řekl po chvíli Franta. „Když se dívám jen na nadmořské výšky bodů, kterými budeme procházet, vypadá to, že půjdeme jenom přes jeden kopec — nejprve nahoru a potom dolů.ÿ „Ale kdepak, to není pravda,ÿ podivil se Pepík. Za chvíli zjistili, kde vzniknul problém: měli různě přesné mapy. Některé nadmořské výšky bodů, které byly na Pepíkově mapě vyznačeny, na Frantově mapě chyběly. Soutěžní úloha. Napište program, který dostane na vstupu seznam nadmořských výšek z Pepíkovy mapy a zjistí, kolik nejvýše z nich může být vyznačeno i na Frantově mapě. Formát vstupu: První řádek vstupu obsahuje jedno celé číslo N (1 ≦ ≦ N ≦ 100 000) — počet těch bodů na trase výletu, které mají na Pepíkově mapě vyznačenou nadmořskou výšku. Další řádky obsahují celkem N celých čísel z rozsahu 1 až 1 000 000 000 — nadmořské výšky těchto bodů (v nějakých vám neznámých jednotkách). Výšky jsou uvedeny v pořadí, jak po sobě následují na trase výletu. Formát výstupu: Výstupem bude jediné celé číslo K — největší počet nadmořských výšek z Pepíkovy mapy, které mohly být vyznačeny i na Frantově mapě. Jestliže a1 , . . . , aK jsou výšky vyznačené na Frantově mapě, pak musí splňovat následující podmínku: pro nějaké i z množiny {1, . . . , K} musí platit ∀j ∈ {1, . . . , i − 1}: aj < aj+1 a zároveň ∀j ∈ {i, . . . , K − 1}: aj > > aj+1 . 7
Příklad : vstup: 12 112 247 211 209 244 350 470 510 312 215 117 217
výstup: 9 Jedna možnost, jak mohly vypadat nadmořské výšky na Frantově mapě: 112, 211, 244, 350, 470, 510, 312, 215, 117
P–I–2 Rezervace místenek „V horách se našlo zlato!ÿ šeptali si lidé v širokém okolí už několik týdnů. Ti s dobrodružnější povahou si už balili věci a mířili přímo do hor, do legendami opředené oblasti zvané Horní Klondík. Když ale Horní Klondík zaplavila vlna nových zlatokopů, nastal nečekaný problém. Jediný místní vláček, který v Klondíku měli, byl najednou tak přecpaný, že se do něj polovina zájemců ani nevešla. A nedivte se, že zlatokopa, který se žene za co nejvýhodnější parcelou, něco takového pořádně rozzlobí. Když už se zdálo, že zanedlouho dojde na každé železniční stanici ke krveprolití, dostali železničáři spásonosný nápad. Budou na vláček prodávat místenky. Soutěžní úloha. Napište program, který bude zpracovávat rezervace míst na jednu jízdu vlaku. Trať vlaku má N + 1 stanic, které si očíslujeme od 0 do N v pořadí, jak na trati leží. Ve vlaku je M míst, takže mezi každou dvojicí po sobě následujících stanic může jet vlakem nejvýše M zlatokopů. Váš program musí postupně zpracovat několik požadavků na rezervaci míst. Každý požadavek je tvaru „x lidí chce jet ze stanice y do stanice z.ÿ Pokud je ještě na každém úseku trati mezi stanicemi y a z ve vlaku aspoň x míst volných, váš program takovýto požadavek přijme, v opačném případě ho odmítne. Formát vstupu: První řádek vstupu obsahuje tři celá čísla N , M a P (1 ≦ N, M, P ≦ 100 000) — počet úseků trati, počet míst ve vlaku a počet požadavků na rezervaci. Následuje P řádků, každý z nich popisuje jeden požadavek na rezervaci v pořadí, v jakém byly tyto požadavky zadány. Přesněji, i-tý z těchto řádků obsahuje tři celá čísla xi , yi , zi oddělená mezerami (1 ≦ xi ≦ M , 0 ≦ yi < zi ≦ N ). Význam těchto hodnot byl popsán výše. Formát výstupu: Pro každý požadavek vypište na výstup jeden řádek a na něm buď řetězec prijat, jestliže příslušný požadavek bylo ještě možné splnit, nebo řetězec odmitnut, pokud už ve vlaku nebylo dost volných míst. 8
Příklad : vstup: výstup: 466 prijat 214 prijat 213 odmitnut 324 odmitnut 312 prijat 601 prijat 434 Po přijetí prvních dvou požadavků víme, že v úsecích mezi stanicemi 1 a 2 a mezi stanicemi 2 a 3 zůstanou už jen dvě volná místa. Proto musíme odmítnout následující dvě trojčlenné skupiny, které chtějí cestovat i na těchto úsecích tratě. Poslední dva požadavky opět můžeme splnit. U prvního z nich je to zřejmé, u druhého nám ve stanici 3 vystoupí dostatek lidí na to, aby se na poslední úsek trati uvolnila přesně potřebná čtyři místa. P–I–3 Fibonacciho soustava Fibonacciho posloupnost vypadá následovně: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . . Sestrojíme ji tak, že prvními dvěma členy posloupnosti jsou 0 a 1 a každý následující člen posloupnosti je součtem dvou předcházejících. Matematicky zapsáno: F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn
(∀n ≧ 0).
Podívejme se nyní na to, jak fungují poziční číselné soustavy. Poziční číselná soustava je určena dvěma údaji: množinou používaných cifer a posloupností, která pro každou pozici v zápisu čísla udává hodnotu, jíž se příslušná cifra násobí. Například naše desítková soustava používá množinu cifer {0, 1, 2, . . . , 9} a jednotlivé pozice v čísle mají hodnoty (zprava doleva) 1, 10, 100, 1 000, . . . Fibonacciho číselná soustava je poziční číselná soustava, která používá pouze cifry 0 a 1 a v níž jsou hodnoty jednotlivých pozic postupně rovny členům Fibonacciho posloupnosti (počínaje číslem F2 = 1). Tedy například zápis 10011 ve Fibonacciho soustavě představuje číslo 1 · 8 + 0 · 5 + 0 · 3 + + 1 · 2 + 1 · 1 = 11. 9
Na rozdíl od běžných číselných soustav ve Fibonacciho soustavě nemají některá čísla jednoznačný zápis. Například také zápis 10100 představuje číslo 11. Soutěžní úloha. a) (3 body) Zápis čísla ve Fibonacciho soustavě nazveme pěkný, jestliže se v něm nikde nevyskytují dvě po sobě jdoucí jedničky. Dokažte, že každé přirozené číslo má ve Fibonacciho soustavě právě jeden pěkný zápis. Napište program, který ze vstupu přečte přirozené číslo N a vypíše jeho pěkný zápis. b) (7 bodů) Napište program, který pro daná k, A a B spočítá, kolik čísel z množiny {A, A + 1, . . . , B} má ve svém pěkném zápisu právě k jedniček. Formát vstupu: V části a) je na vstupu jediné přirozené číslo N (1 ≦ ≦ N ≦ 1 000 000 000). V části b) jsou na vstupu tři přirozená čísla k, A a B (1 ≦ k ≦ 30, 1 ≦ A < B ≦ 1 000 000 000). Formát výstupu: V části a) vypište na jeden řádek řetězec nul a jedniček, který představuje pěkný zápis čísla N . V části b) vypište jedno celé číslo — počet čísel ze zadaného intervalu, která mají ve svém pěkném zápisu právě k jedniček. Příklady pro část a): vstup 1: výstup 1: 11 10100 vstup 2: výstup 2: 174591 1010001000000000100010010 Příklady pro část b): vstup 1: výstup 1: 1 4 13 3 (Pro k = 1 je výstupem počet Fibonacciho čísel v daném rozsahu. V zadaném rozsahu leží Fibonacciho čísla 5, 8 a 13.) vstup 2: 2 4 13 vstup 3: 10 102000 103000
výstup 2: 6 výstup 3: 86
P–I–4 Překládací stroje V tomto ročníku olympiády budeme pracovat s překládacími stroji. Ve studijním textu uvedeném za zadáním úlohy jsou tyto stroje popsané. 10
Soutěžní úloha. a) (1 bod) Všimněte si překládacích strojů B a C z příkladů ve studijním textu. Tyto dva stroje zjevně provádějí překlad „opačnými směryÿ. Mohli bychom proto očekávat, že platí následující tvrzení: Nechť M je libovolná (třeba i nekonečná) množina, jejímiž prvky jsou nějaké řetězce písmen a, e a i. Potom C(B(M )) = M . Slovně popsáno: Když vezmeme množinu M , přeložíme ji pomocí stroje B a výsledek přeložíme pomocí C, dostaneme původní množinu. Pokud toto tvrzení skutečně platí, dokažte ho. Pokud ne, najděte protipříklad. b) (1 bod) Totéž jako v předcházející části, jen M obsahuje řetězce tvořené znaky a • a zajímá nás, zda musí platit B(C(M )) = M .
c) (3 body) Řekneme, že řetězec je zajímavý, jestliže obsahuje pouze písmena a a b, přičemž písmen a je dvojnásobný počet než písmen b. Nechť X je množina všech zajímavých řetězců. Tedy například aaabab ∈ X, ale baba 6∈ X. Nechť Y je množina všech řetězců, které obsahují nejprve několik písmen a a za nimi trojnásobné množství písmen b. Tedy například abbb ∈ Y , ale aaabab 6∈ Y . Sestrojte překládací stroj, který přeloží X na Y .
d) (5 bodů) Na začátku máme množinu M1 , jež obsahuje všechny takové řetězce tvořené z písmen a, b, které obsahují stejný počet písmen a jako b. Tedy například abbbaa ∈ M1 , ale aabab 6∈ M1 . Nové množiny můžeme sestrojovat následujícími operacemi: ⊲ překladem nějaké již sestrojené množiny nějakým strojem (můžeme použít pokaždé jiný stroj), ⊲ sjednocením dvou již sestrojených množin, ⊲ průnikem dvou již sestrojených množin. Provedením co nejmenšího počtu operací sestrojte množinu G, která obsahuje právě všechny řetězce, v nichž je nejprve několik písmen a, potom stejný počet písemen b, a nakonec stejný počet písmen c. Tedy například aabbcc ∈ G, ale abcc 6∈ G, a ani bac 6∈ G. Studijní text: Překládací stroj přijímá na vstupu řetězec znaků. Tento řetězec postupně čte a podle předem zvolené soustavy pravidel (tedy podle svého programu) občas nějaké znaky zapíše na výstup. Když stroj zpracuje celý vstupní řetězec a úspěšně ukončí svůj výpočet, vezmeme řetězec znaků zapsaný na výstup a nazveme ho překladem vstupního řetězce. Výpočet stroje nemusí být jednoznačně určen. Jinými slovy, soustava pravidel může někdy stroji umožnit, aby se rozhodl o dalším postupu vý11
počtu. V takovém případě se může stát, že některý řetězec bude mít více různých překladů. Naopak, může se stát, že v určité situací se podle daných pravidel nebude moci v překladu pokračovat vůbec. V takovém případě se může stát, že některý řetězec nebude mít vůbec žádný překlad. Formálnější definice překládacího stroje Každý překládací stroj pracuje nad nějakou předem zvolenou konečnou množinou znaků. Tuto množinu znaků budeme nazývat abeceda a značit Σ. V soutěžních úlohách bude vždy Σ známa ze zadání úlohy. Abeceda nebude nikdy obsahovat znak $, ten budeme používat k označení konce vstupního řetězce. Stroj si může během překladu řetězce pamatovat informaci konečné velikosti. Formálně tuto skutečnost definujeme tak, že stroj se v každém okamžiku překladu nachází v jednom z konečně mnoha stavů. Nutnou součástí programu překládacího stroje je tedy nějaká konečná množina stavů, v nichž se stroj může nacházet. Tuto množinu označíme K. Kromě samotné množiny stavů je také třeba uvést, ve kterém stavu se stroj nachází na začátku každého překladu. Tento stav nazveme počáteční stav. Program stroje se skládá z konečného počtu překladových pravidel. Každé pravidlo má tvar čtveřice (p, u, v, q), kde p, q ∈ K jsou nějaké dva stavy a u, v jsou nějaké dva řetězce znaků z abecedy Σ. Stavy p a q mohou být i stejné. Řetězec u může být tvořen jediným znakem $. Řetězce u a v mohou být i stejné. Některý z těchto řetězců může být případně prázdný. Aby se program lépe četl, budeme místo prázdného řetězce psát symbol ε. Překladové pravidlo má následující význam: „Když je stroj právě ve stavu p a dosud nepřečtená část vstupu začíná řetězcem u, může stroj tento řetězec ze vstupu přečíst, na výstup zapsat řetězec v a změnit svůj stav na q.ÿ Všimněte si, že pravidlo tvaru (p, ε, v, q) můžeme použít vždy, když se stroj nachází ve stavu p, bez ohledu na to, jaké znaky ještě zůstávají na vstupu. Ještě potřebujeme stanovit, kdy překlad úspěšně skončil. V první řadě budeme požadovat, aby překládací stroj přečetl celý vstupný řetězec. Kromě toho umožníme stroji „odpovědětÿ, zda se mu překlad podařil nebo ne. To zařídíme tak, že některé stavy stroje označíme jako koncové stavy. Množinu všech koncových stavů budeme značit F . Formální definice překládacího stroje Překládací stroj je uspořádaná pětice (K, Σ, P, q0 , F ), kde Σ a K jsou konečné množiny, q0 ∈ K, F ⊆ K a P je konečná množina překladových pravidel popsaných výše. Přesněji, nechť Σ∗ je množina všech ře12
tězců tvořených znaky ze Σ, potom P je konečná podmnožina množiny K × (Σ∗ ∪ {$}) × Σ∗ × K. (Pro každé q ∈ K budeme množinu pravidel, jejichž první složkou je q, nazývat „překladová pravidla ze stavu qÿ.) Chceme-li definovat konkrétní překládací stroj, musíme uvést všech pět výše uvedených objektů. Když už máme definován konkrétní stroj A = (K, Σ, P, q0 , F ), můžeme určit, jak tento stroj překládá konkrétní řetězec. Uvedeme nejprve formální definici a potom ji slovně vysvětlíme. Množina platných překladů řetězce u překládacím strojem A je: n A(u) = v ∃n ≧ 0∃(p1 , u1 , v1 , r1 ), . . . , (pn , un , vn , rn ) ∈ P : (∀i ∈ {1, . . . , n − 1} : ri = pi+1 ) ∧ p1 = q0 ∧ rn ∈ F ∧ o ∧ ∃k ≧ 0: u1 u2 . . . un = u $| .{z . . $} ∧v1 v2 . . . vn = v . k
Definice stanoví, kdy je řetězec v překladem řetězce u. Vysvětlíme si slovně význam jednotlivých řádků definice: ⊲ První řádek říká, že aby se dalo u přeložit na v, musí existovat nějaká posloupnost překladových pravidel, kterou při tomto překladu použijeme. Další dva řádky popisují, jak tato posloupnost musí vypadat. ⊲ Druhý řádek zabezpečuje, aby stavy v použitých pravidlech byly správné: První pravidlo musí být pravidlem z počátečního stavu, každé další pravidlo musí být pravidlem z toho stavu, do něhož se stroj dostal použitím předcházejícího pravidla. Navíc stav, v němž se bude stroj nacházet po skončení výpočtu, musí být koncový. ⊲ Poslední řádek popisuje řetězce, které stroj při použití dotyčných překladových pravidel čte a zapisuje. Řetězec, který při použití těchto pravidel stroj přečte ze vstupu, musí být skutečně zadaným řetězcem u, případné může být zprava doplněn vhodným počtem znaků $. Řetězec, který stroj zapíše na výstup, musí být přesně řetězcem v. K čemu budeme používat překládací stroje? Překládací stroje nám budou sloužit k získání překladu jedné množiny řetězců na jinou množinu řetězců. Jestliže A je překládací stroj a M ⊆ Σ∗ nějaká množina řetězců, potom překlad množiny M strojem A je množina A(M ) =
[
A(u).
u∈M
13
Jinými slovy, výslednou množinu A(M ) sestrojíme tak, že vezmeme všechny řetězce z M a pro každý z nich přidáme do A(M ) všechny jeho platné překlady. Příklad 1 : Mějme abecedu Σ = {0, . . . , 9}. Nechť M je množina všech řetězců, které představují zápisy kladných celých čísel v desítkové soustavě. Sestrojíme překládací stroj A, pro který bude platit, že překladem této množiny M bude množina zápisů všech kladných celých čísel, která jsou dělitelná třemi. Řešení. Nejjednodušší bude prostě vybrat z M ta čísla, která jsou dělitelná třemi. Náš překládací stroj bude kopírovat cifry ze vstupu na výstup, přičemž si bude pomocí stavu pamatovat, jaký zbytek po dělení třemi dává dosud přečtené (a zapsané) číslo. Nachází-li se po dočtení vstupu ve stavu odpovídajícím zbytku 0, přejde do koncového stavu. Formálně A bude pětice (K, Σ, P, 0, F ), kde K = {0, 1, 2, end}, F = = {end} a překladová pravidla vypadají následovně: P = {(x, y, y, z)|x ∈ {0, 1, 2} ∧ y ∈ Σ ∧ z = (10x + y) mod 3} ∪ ∪ {(0, $, ε, end)}. Příklad 2 : Mějme abecedu Σ = {a, e, i, •, }. Sestrojíme překládací stroj B, pro který bude platit, že překladem libovolné množiny M , která obsahuje pouze řetězce z písmen a, e a i, bude množina stejných řetězců zapsaných v morseovce (bez oddělovačů mezi znaky). Zápisy našich písmen v morseovce vypadají následovně: a je • , e je • a i je ••. Například množinu M = {ae, eea, ia} by náš stroj měl přeložit na množinu {• •, ••• }. (Všimněte si, že řetězce eea a ia mají v morseovce bez oddělovačů stejný zápis.) Řešení. Překládací stroj B bude číst vstupní řetězec po znacích a vždy zapíše na výstup kód přečteného znaku. Formálně B bude pětice (K, Σ, P, ♥, F ), kde K = {♥}, F = {♥} a překladová pravidla vypadají takto: P = {(♥, a, • , ♥), (♥, e, •, ♥), (♥, i, ••, ♥)}. Všimněte si, že nepotřebujeme nijak zvlášť kontrolovat, zda jsme na konci vstupu. Během celého překladu je totiž stroj v koncovém stavu, takže jakmile přečte poslední znak ze vstupu, bude vytvořený překlad platný. Příklad 3 : Mějme abecedu Σ = {a, e, i, •, }. Sestrojíme překládací stroj C, pro který bude platit, že překladem libovolné množiny M , která 14
obsahuje pouze řetězce tvořené znaky • a , bude množina všech řetězců z písmen a, e a i, jejichž zápisy v morseovce (bez oddělovačů mezi znaky) jsou obsaženy v množině M . Například množinu M = {• •, • • • } by náš stroj měl přeložit na {ae, eea, ia}.
Řešení. Našemu překládacímu stroji dáme možnost rozhodnout se v každém okamžiku překladu, že bude číst kód nějakého písmena a zapíše na výstup toto písmeno. Potom každé možnosti, jak lze rozdělit vstupní řetězec na kódy písmen, bude odpovídat jeden platný překlad. Formálně C bude pětice (K, Σ, P, ♦, F ), kde K = {♦}, F = {♦} a překladová pravidla vypadají následovně: P = {(♦, • , a, ♦), (♦, •, e, ♦), (♦, ••, i, ♦)}.
Ukážeme si, jak mohl probíhat překlad řetězců z výše uvedené množiny M . Existují tyto tři možnosti: ⊲ (♦, • , a, ♦), (♦, •, e, ♦) ⊲ (♦, ••, i, ♦), (♦, • , a, ♦) ⊲ (♦, •, e, ♦), (♦, •, e, ♦), (♦, • , a, ♦) Kdybychom zkusili pro libovolný vstupní řetězec z M použít překladová pravidla v jiném pořadí – např. pro vstup • • • použít třikrát pravidlo (♦, •, e, ♦) – nepodaří se nám dočíst vstupní řetězec až do konce. Příklad 4 : Mějme abecedu Σ = {a, b, c}. Nechť množina X obsahuje právě všechny řetězce, v nichž je obsažen stejný počet znaků a a b. Tedy například abbccac ∈ X, ale cbaa 6∈ X. Nechť množina Y obsahuje právě všechny řetězce, které neobsahují žádné a, neobsahují podřetězec bc, a písmen c je dvakrát více než písmen b. Tedy například ccccbb ∈ Y , ale cccbcb 6∈ Y a acacba 6∈ Y . Sestrojíme překládací stroj D, který přeloží X na Y .
Řešení. Budeme překládat jenom některé vhodné řetězce z množiny X. Budou to ty řetězce, které neobsahují žádné c a všechna a v nich předcházejí všem znakům b. Takovýto řetězec přeložíme tak, že nejprve každé a přepíšeme na cc, a potom zkopírujeme na výstup všechna b. Tedy například překladem slova aabb bude slovo ccccbb. Formálně D bude pětice (K, Σ, P, čti-a, F ), kde K = {čti-a, čti-b}, F = = {čti-b} a překladová pravidla vypadají takto: P = {(čti-a, a, cc, čti-a), (čti-a, ε, ε, čti-b), (čti-b, b, b, čti-b)}. Proč tento překládací stroj funguje? Když vstupní řetězec obsahuje nějaké písmeno c, při jeho překládání se u prvního výskytu c náš stroj 15
zastaví. Proto takové řetězce nemají žádný platný překlad. Podobně nemají platný překlad řetězce, v nichž není dodrženo pořadí písmen a a b. Po přečtení nějaké posloupnosti písmen a přejde stroj pomocí druhého pravidla do stavu čti-b, a pokud se poté ještě objeví na vstupu a, stroj se zastaví. Platné překlady tedy existují skutečně pouze pro slova výše popsaného tvaru. Je zjevné, že překladem každého z nich získáme nějaký řetězec z Y , takže D(X) ⊆ Y . Naopak, vybereme-li si libovolné slovo z Y , snadno najdeme slovo z X, které se na něj přeloží. Proto také Y ⊆ D(X), takže Y = D(X).
Informace o MO a zadání úloh najdete též na internetu http://math.muni.cz/mo
Sponzor matematické olympiády v České republice
ÚSTŘEDNÍ KOMISE MATEMATICKÉ OLYMPIÁDY 57. ROČNÍK MATEMATICKÉ OLYMPIÁDY Leták kategorií A, B, C a P
Vydala Jednota českých matematiků a fyziků pro vnitřní potřebu Ministerstva školství, mládeže a tělovýchovy ČR v 1. vydání Programem TEX připravil Karel Horák c Jednota českých matematiků a fyziků, 2007
