Vzorová řešení a komentáře k 1. sérii
Řešení je k dispozici také ve formátu pdf.
Úloha č. 1
Pro zjištění výdělku musíme nejprve spočítat, kolik lián vína je na vinici. To jde udělat hned několika způsoby. U všech si musíme uvědomit, že když předposlední řada má 85 lián, poslední má 87 lián. Úvahově nejjednodušší, ale početně nejpracnější, je ručně (nebo s pomocí kalkulačky) sečíst řadu čísel 1+3+5+\cdots+85+87. Nejrychlejší způsob je znát vzorec pro výpočet aritmetické posloupnosti, který je v našem případě následující:
kde l je počet lián na vinici, r počet řad a v závorce je součet lián v první a poslední řadě.
Pokud tento vzorec neznáme, můžeme k němu dojít i úvahou. Součet lián v první a poslední řadě je 88, stejně jako součet lián v druhé a předposlední řadě (87+1=85+3=83+5=\cdots). Když doplníme každou řadu liánami tak, aby měla 88 lián, přidali jsme 87+85+...+3+1 lián, tedy další vinici. O počtu lián na vinici můžeme napsat:
čímž jsme dostali už zmíněný vzorec.
Už zbývá jen zjistit, kolik řad má vinice. Počet lián v každé řadě tvoří lichá čísla do 87 (včetně). V každé desítce je 5 lichých čísel (1,3,5,7,9), lichých čísel menších než 80 je tedy 40. Už chybí jen přičíst lichá čísla od 81 do 87. Na vinici je tedy 44 řad.
Tento výsledek dosadíme do vzorce:
stejný výsledek vyjde i jiným správným způsobem výpočtu. Když ze tří lián vyrobíme pikogalón vína, z celé vinice vyrobíme 1936/3 \doteq 645,333 pikogalónů vína. Každý pikogalón vinař prodá za 35 pikokorun, z veškeré sklizně pak vinař vydělá 1936/3 \cdot 35\doteq 22\,586{,}667 pikokorun.
Komentář: Nejsložitější částí úlohy byl součet lián vína na vinici. Mnoho řešitelů mechanicky sečetla počty lián v jednotlivých řadách, někteří použili součet aritmetických posloupností nebo vlastní nápaditý postup. Za správnou odpověď jsme dávali plný počet bodů, pokud výsledek správný nebyl, bodovali jsme podle postupu řešení a správnosti úvah. Za numerické chyby jsme body nestrhávali.
Úloha č. 2
Pro potvrzení, nebo vyvrácení tohoto tvrzení použijeme následující postup:
Napřed sečteme plochy všech plachet. Zadaná jednotka byla dračí tlapy čtvereční – dt^{2}. Ale na jednotce vlastně nezáleží.
Pokud by neexistovalo místo, kde by se všechny tři vrstvy překrývaly, louka by musela být pokryta maximálně dvěma vrstvami plachet. Maximální využitelná plocha při takovém rozložení by byla:
Vzhledem k nerovnosti 12 \,dt^{2} < 13 \,dt^{2} můžeme říct, že při jakémkoliv rozložení plachet by se plachty na louku ve dvou vrstvách nevešly.
Toto vyplívá i z Dirichletova principu. Tedy že máme 13 \,dt^{2} a pokud je máme rozložit mezi dvě vrstvy louky o maximální ploše 6\, dt^{2}, dojdeme k závěru, že alespoň 1\, dt^{2} musí být ve třetí vrstvě louky.
Komentář: Šlo o poměrně jednoduchou úlohu, a tak jsem mohl povětšinou udělovat plný počet bodů.
Úloha č. 3
Počet ovcí si označíme x a počet pštrosů y. Z informace o počtu nohou získáme rovnici:
Z informace: stádo má 45 vztyčených hlav a dvě sedminy pštrosů mají hlavu v písku, dostaneme tuto rovnici:
Druhou rovnici si upravíme do tvaru:
Z první vyjádříme y = 81 - 2x a následně dosadíme do druhé:
Nyní nám zbývá spočítat počet ovcí – tedy x.
Ve stádě je tedy 30 ovcí.
Komentář: Někteří úlohu řešil metodou pokus omyl. Tedy uvědomili si, že počet pštrosů musí být dělitelný 7. Poté k jednotlivím násobkům 7 dopočítali počet ovcí, dokud jim nevyšlo řešení splňující obě podmíky v zadání. Našli se i tací, kteří špatně pochopili zadání (vztyčené krky přiřadily pouze pštrosům). Tím si celou úlohu značně zjednodušili, protže neřešili klasickou soustavu rovnic. Za takové řešení jsem udělil pouze 3 body.
Úloha č. 4
Jestliže Mariánovi vyjde po dělení palindromů 11 vždy 0, pravděpodobně bude v tomto příkladu hrát roli dělitelnost 11. Podíváme-li se například na Wikipedii, zjistíme, že číslo je dělitelné 11 právě tehdy, když splňuje jednu z následujících podmínek:
- je-li rozdíl součtu číslic na sudém a lichém místě dělitelný jedenácti,
- je-li součet jednotlivých dvojčíslí dělitelný 11,
- je-li rozdíl trojčíslí na sudých a lichých místech dělitelný 11.
Pro tuto úlohu se zaměříme na první podmínku.
Napíšeme si obecný palindrom jako ABCDEEDCBA, můžeme si všimnout, že se každá číslice nachází jednou na sudém a jednou na lichém místě. To znamená, že když sečteme číslice na sudém místě a ty na místě lichém a tyto součty od sebe odečteme, dostaneme výsledek roven 0 (ABCDE-ABCDE=0). Proto platí, že jsou všechny palindromy sudé délky dělitelné 11 beze zbytku.
Komentář: Výše uvedené řešení je nejrychlejší, pro správné vyřešení si stačí jen uvědomit nebo zjistit pravidla dělitelnosti 11. Pro řešení se dala použít i jiná z podmínek dělitelnosti, někteří z vás použili podmínku druhou. Dokázat, že jsou palindromy sudé délky vždy dělitelné 11, šlo i jinými, méně jednoduchými metodami. Zde bych chtěla vyzdvihnout řešení Tomáše Flídra, který pro důkaz použil matematickou indukci.
Úloha č. 5
Možností jak mince posunout bylo několik, na obrázku vz151) vidíte jednu z možností (prázdná kolečka označují přemístěné mince). Můžeme si všimnout, že pozice, na které musíme mince přesunout, jsou jednoznačně určené průsečíky přímek, které vedeme původními mincemi (obr. . Záleží tedy jen na tom, jaké mince odebereme.
Komentář: U této úlohy velká část využila toho, že v zadání nebylo explicitně uvedeno, jak jsou mince uspořádané. Na začátku si tak uspořádali mince ne do dvou pravidelných řad, ale tak, aby se jim lépe vytvářel výsledný útvar. Někteří šli dokonce ještě dál a brali mince jako nebodové útvary (takže jim dvě rovnoběžky mohly končit v jedné minci) nebo pokládali mince na sebe. Nic z toho jsme ale v zadání opravdu nezakázali, takže jsem za taková řešení žádné body nestrhávala. Velkou pochvalu si ale zaslouží ti řešitelé, kteří správně vyřešili původní (a těžší) úlohu.
Úloha č. 6
Úloha trochu navádí k tomu, že se nám bude hodit jak označovat vchody do místností, tak odmotávat a namotávat Ariadninu nit. Zkusme tedy vymyslet, jak bychom každou z možností mohli využít s ohledem na to, jak zapomnětlivého Thesea máme.
Co si počít s označováním vchodů?
Nejjednodušší možností, která se nabízí, je označovat všechny vchody stejně – řekněme křížkem. Pojďme proto zkusit, jestli by nám taková možnost nestačila. Hned dalším problémem, který se nabízí vyřešit je, zda označovat vchody před nebo po projití. Pokud bychom dveře označili před průchodem, získáme tu výhodu, že Theseovi můžeme v instrukcích říci jen: „označ dveře, do kterých půjdeš.“
Kdežto pokud by Theseus označoval dveře až teprve poté, co jimi projde, budeme mu muset důsledně popsat, které dveře má označit (protože s průchodem dveřmi zapomene i informaci, kterými dveřmi se do místnosti dostal). To s trochou snahy půjde, ale budeme muset vyřešit zvlášť případ, kdy Theseus namotával nit a kdy ji odmotával a celkové instrukce se tím patřičně prodlouží. My proto tuto možnost necháme čtenáři jako cvičení a zkusíme dveře označovat před průchodem.
Jak využít Ariadninu nit?
Je asi přímočaré, že pokud budeme postupovat dále v bludišti, budeme Ariadninu nit odmotávat, a pokud se budeme vracet (půjdeme vchodem, ze kterého vede nit), tak budeme nit namotávat zpět na klubko. Důležité ale je si uvědomit, že může nastat situace, kdy vejdeme do místnosti, skrze kterou už je nit jednou natažená. V takové situaci máme dvě možnosti.
Buď necháme nit překřížit a budeme pokračovat dále. Potom ale hrozí, že se nám tato situace bude několikrát opakovat a Theseus se na cestě zpět bude muset celý vynervovaný snažit nit rozmotat. Také by v tomto případě potřeboval delší nit. Nevíme, jak je labyrint rozlehlý, tak bude lepší to neriskovat, ale v principu by Theseus mohl postupovat i takto.
Druhou možností je, že Theseus nikdy svou nit nepřekříží. Tedy v situaci, kdy se ocitne v místnosti, skrze kterou už jeho nit vede, si označí vchod, kterým přišel (ze kterého vede nit k němu), a vrátí se do předchozí místnosti. Tak ušetří nit a zároveň bude mít jistotu, že než se vrátí po Ariadnině niti až do oné kritické místnosti, tak bude mít celou část bludiště dostupnou skrze označený vchod projitou. Přikloňme se proto k této možnosti.
Kuchařka pro Thesea
V předchozích odstavcích jsme si rozmysleli, jak používat Ariadninu nit a jak louč k označování vchodů. Při sepisování instrukcí ale ještě musíme mít na paměti, že náš Theseus v každé místnosti vše zapomene (včetně instrukce, kterou provedl v místnosti předchozí), a tak potřebuje seznam pokynů, který vždy od začátku přesně provede. Jak by tedy takový seznam mohl vypadat? Předpokládáme, že se Theseus právě nachází v místnosti.
- Vidíš Minotaura? Zabij ho a vrať se po Ariadnině niti do předchozí místnosti. Nit namotávej.
- Vede skrze místnost Ariadnina nit? Označ dveře, do kterých od Tebe vede nit, a projdi jimi do předchozí místnosti, zatímco namotáváš Ariadninu nit.
- Vede z místnosti alespoň jeden neoznačený vchod, ze kterého nevede Tvá nit? Vyber si libovolný, označ ho a projdi jím do další místnosti, zatímco odmotáváš Ariadninu nit.
- Všechny vchody v místnosti, když nepočítáme ten, ze kterého k Tobě vede nit, jsou označené? Vrať se do předchozí místnosti dveřmi, ze kterých k Tobě vede Ariadnina nit. Nit namotávej.
Závěr
Tento postup pro vyhledávání v bludišti je ve skutečnosti velmi dobře známý. V literatuře o teorii grafů byste ho našli pod názvem prohledávání do hloubky a patří do základní výbavy každého programátora.
Komentář: Byť se jedná o známý problém, tak uvědomujeme, že vymyslet řešení od úplného začátku je značně náročné. Proto jsme došlá řešení hodnotili velmi mírně. I tak zkusíme vyzdvihnout několik zádrhelů v došlých řešeních. Hodně z vás využívalo triku, kdy jste nechávali Thesea procházet labyrintem s pravou rukou na zdi. To by nejspíše úplně dobře nefungovalo s vyděšeným a zapomínajícím Theseem, ale i kdyby ano, tak tato metoda funguje dobře jen v labyrintech, které neobsahují cykly. V ostatních labyrintech sice Theseus vždy vyjde ven, ale nemusí metodou pravé ruky najít Minotaura.
Další častou chybou v úvaze bylo, že jste Theseovi podle stavu v aktuální místnosti určovali, jakou instrukcí má pokračovat v místnosti následující. To ale Theseus při vstupu do další místnosti zapomene. Poslední častější chybou bylo, že jste po Theseovi chtěli, aby označil dveře, kterými se dostal do aktuální místnosti. To ale chudák zapomněl ve chvíli, kdy vešel. Málokdo z vás už mu připojil popis, jak dveře, kterými přišel, poznat.
Na závěr bychom chtěli pochválit všechny, co se nebáli s touto úlohou popasovat a poslali své řešení. Úloha to nebyla jednoduchá a s úrovní došlých řešení jsme byli spokojeni.
Úloha č. 7
Každý učitel si musí přiťuknout (2n − 1) krát. Když si přiťukávají jeho dva sousedé, tak si nemůže přiťuknout s nikým, protože by si ťukal křížem přes ně. Minimálně je tedy třeba 2n kol.
Nyní je třeba dokázat, že je to možné. Aby se tak stalo, musí si každý učitel přiťuknout v každém kole, kromě jednoho. Učitele si představme jako vrcholy pravidelného 2n-úhelníku. Tento 2n-úhelník rozpůlíme osami symetrií (přímkami, které vedou buďto středy protějších hran, nebo protějšími vrcholy). Počet těchto os symetrií je 2n (obr. vz171).
Ke každé této ose přiřadíme jedno kolo přiťukávání. Přiťukávat si budou v daném kole takové dvojice učitelů, které lze spojit úsečkou kolmou na danou osu. Jelikož dvě kolmice na stejnou přímku jsou vzájemně rovnoběžky, tak je splněna podmínka o tom, aby se přiťuknutí nekřížila. Zároveň, protože žádné dvě z os symetrií nejsou rovnoběžné, tak jsou úsečky na ně kolmé různé. Pokud bude osa procházet středy stran, tak je každý vrchol propojen s jiným vrcholem – všichni učitelé si přiťukávají. Pokud osa prochází vrcholy, tak tyto dva vrcholy s ničím nespojuje (učitelé si nepřiťukávají). (Jsou kolmicí na danou osu spojeny sami se sebou).
Učitel si tedy bude přiťukávat v každém kole kromě jednoho, kdy jím prochází osa. Pokud bude n = 1, tak stačí n kol. Pro ostatní n je nejméně potřeba 2n kol.
Komentář: Nejčastější problém byl, že řešitelé správně vyřešili dva až tři případy a tvrdili, že to tak bude vycházet pořád, ale nenašli proč to tak bude. Další častá chyba byla, že téměř všichni řešitelé nezdůvodňovali, že to nejde udělat lépe, ale pokud k tomu nebyl žádný další nedostatek, tak jsem nic nestrhával.
Opravovali: 1. Jan Hrůza, 2. Jura Pelc, 3. Jiří Štrincl, 4. Barbora Šmídová, 5. Kateřina Nová, 6. Jiří Erhart a Jiří Frantál, 7. Magdaléna Mišinová a František Steinahuser.
