Vzorová řešení a komentáře k 3. sérii

Řešení je k dispozici také ve formátu pdf.

Zadání naleznete zde.

Úloha č. 1

Nikdo přesně nevěděl, kdo měl tehdy směnu. Erik získal následující informace:

• Žádným dvěma dělníkům nezačíná směna najednou.
• Ben nesmí být ve službě, když je s ním Andrew, pokud s nimi neslouží i Charlie.
• Danovi začala služba před Fineganem.
• George šel do služby až po Andrewovi.
• George může být ve službě spolu s Andrewem, jen když je s nimi i Finegan.
• Charlie nepřišel do služby jako první ani jako poslední.
• Dan přišel po Benovi.
• Dan přijde, až když budou v práci alespoň tři další.

Nikdo jiný na molu ten den nepracoval. V jakém pořadí mohly začínat jejich směny? Jak se to změní, pokud bychom ještě věděli, že Andrew a Charlie nepřišli do práce těsně po sobě?

Řešení: Máme šest dělníků, které si můžeme označit počátečním písmenem jejich jména. Písmenem X označíme „někdo (jeden) z dělníků“. Dále si pro větší přehlednost získané informace označíme čísly od 1 do 8.

Nejsložitější jsou informace 2 a 5, proto si je rozebereme samostatně ještě před skládáním informací dohromady. Podrobně se podíváme na informaci 2: Ben nesmí být ve službě, když je s ním Andrew, pokud s nimi neslouží i Charlie. To znamená, že buď Charlie přijde mezi nimi, nebo přijde Charlie první a Andrew a Ben v libovolném pořadí. Jsou tedy možné všechny tyto možnosti: A C B, B C A, C A B a C B A. Podobně z informace 5 plynou možnosti: A F G, G F A, F A G a F G A.

Nyní můžeme začít hledat pořadí, v jakém všichni dělníci přišli. Z první informace víme, že hledáme 6 různých příchodů.

Z poslední (8.) informace zjistíme, že Dan může přijít 4., 5. nebo 6. Z informace 3 víme, že Dan nepřišel poslední, protože mu začala služba před Fineganem. Z informace 5 víme, že George a Andrew nemohou být oba před Finegenem, musí aspoň jeden z nich být za ním, a tedy Finegan nesmí být poslední, zbyde na něj jen 5. místo. A Dan musí být čtvrtý. V tuto chvíli víme X X X D F X. Z informace 4 bude za Fineganem George. Máme jasné pořadí posledních tří dělníků: X X X D F G.

Zbývají dělníci Andrew, Ben a Charlie. Charlie podle 6 nebude první, může tedy být 2. nebo 3. Podle informace 2 víme, že nemůže být 3., protože to by byli Andrew a Ben spolu bez něj. Charlie bude tedy druhý. Pořadí je X C X D F G. Žádná další informace neříká nic dalšího o Andrewovi ani Benovi, na prvním a třetím místě mohou být oba. Překontrolujeme, že obě pořadí splňují všechny podmínky. Jsou tedy pouze dvě možnosti, jak dělníci mohli přijít: A C B D F G a B C A D F G.

Víme-li navíc, že Charlie a Andrew nepřišli těsně po sobě, tak neexistuje pořadí, v jakém by mohli přijít, protože v jednom z nalezených přijde Charlie těsně po Andrewovi a v druhém těsně před ním.

Komentář: Tuto úlohu jsem bodovala následovně: každé pořadí, jak mohli přijít, za 2 body, správná odpověď na doplňkovou otázku 1 bod. Spousta řešitelů získala plný počet bodů, za což bych je chtěla pochválit.

Nejčastější chybou bylo nerozlišování toho, když „někdo přišel po někom“ od „někdo přišel těsně po někom“, v prvním případě mezi nimi mohl ještě někdo přijít, naopak v druhém ne.

Úloha č. 2

Erik musí navštívit policejní komisariát na Králově náměstí, pobřežní stráž na Westfálské ulici a svoji policejní stanici na Lundské ulici. Přitom se chce zastavit i ve své oblíbené restauraci na Rybném trhu. Bude muset cestovat koněspřežnou drahou nebo vlakem.

Z Rybného trhu se může dostat koňkou č. 14 na Královo náměstí, anebo modrým vlakem na Westfálskou.

Z Westfálské se může dostat s přestupem koňkami č. 5 a 8 na Královo náměstí nebo jet na Lundskou buď pětkou, nebo zeleným vlakem.

Z Lundské může jet na Královo náměstí buď koňkou č. 1, nebo s přestupem zeleným a šedým vlakem.

Začít může kdekoli, všechny popsané spoje jezdí obousměrně. Může Erik cestovat tak, aby použil každou z uvedených linek hromadné dopravy právě jednou?

Řešení: Vyskytla se dvě různá zadání, která jste řešili. Liší se v koňce č. 1 (1), která vede mezi Lundskou (L) a Královým náměstím (K). Před řešením jednotlivých možností ještě probereme pár obecných poznatků.

Problém činí linky s přestupem. V zadání není jednoznačně řečeno, kde je přestup. Protože ale vede zelený vlak (Z) a koňka č. 5 (5) mezi Westfálskou (W) a L, musí přestup být mezi W a K (ozn. P_{2}), resp. L a K (ozn. P_{1}). Později je přestup mezi W a K umístěn do L a přestup mezi L a K umístěn do W. U některých řešení se vyskytly přestupní body mezi L a W a argumentace, že pak je více vrcholů s lichým počtem cest. Ovšem můžeme ignorovat cestu z přestupního bodu z 8 na 5 mezi W a L, která vede do W, protože 5 je využita při cestě z P_{1} do L, analogicky s druhým přestupem – viz obr. vz321. Při využívání těchto spojů, tedy např. při cestě z L na K, musí jet Erik šedým vlakem (Š) spolu se Z, musí na Z přestoupit. Určitě už tedy pak nebude moci použít Z mezi W a L. Obdobně pro cestu mezi L a W nepoužije spoj 5, protože ho využije při cestě z K do W přes L.

Ještě si označíme zkratkami zbylé spoje a místa analogicky, jak už jsem začal. Modrý vlak M, koňky dle jejich čísel a Rybný trh R.

Ptáme se, zda je schopen Erik použít každý spoj právě jednou a objet všechna místa. Stačí nám tedy najít nějakou cestu, která tyto podmínky splní. Není podmínkou, že bychom nějaké místo nesměli navštívit vícekrát, můžeme si to dovolit.

Nejprve vyřešme současné zadání, tedy s koňkou č. 1 mezi L a K. Nakresleme si schéma jednotlivých cest – viz obr. vz323. Z každého místa vede sudý počet cest. Znamená to, že můžeme vyrazit z jakéhokoli místa a opět se do něj vrátíme. Začněme třeba na K (můžeme začít kdekoliv). Máme spoustu možností, stačí jedna, tedy např. cesta: K(14) \rightarrow R(M) \rightarrow W(5,8) \rightarrow K(Š,Z) \rightarrow L(1) \rightarrow K.

Teď se podívejme na druhou možnost, bez koňky č. 1 (viz obr. vz322). Máme zde dvě místa (vrcholy) s lichým počtem a dvě se sudým počtem cest. Aby úloha měla řešení, musíme začít v jednom z míst s lichým počtem cest a skončit v tom druhém místě s lichým počtem cest. Tato místa jsou K a L. Možná cesta je tedy např.: K(14) \rightarrow R(M) \rightarrow W(5,8) \rightarrow K(Š,Z) \rightarrow L. Tedy stejná jako v předchozím odstavci popsaná jen bez poslední cesty koňkou č. 1.

Závěr je, že Erik může použít všechny spoje právě jednou a navštívit všechna místa.

Komentář: Jak jsem zmínil v řešení, vyskytl se problém s koňkou č. 1. Pokud bylo řešení bez ní správné, uznával jsem ho a nijak nepenalizoval.

Vyskytl se opět problém s postupem. Ač je to celkem snadná úloha, je nutné napsat, jak jste tu cestu vymysleli. Nakreslit schéma spojů/možností. Udělat nějaké pozorování – počet cest z vrcholů, nemožnost použití linky 5 mezi W a L kvůli přestupu mezi W a K a kombinaci s linkou 8. Pokud bylo alespoň schéma, řešení a odpověď, nestrhával jsem body. Odpověď nebo závěr je důležitý. Tím, že napíšete nějakou trasu (ač fungující), tím neříkáte nic. Je to z toho jasné, ale pouze sekvence čísel a písmen nic neříká. Obzvlášť pokud na papíru není nic jiného. Je nutné napsat, co z toho plyne, jak jste na to přišli. Pokud chyběl závěr a postup či schéma, strhával jsem bod.

Chyby, kdy bylo 5 a Z využito víckrát, jsem penalizoval ztrátou bodu, pokud byl postup či schéma a bylo jasné, že je to jen nepozorností či jinou malou chybou. Bez postupu či schématu bohužel 0 bodů.

Úloha č. 3

Studenti si tajně vytvořili stroj, který vyrábí dlaždice ve tvaru stejných konvexních čtyřúhelníků. Je možné těmito dlaždicemi pokrýt podlahu (vyjma okrajů místnosti) tak, aby v dlažbě nebyly díry, bez ohledu na to, jak tyto čtyřúhelníky vypadají?

Řešení: Mějme obecný konvexní čtyřúhelník ABCD s úhly \alpha, \beta, \gamma a \delta.

Pokud s ním chci vyskládat celou rovinu, tak musím přikládat k sobě stejně dlouhé strany, a zároveň úhel 360° získám jen složením všech úhlů (proto v každém bodu lepení musí být každý úhel právě jednou).

Zkusím tedy dát dva obecné čtyřúhelníky nejdelší stranou k sobě (nebo kteroukoliv stejnou stranou). Na to mám dvě možnosti. Jednu posunutím a otočením a druhou obrácením, posunutím a otočením (vznikne středově, nebo osově symetrický šestiúhelník). Navíc, pokud použiji obrácení (osovou symetrii), tak v obou vrcholech sčítám dvakrát stejný úhel, a proto po takovémto přiložení už celou rovinu nepokryji (viz obr. vz332).

Pokud ale použiji středovou symetrii, tak získám středově symetrický (tedy rovnoběžný) šestiúhelník, který jde posunutím sám k sobě přiložit ke všem stranám (viz obr. vz333).

Proto pokud s ním vyplňuji tuto mřížku, tak vyplním celou rovinu (viz obr. vz334).

Komentář: Většina z vás na to, že podlaha těmito útvary pokrýt jde, přišla, ale často jsem strhával jeden bod, když nebylo zdůvodněno, že tímto útvarem půjde pokrýt celá rovina, i když někdo měl návod, jak je k sobě přikládat, a že to kolem prvního (nebo prvních dvou) funguje.

Úloha č. 4

Žebřík se opírá o regál. Jeho délka je přirozené číslo, stejně tak výška, ve které se opírá o regál, a vzdálenost regálu od místa, kde se žebřík opírá o podlahu. Může existovat takový žebřík, který by šlo opřít dvěma různými způsoby, aby všechny vzdálenosti byly různá přirozená čísla? Pouhé prohození těchto délek nestačí.

Řešení: Pokud si dobře rozmyslíme úlohu, jde vlastně o to najít dva různé pravoúhlé trojúhelníky takové, že všechny strany jsou přirozenými čísly a zároveň mají oba dva trojúhelníky stejně dlouhou přeponu. Trojici přirozených čísel a, b, c, které jsou stranami pravoúhlého trojúhelníka se říká pythagorejská trojice. Pro takovouto trojici platí, že stranami pravoúhlého trojúhelníku budou i jakékoli násobky trojice. Lze to dokázat zcela jednoduše: platí a^{2}+b^{2}=c^{2}. Pro n-násobek všech délek stran bude platit: (n\cdot a)^{2}+(n\cdot b)^{2}= n^{2}\cdot a^{2}+n^{2}\cdot b^{2} =n^{2}\cdot(a^{2}+b^{2})=n^{2} \cdot c^{2}.

Teď už jen vezmeme dvě pythagorejské trojice a najdeme společný násobek přepon. Nejmenší pythagorejské trojice jsou 3, 4, 5 a 5, 12, 13. Společný násobek přepon je 65, takže naše hledané trojúhelníky budou mít strany 39, 52, 65 a 25, 60, 65.

Komentář: Zadání znělo, zda tento žebřík může existovat. Takže pokud jste našli jedno jakékoli řešení, že žebřík existovat mohl, úlohu jste tím vyřešili. Body jsem strhávala za chybějící či nedostatečný postup, většinou jsem dávala alespoň jeden bod za snahu. Různá „vychytralá“ řešení – pokud budeme udávat délku žebříku v mikrometrech, vždycky to bude přirozené číslo – jsem hodnotila nulou.

Úloha č. 5

Vyšlo najevo, že Peter (tak se jmenoval) nerad pere. Má 5 párů černých, 2 páry tmavošedých, 3 páry světlošedých a 5 kusů bílých (byly 3 páry, ale jednu ztratil – podezírá spolubydlícího) ponožek. Aby si zachoval systém, chce mít na levé noze vždy tmavší ponožku než na pravé noze (nikoli stejně tmavou). Kolika způsoby si může obléct ponožky? V každém páru jsou ponožky stejné, ale páry jsou navzájem rozdílné.

Řešení: Než se pustíme do samotného řešení, musíme si pořádně uvědomit, co se po nás vlastně chce. V zadání se píše, že Peter měl 5 párů černých, 2 páry tmavošedých, 3 páry světlošedých a 2 páry bílých ponožek. K tomu měl navíc jednu samostatnou bílou ponožku. Všechny páry byly navzájem různé, ale v rámci páru byly ponožky identické. Peter tedy měl 5+2+3+2+1=13 navzájem různých ponožek. Všechny ostatní už byly stejné, jako některá z těch třinácti. Proto stačí, když budeme počítat jen s těmi třinácti navzájem různými.

Peter má 5 navzájem různých černých ponožek. Každou z nich může kombinovat se všemi ponožkami ostatních barev (těch má 13-5=8). Proto má Peter 5\cdot8=40 možností, jak zkombinovat černé ponožky se světlejšími.

Obdobně má Peter 2 navzájem různé tmavošedé ponožky. Každou může kombinovat se všemi světlošedými a bílými ponožkami (těch má 13-5-2=6). Proto má Peter 2\cdot6=12 možností, jak zkombinovat tmavošedé ponožky se světlejšími.

Nakonec má Peter 3 navzájem různé světlošedé ponožky. Každou může kombinovat se všemi bílými ponožkami (ty má 2+1=3). Proto má Peter 3\cdot3=9 možností, jak zkombinovat světlošedé ponožky se světlejšími. Celkem má tedy Peter 40+12+9=61 možností, jak si obléci ponožky tak, aby měl na levé noze vždy tmavší ponožku než na noze pravé.

Komentář: Úloha byla spíše jednodušší a spoustě z vás se jí podařilo úspěšně a často i pěkně vyřešit. Na druhou stranu se našlo dost z vás, kteří zapomněli na některou z podmínek v zadání. Nejčastěji jste zapomínali, že Peter nechce nosit dvě stejně tmavé ponožky, a proto vám vycházelo 78 možností, jak ponožky kombinovat. Druhou nejčastější chybou bylo, že jste všechny ponožky stejné barvy považovali za stejné, a tak vám vycházelo jen šest možností, jak může Peter ponožky nosit. Pokud si neumíte představit, že mohou existovat dvě různé ponožky stejné barvy, nahlédněte doma do šuplíku. Minimálně kluci určitě objeví dvoje stejně černé ponožky s různým vzorkem nebo různé délky. Nakonec bych chtěl pochválit, že většina došlých řešení byla doprovozená pěkným slovním komentářem. Toho si cením a prosím vás, pokračujte v tom. :-)

Úloha č. 6

Profesor Compton používal pořád tutéž sbírku úloh, v níž bylo 1\,155 příkladů. Každému žákovi zadal nějakého dělitele 1\,155, a on musel potom vyřešit všechny úlohy označené násobkem zadaného čísla. Každý student opíše všechny úkoly, které již byly někým vyřešené. Kolika studentům může profesor postupně zadat čísla tak, aby každý z nich musel sám vyřešit alespoň jednu úlohu?

Řešení: Profesor Compton zadává jen ty úlohy, jejichž čísla dělí 1\,155. Můžeme tedy vybírat jen z množiny dělitelů čísla 1\,155 a ostatní čísla úplně vynechat. Začneme rozložením čísla 1\,155 na jeho prvočíselné dělitele: 1\,155 = 3\cdot 5\cdot 7\cdot 11.

Způsobů, jak ze zjištěného prvočíselného rozkladu dostat všechny dělitele zadaného čísla, je spousta. Uvedu pro příklad dva.

Nejelegantnější z možností je si uvědomit, že nepotřebujeme vědět ani tak, jaká to jsou čísla, ale spíš kolik jich je. Pak můžeme využít úvah, že každý dělitel se musí skládat jenom z daných prvočísel a navíc u každého z těchto prvočísel mohou nastat právě dvě možnosti („stavy“) – dělitel ho buď obsahuje, nebo ne. V našem případě máme čtyři prvočísla, každé má dva „stavy“, tedy počet dělitelů čísla 1\,155 je 2^{4} = 16.

Druhý způsob je vlastně stejný, jen více popisný, a proto možná lépe pochopitelný. Vyjdeme zde vlastně ze stejného faktu, tj. že každý dělitel čísla se může skládat jedině z prvočísel prvočíselného rozkladu čísla. Musíme tedy najít všechny kombinace zjištěných prvočísel (3, 5, 7, 11 pro jednoprvkové, 15, 21, 33, 35, 55, 77 pro dvouprvkové, 105, 165, 231, 385 pro tříprvkové a 1\,155 zahrneme-li všechna prvočísla). V tomto případě, ale nesmíme zapomenout na jedničku, která číslo 1\,155 samozřejmě také dělí, ale protože ji nebereme jako prvočíslo, tak jsme ji z rozkladu vynechali. S ní už dostáváme plný počet dělitelů, tedy 16.

Pointou příkladu pak bylo, uvědomit si, že když profesor zadá např. číslo 15, tak vybraný žák vyřeší všechny úlohy s násobkem tohoto čísla, tedy i všechny další dělitele 1,155, které obsahují 15 (resp. 3\cdot 5) a tedy 105, 165 a 1\,155. Chce však zadat úlohy co největšímu počtu žáků, a proto musí začínat zadávání úloh od nejvyššího čísla.

Profesor tedy může zadat úlohy šestnácti studentům.

Komentář: Body jsem rozdával za hlavní myšlenku (že profesor bude zadávat čísla sestupně). Bodík se také dal získat za správné určení dělitelů čísla.

Úloha č. 7

Orichalciové jádro je zdroj energie, který vyzařuje všemi směry nebezpečné paprsky. Je proto potřeba kolem něj postavit ochranný štít z koulí tak, aby se nedotýkaly jádra, ale zároveň aby žádné paprsky nepronikly ven. Je možné postavit takový štít z osmi koulí?

Řešení: Nejjednoduší a nejčastější řešení bylo umístit koule do vrcholů dvou čtyřstěnů, které budou do sebe vnořené (tedy vnitřní bude výrazně menší). Tento obrázek se špatně kreslí, proto tady je jen jeden z těchto čtyřstěnů (obr. vz371).

Z pohledu zevnitř (obr. vz372) je jasné, že se musejí vnější koule dotýkat, aby nic neuniklo. Pokud se ale dotýkají, tak opravdu žádný paprsek neunikne.

Další skupina řešení spočívala na dvou obrovských koulích, kterým stačí, aby ostatní koule utvořili kolem jádra nějaký prstenec s nenulovou výškou. Tato řešení jsou sice do skříně nepraktické, ale zadání odpovídají (menšina z řešitelů s takovýmto postupem přišla). Pohled na tyto dvě obrovské koule s prstencem vypadá jako na obr. vz373.

Jak vytvořit tento prstenec je více způsobů. Nejjednoduší postup je s celkově osmi koulemi, tedy v rovině se šesti.

Pohled zevnitř pak vypadá jako na obrázku vz375.

Petr Khartskhaev vymyslel dokonce řešení za použití celkově jen šesti koulí, kdy na prstenec použil jen čtyři koule (obr. vz376).

Pokud tuto myšlenku ještě rozvinu, tak najdu i řešení za použití celkově pěti koulí (obr. vz377), které spočívá v tom, že jádro není mezi třemi koulemi uprostřed, ale u kraje, takže nevidí na žádný bod dotyku těchto tří koulí.

Komentář: Úlohu jsem považoval za těžší, proto jsem dával body za jakýkoliv správný postřeh.

Opravovali: 1. Lenka Vábková, 2. Jan Kadlec, 3. František Steinhauser, 4. Helena Molíková, 5. Jiří Erhart, 6. Jan Erhart, 7. František Steinhauser.