MATEMATICKÁ OLYMPIÁDA NA STŘEDNÍCH ŠKOLÁCH kategorie A, B, C a P 64. ROČNÍK, 2014/2015 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 2014/2015 2015/2016 2016/2017 2017/2018
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 1. prosince 2014 (kategorie A) a do 12. ledna 2015 (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. Podle rozhodnutí Ústřední komise MO z března 2011 nebudou od školního roku 2011/2012
v klauzurních kolech MO povoleny kalkulačky, notebooky ani žádné jiné elektronické pomůcky. 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. Bodové hranice k určení úspěšných řešitelů a úspěšných účastníků budou stanoveny centrálně po vyhodnocení statistik bodových výsledků ze všech krajů. Podrobnější pravidla pro vyhodnocování krajských kol najdete na http://www.math.muni.cz/mo. 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 do 15. 11. 2014 jen čtyři úlohy uvedené v tomto letáku. Řešení nebudete odevzdávat ve škole, ale odešlete ho přes webové rozhraní podle pokynů uvedených u úloh. 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. Termíny soutěžních kol 64. ročníku MO jsou stanoveny takto:
Kategorie A Kategorie B, C Kategorie P
I. kolo (školní část)
II. kolo (krajské)
III. kolo (ústřední)
9.12. 2014 22.1. 2015 —
13.1. 2015 31.3. 2015 20.1. 2015
22.3.–25.3. 2015 — 25.3.–28.3. 2015
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í pověření 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 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 1. Je dáno přirozené číslo n. Čtverec o straně délky n je rozdělen na n2 jednotkových čtverečků. Za vzdálenost dvou čtverečků považujeme vzdálenost jejich středů. Určete počet dvojic čtverečků, jejichž vzdálenost je 5. (Jaroslav Zhouf ) 2. Je dán trojúhelník ABC, v němž je BC nejkratší stranou. Její střed označme M . Na stranách AB a AC určíme postupně body X a Y tak, aby platilo |BX| = |BC| = |CY |. Průsečík přímek CX a BY označme Z. Ukažte, že přímka ZM prochází středem kružnice připsané straně BC daného trojúhelníku. (Michal Rolínek ) 3. Najděte všechna celá čísla k ≧ 2, pro která existuje k-prvková množina M celých kladných čísel taková, že součin všech čísel z M je dělitelný součtem libovolných dvou (různých) čísel z M. (Jaromír Šimša) 4. Předpokládejme, že pro reálná čísla x, y, z platí 15(x + y + z) = 12(xy + yz + zx) = 10(x2 + y 2 + z 2 ) a že alespoň jedno z nich je různé od nuly. a) Dokažte rovnost x + y + z = 4. b) Najděte nejmenší interval ⟨a, b⟩, v němž leží všechna tři čísla z libovolné trojice (x, y, z) vyhovující předpokladům úlohy. (Jaromír Šimša) 5. V daném trojúhelníku ABC označme D bod dotyku kružnice vepsané se stranou BC. Kružnice vepsaná trojúhelníku ABD se dotýká stran AB a BD v bodech K a L. Kružnice vepsaná trojúhelníku ADC se dotýká stran DC a AC v bodech M a N . Dokažte, že body K, L, M , N leží na jedné kružnici. (Josef Tkadlec) 6. Nechť ∞a, b jsou daná, navzájem nesoudělná přirozená čísla. Posloupnost xn n=1 přirozených čísel je sestavena tak, že pro každé n > 1 platí xn = axn−1 +b. Dokažte, že v libovolné takové posloupnosti každý člen xn s indexem n > 1 dělí nekonečně mnoho jejích dalších členů. Platí toto tvrzení i pro n = 1? (Jaromír Šimša)
3
Kategorie B 1. V oboru reálných čísel řešte soustavu rovnic |x − 5| + |y − 9| = 6, 2
|x − 9| + |y 2 − 5| = 52. (Pavel Calábek ) 2. Drak má n hlav, po jedné na každém z n krků uspořádaných do kruhu. Rytíř dokáže jedním úderem tít po k sousedních krcích a hlavy na nich setnout. Jestliže drakovi po úderu zbyde aspoň jedna hlava, může si nechat některou z chybějících hlav okamžitě dorůst. Dokažte, že když pro daná čísla n a k může rytíř draka zbavit všech hlav bez ohledu na to, jak mu dorůstají, svede to udělat nejvýše třemi údery. (Ján Mazák ) 3. V trojúhelníku ABC označme U střed strany AB a V střed strany AC. V polorovině opačné k polorovině BCA uvažujme libovolný rovnoběžník BCDE. Označme X průsečík přímek U D a V E. Dokažte, že přímka AX dělí rovnoběžník BCDE na dvě části téhož obsahu. (Michal Rolinek ) 4. Nechť m je přirozené číslo, které má 7 kladných dělitelů, a n je přirozené číslo, které má 9 kladných dělitelů. Kolik dělitelů může mít součin m·n? (Eva Patáková) 5. Nechť S je střed přepony AB pravoúhlého trojúhelníku ABC, který není rovnoramenný. Označme D patu výšky z vrcholu C a R průsečík osy vnitřního úhlu při vrcholu C s přeponou AB. Určete velikosti vnitřních úhlů tohoto trojúhelníku, platí-li |SR| = 2|DR|. (Jaroslav Švrček ) 6. Dokažte, že pro libovolná kladná reálná čísla a, b, c platí 1 1 1 1 1 1 + 2 + 2 ≦ 2 + 2 + 2. a2 − ab + b2 b − bc + c2 c − ca + a2 a b c Určete, kdy nastane rovnost.
4
(Jaroslav Švrček )
Kategorie C 1. Určete všechny dvojice (x, y) reálných čísel, která vyhovují soustavě rovnic p (x + 4)2 = 4 − y, p (y − 4)2 = x + 8. (Jaroslav Švrček ) 2. Petr má zvláštní hodinky se třemi ručičkami – první z nich oběhne kruhový ciferník za minutu, druhá za 3 minuty a třetí za 15 minut. Na začátku jsou všechny ručičky ve stejné poloze. Určete, za jak dlouho budou ručičky rozdělovat ciferník na tři shodné části. Najděte všechna řešení. (Tomáš Jurík ) 3. Simona a Lenka hrají hru. Pro dané celé číslo k takové, že 0 ≦ k ≦ 64, vybere Simona k políček šachovnice 8 × 8 a každé z nich označí křížkem. Lenka pak šachovnici nějakým způsobem vyplní dvaatřiceti dominovými kostkami. Je-li počet kostek pokrývajících dva křížky lichý, vyhrává Lenka, jinak vyhrává Simona. V závislosti na k určete, která z dívek má vyhrávající strategii. (Michal Rolínek ) 4. Označme E střed základny AB lichoběžníku ABCD, v němž platí |AB| : |CD| = 3 : 1. Úhlopříčka AC protíná úsečky ED, BD po řadě v bodech F , G. Určete postupný poměr |AF | : |F G| : |GC|. (Jaroslav Zhouf ) 5. Rozdíl dvou přirozených čísel je 2 010 a jejich největší společný dělitel je 2 014krát menší než jejich nejmenší společný násobek. Určete všechny takové dvojice čísel. (Jaromír Šimša) 6. Najděte √ nejmenší přirozené číslo n takové, že v zápise iracionálního čísla n následují bezprostředně za desetinnou čárkou dvě devítky. (Josef Tkadlec)
5
KATEGORIE P Úlohy P–I–1 a P–I–2 jsou praktické, vaším úkolem v nich je vytvořit a odladit efektivní program v jazyce Pascal, C nebo C++. Řešení těchto dvou úloh odevzdávejte ve formě zdrojového kódu přes webové rozhraní přístupné na stránce http: //mo.mff.cuni.cz/submit/, kde také naleznete další informace. Odevzdaná řešení budou automaticky vyhodnocena pomocí připravených vstupních dat a výsledky vyhodnocení se dozvíte krátce po odevzdání. Pokud váš program nezíská plný počet 10 bodů, můžete své řešení opravit a znovu odevzdat. Úlohy P–I–3 a P–I–4 jsou teoretické. V úloze P–I–3 je vaším úkolem nalézt efektivní algoritmus řešící zadaný problém. Řešení úlohy se skládá z popisu navrženého algoritmu, zdůvodnění jeho správnosti (funkčnosti) a také odhadu časové a paměťové složitosti. Součástí řešení úlohy P–I–3 je i zápis navrženého algoritmu ve formě zdrojového kódu nebo pseudokódu. V úloze P–I–4 je potřeba popsat požadovanou magickou síť a dokázat, že splňuje zadané vlastnosti; pokud požadovaná síť neexistuje, je nutné její neexistenci zdůvodnit. Řešení obou teoretických úloh odevzdávejte ve formě souboru typu PDF přes výše uvedené webové rozhraní. Řešení všech úloh můžete odevzdávat do 15. listopadu 2014. Opravená řešení a seznam postupujících do krajského kola najdete na webových stránkách olympiády na adrese http://mo.mff.cuni.cz/, kde jsou také k dispozici další informace o kategorii P.
P–I–1 Mezery Textové editory a obdobné programy pro přípravu textů se snaží, aby jimi vytvořené texty vypadaly esteticky co nejlépe. Podíváte-li se například na toto zadání, všimnete si, že konce všech řádků v odstavci kromě posledního jsou zarovnané přesně pod sebou. Aby toto bylo možné, ne všechny mezery mají stejnou šířku. Je ovšem nežádoucí, aby na některém řádku byly mezery příliš široké nebo naopak příliš úzké. Proto může být vhodné také změnit zalomení řádků. Editory samozřejmě berou do úvahy i další možnosti a omezení (rozdělování slov, řádek by neměl končit předložkou apod.), kterými se ale pro účely této úlohy nebudeme zabývat. Soutěžní úloha. Je zadán odstavec textu. Určete jeho rozdělení na řádky tak, aby velikosti mezer byly co nejbližší jejich optimální hodnotě. Formát vstupu: Vstupem je posloupnost slov (složených pouze z malých a velkých písmen latinské abecedy) oddělených mezerami či konci řádků. Každý řádek obsahuje nanejvýš 200 znaků, každé slovo má nejvýše 29 písmen. Celý text má nejvýše 100 000 slov. Formát výstupu: Výstupem je posloupnost vstupních slov ve stejném pořadí, lišící se pouze rozložením na řádky. Délka každého řádku výstupu smí být nejvýše 60 znaků (včetně mezer) a na každém řádku kromě posledního musí být alespoň dvě slova. Bodování Pokud vaše řešení neskončí pro některý z testovacích vstupů v časovém limitu či jeho výstup nesplňuje dané podmínky, nezíská za tento testovací vstup žádné body. 7
Jinak pro každý řádek výstupu kromě posledního určíme šířku mezer tímto způsobem (který předpokládá, že délka řádku je 60 a všechna písmena mají stejnou šířku 1): šířka mezer =
60 − počet písmen na řádku . počet slov na řádku − 1
Dále určíme chybu řádku tímto způsobem (za každou mezeru započítáme druhou mocninu její odchylky od optimální šířky 1; díky použití druhé mocniny podstatně více penalizujeme neesteticky vypadající velké mezery): chyba = (počet slov na řádku − 1) · (šířka mezer − 1)2 . Chyba celého odstavce je součet chyb jeho řádků. Vaše řešení pak za tento testovací vstup obdrží 1 + chyba optimálního řešení 1 + chyba vašeho řešení
bodů.
Body za všech 10 testovacích vstupů pak sečteme a výsledek zaokrouhlíme na nejbližší celé číslo. V sedmi z testovacích vstupů bude mít text nejvýše 1 000 slov. Ve třech z nich bude mít optimální řešení nejvýše 5 řádků. Příklad Pro vstup Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorper mi quis pretium diam Praesent volutpat at dolor nec mollis Praesent at odio non metus ornare egestas Nullam justo libero luctus vitae tortor vel posuere laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae ullamcorper diam je optimální následující výstup: Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae ullamcorper diam 8
Jeho první řádek má 8 mezer délky 1,000, druhý má 8 mezer délky 1,125, třetí má 8 mezer délky 1,750, čtvrtý má 7 mezer délky 1,429, pátý má 8 mezer délky 1,375 a šestý (tedy předposlední) má 4 mezery délky 1,750. Celková chyba tedy je 8 · 0,0002 + 8 · 0,1252 + 8 · 0,7502 + 7 · 0,4292 + 8 · · 0,3752 + 4 · 0,7502 ≈ 9,286. Naproti tomu vydá-li vaše řešení výstup Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae ullamcorper diam s celkovou chybou 12,111 (první řádek 8 mezer délky 1,000, druhý 8 mezer délky 1,125, třetí 9 mezer délky 1,222, čtvrtý 6 mezer délky 2,167, pátý 8 mezer délky 1,375 a šestý 4 mezery délky 1,750), získá za něj 0,785 bodu. Kdyby stejně úspěšně řešilo všech 10 testovacích vstupů, získá 8 bodů. P–I–2 Rušení stanic Radní v Kocourkově řeší problém, proč jsou poslední dobou obyvatelé města tak bledí. Napadlo je, že za to může nedostatek sluníčka. Proto se rozhodli, že zruší ve městě metro a lidé budou nuceni strávit víc času venku. Aby však změna nebyla pro obyvatele příliš náhlá, rozhodli se, že budou metro rušit postupně po jednotlivých stanicích. Navíc by chtěli, aby zbylá síť metra i po zrušení několika stanic zůstala souvislá — tedy aby se mezi každými dvěma zbylými stanicemi bylo možné dopravit (třeba i s několika přestupy), aniž by bylo potřeba projet zrušenou stanicí. Pomůžete radním rozhodnout, v jakém pořadí mají rušit stanice metra? Soutěžní úloha. Je zadána souvislá síť metra s N stanicemi očíslovanými od 1 do N a s M obousměrnými linkami mezi některými dvojicemi stanic. Vypište čísla všech stanic v pořadí, ve kterém by bylo možné je ze sítě postupně odebírat, aniž by zbývající síť v kterémkoli okamžiku přestala být souvislá. Formát vstupu: Program čte vstupní data ze standardního vstupu. První řádek obsahuje dvě celá čísla N , M oddělená mezerou (N ≧ 1, M ≧ 0), udávající po řadě počet stanic a počet linek v síti. Každý z následujících M řádků obsahuje dvě celá čísla od 1 do N , udávající dvojici stanic, které jsou spojeny linkou. Můžete předpokládat, že žádná linka se ve vstupu neobjeví dvakrát a žádná stanice není spojena sama se sebou. 9
Formát výstupu: Program vypíše na standardní výstup jediný řádek. Na něm bude N mezerami oddělených čísel udávajících pořadí, v jakém mají být stanice odstraněny. Pokud je více možných řešení, vypište libovolné z nich. Příklady Výstup: Vstup: 1 2 3 4 5 5 4 1 2 2 3 3 4 4 5 Další možná řešení jsou například 5 4 3 2 1, 5 1 4 2 3 nebo 1 2 5 3 4. Výstup: Vstup: 1 4 5 3 7 2 6 7 10 1 4 4 5 5 1 5 2 2 3 3 4 2 6 5 7 2 7 6 7 Uvedený výstup je jednou z mnoha správných odpovědí. Bodování Plných 10 bodů obdrží správné řešení, které efektivně vyřeší libovolný vstup s N ≦ 1 000 000 a M ≦ 10 000 000. Až 5 bodů získá správné řešení, které efektivně vyřeší libovolný vstup s N ≦ 1 000 a M ≦ 10 000. P–I–3 Ztracený paket Při přenosu velkých souborů po síti je nutné je rozdělit na menší kusy (pakety), které jsou doručovány samostatně. Při doručování není zaručeno zachování pořadí paketů. Aby je přijímající počítač dokázal správně spojit, pakety jsou očíslovány od 1 do n dle pořadí, v jakém po sobě následují v souboru. Na přijímající počítač zatím dorazilo n − 1 z n odeslaných paketů, jeden se tedy ztratil. Abychom mohli odesílající počítač požádat o jeho znovuzaslání, potřebujeme určit číslo tohoto ztraceného paketu. Přijaté 10
pakety jsme zatím neměli čas nijak zpracovat, máme je pouze uloženy na disku v pořadí, v jakém dorazily. Paketů je mnoho, nemůžeme si proto všechna jejich čísla uložit do paměti. Čtení dat z disku je ovšem pomalé a chceme jej minimalizovat. Formát vstupu: Váš program čte data ze souboru pakety.txt. Na jeho prvním řádku je přirozené číslo n (1 ≦ n ≦ 1 000 000 000). Na každém z n−1 následujících řádků je jedno přirozené číslo v rozsahu 1 až n včetně, udávající číslo paketu. Každé číslo paketu se v souboru vyskytuje nejvýše jednou, pořadí čísel paketů ve vstupním souboru může být libovolné. Formát výstupu: Výstupem je přirozené číslo v rozsahu 1 až n včetně, které se nevyskytuje mezi čísly paketů ve vstupním souboru. Příklad Vstup: 6 2 4 1 6 5
Výstup: 3
Bodování Přijatelná jsou pouze řešení, jejichž proměnné na běžném počítači používají nanejvýš 10 kB paměti (do tohoto limitu se počítá i dynamicky alokovaná paměť a zásobník návratových hodnot v rekurzivních programech; naopak se do něj nepočítají vnitřní proměnné standardních knihoven apod.). Plných 10 bodů obdrží takové řešení, které přečte vstupní soubor právě jednou a nepoužívá žádné další pomocné soubory. Až 7 bodů může obdržet řešení, které přečte vstupní soubor (či pomocné soubory srovnatelné velikosti) nejvýše 300krát. Libovolné jiné přijatelné řešení může obdržet až 4 body. P–I–4 Magická síť K této úloze se vztahuje studijní text uvedený na následujících stranách. Doporučujeme nejprve prostudovat studijní text a až potom se vrátit k samotným soutěžním úlohám. Soutěžní úloha. Úkol 1: Nechť nae(x, y, z) je omezení předepisující, že proměnné x, y a z nemají všechny stejnou hodnotu. Nechť one(x) je omezení předepisující, že proměnná x má hodnotu 1. Nalezněte síť, používající pouze omezení typu nae a one, která simuluje or. 11
Úkol 2: Nalezněte síť, používající pouze omezení typu nae, která simuluje eq(a, b), kde a a b jsou navzájem různé proměnné. Úkol 3: Ukažte, že pomocí nae nelze simulovat or. Studijní text Magická síť se skládá z omezení a proměnných. Každá proměnná může nabývat hodnot 0 nebo 1. Omezení pak předepisují podmínky, které ohodnocení proměnných musí splňovat. Například omezení xor(x, y, z) předepisuje, že z proměnných x, y a z jich lichý počet musí mít hodnotu 1, omezení or(x, y, z) předepisuje, že alespoň jedna z x, y a z musí mít hodnotu 1, omezení eq(x, y) předepisuje, že x a y musí mít stejnou hodnotu, a podobně. Proměnné se v jednom omezení mohou opakovat. Některé z proměnných jsou vstupní a můžeme jim nastavit konkrétní hodnotu. Po seslání příslušného zaklínadla se pak ostatním proměnným nastaví takové hodnoty, aby všechna omezení byla splněna. Pokud žádná taková volba hodnot neexistuje, zaklínadlo nás na to upozorní. V prvním případě říkáme, že magická síť zadaný vstup přijímá, ve druhém ho odmítá. Magická síť simuluje omezení O, jestliže přijímá právě stejné hodnoty proměnných jako omezení O. Příklad 1: Magickou síť zapisujme jako seznam typů omezení, k nimž do závorek budeme připisovat proměnné, na které jsou aplikovány. Síť xor(a, b, c), xor(b, c, d) tedy vynucuje, že lichý počet z proměnných a, b a c má hodnotu 1 a že lichý počet z proměnných b, c a d má hodnotu 1. Nechť a a d jsou vstupní proměnné této sítě. Jestliže a má hodnotu 0, pak právě jedna z proměnných b a c musí mít hodnotu 1, a proto d musí mít hodnotu 0. Naopak, má-li a hodnotu 1, pak hodnota proměnné b musí být stejná jako hodnota proměnné c, a proto d musí mít hodnotu 1. Tato magická síť tedy přijímá právě ty vstupy, kde a a d mají stejnou hodnotu, a simuluje tedy omezení eq(a, d). Obecněji: Typicky nás bude zajímat, která omezení jdou vyjádřit pomocí jiných. Říkáme, že množina typů omezení {O1 , O2 , . . . , On } simuluje omezení O, jestliže existuje magická síť používající pouze omezení typu O1 , O2 , . . . , On , která simuluje O. Příklad 1 tedy ukazuje, že xor simuluje eq. Omezení O(x1 , . . . , xn ) nazveme slabé, jestliže zakazuje právě jednu kombinaci hodnot proměnných x1 , . . . , xn . Slabé omezení budeme zapisovat jako Sh1 h2 ...hn , kde h1 , . . . , hn jsou hodnoty proměnných, které zakazuje. Třeba omezení S001 (x, y, z) je splněno, jestliže x = 1 nebo y = 1 nebo z = 0, a omezení S000 je stejné jako or. Nechť satn označuje množinu všech slabých omezení s právě n proměnnými. 12
Příklad 2: sat3 simuluje xor, jelikož síť S000 (x, y, z), S011 (x, y, z), S101 (x, y, z), S110 (x, y, z) zakazuje všechny kombinace hodnot proměnných x, y a z, v nichž se hodnota 1 vyskytuje suděkrát. Příklad 3: Množina omezení sat2 nesimuluje or. Abychom si to dokázali, zaveďme si nejprve funkci maj se třemi vstupy. Ta bude vracet ten vstup, který se vyskytuje nejčastěji (proto se jí také někdy říká majorita). Tedy třeba maj (1, 1, 1) = maj (1, 0, 1) = 1 a maj (0, 0, 1) = 0. Uvažujme nyní libovolnou síť s omezeními z množiny sat2 . Nechť x1 , . . . , xn jsou proměnné této sítě. Řekněme, že by tato síť simulovala or(x1 , x2 , x3 ). Jelikož omezení OR je splněno pro hodnoty 1, 0 a 0, existuje nějaké přiřazení hodnot proměnným, které splňuje všechna omezení, x1 má hodnotu 1 a x2 a x3 mají hodnoty 0. Nechť ai označuje hodnotu proměnné xi v tomto přiřazení, pro i = 1, . . . , n. Obdobně existuje přiřazení s hodnotami bi splňující všechna omezení takové, že b2 = 1 a b1 = b3 = 0, a přiřazení s hodnotami ci splňující všechna omezení takové, že c3 = 1 a c1 = c2 = 0. Uvažme ohodnocení s hodnotami di = maj (ai , bi , ci ). Tvrdíme, že di také splňuje všechna omezení: Mějme nějaké omezení Sh1 h2 (xi , xj ) ze sítě. Pokud ai = bi a aj = bj , pak di = maj (ai , ai , ci ) = ai a dj = = maj (aj , aj , cj ) = aj splňuje podmínku Sh1 h2 , protože ji splňuje ai a aj . Proto předpokládejme, že ai ̸= bi nebo aj ̸= bj , a obdobně ai ̸= ci nebo aj ̸= cj a stejně tak bi ̸= ci nebo bj ̸= cj . Ze symetrie mezi i a j a mezi ohodnoceními a, b a c stačí uvažovat případ, že ai ̸= bi a ai ̸= ci . Z toho odvodíme, že bi = ci , a proto bj ̸= cj . Díky symetrii mezi b a c pak stačí uvažovat případ, že aj = bj a aj ̸= cj . Pak ale maj(ai , bi , ci ) = maj (ai , bi , bi ) = bi a maj(aj , bj , cj ) = maj (bj , bj , cj ) = bj , a proto di = bi a dj = bj splňuje podmínku Sh1 h2 . Povšimněme si, že d1 = maj (1, 0, 0) = 0 a obdobně d2 = d3 = 0. Ale omezení or(x1 , x2 , x3 ) předepisuje, že alespoň jedna z proměnných x1 , x2 a x3 má hodnotu 1, a proto v každé magické síti simulující or(x1 , x2 , x3 ) musí přiřazení hodnot di proměnným porušovat nějaké omezení. Uvažovaná síť tedy nesimuluje or(x1 , x2 , x3 ).
13
