Vzorová řešení a komentáře k 2. sérii
Řešení je k dispozici také ve formátu pdf.
Úloha č. 1
Stačí si uvědomit, že určitě budeme moct rozsvítit lampy označené prvočíslem, protože ty lze rozsvítit pouze vypínačem první lampy, která nefunguje, nebo jim přiřazeným vypínačem. Musíme tedy zapnout vypínač číslo 2, 3, 5, 7, 11, 13, 17, 19.
Tím řešení ještě nekončí, protože vypínače lampy také zhasínají. Máme tedy nyní zhaslé lampy číslo 6, 10, 12, 14, 15, 18, 20. Nyní nám stačí zapnout vždy vypínač s nejnižším, číslem, protože jinak nebude ta lampa zapnutá.
Zmáčkneme tedy 6. vypínač, který nám rozsvítí lampy 6, 12 a 18. Dále musíme zmáčknout 10. vypínač, který rozsvítí lampy 10 a 20. Poslední 2 zhasnuté lampy jsou 14 a 15, takže musíme zmáčknout 14. i 15. vypínač.
Celkem jsme tedy stiskli 12 vypínačů -- 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19.
Komentář: Většina z vás si neuvědomila, že vypínače lampy nejen rozsvěcí, ale také zhasínají. Jelikož to ale nebylo v zadání, takto odevzdané řešení jsem obodoval třemi body. Chtěl bych ale pochválit ty řešitele, kteří přišli nejen na zjednodušené řešení, ale i na řešení, kdy se lampy zhasínají, a poslali obě řešení.
Úloha č. 2
Ze zadání víme, že kostka ledu je kolmý hranol s obsahem průřezu \def\cm{\,{\rm cm}}9\cm^{2}. Objem kolmého hranolu můžeme vypočítat pomocí obecného vzorce:
kde Sp je obsah podstavy a v výška hranolu. V našem případě známe obsah kolmého průřezu, který ve vzorci odpovídá obsahu podstavy kolmého hranolu. Zbývá tedy určit výšku v vzhledem ke kolmému průřezu. Známe délky stran kolmých na průřez (můžeme je tedy považovat za výšky). Pro obsah použijeme průměrnou délku těchto stran:
Průměr délek může představovat např. překlopení přebývajících částí na koncích hranolu tak, že z nepravidelného tělesa vznikne lépe počitatelný kvádr.
Komentář: Většina řešitelů této úlohy ji vyřešila na plný počet. U řešení se správným výsledkem jsme strhávali 1 bod za nedostatečné odůvodnění postupu. V řešení musí být jasné, co (a proč) se počítá. Častou drobnou chybou byl předpoklad, že průřez je čtverec se stranami o délce 3\cm. Podle zadání to čtverec být nemusí. Tvar průřezu ale nebyl podstatný pro řešení, proto jsme za takovou úvahu nestrhávali žádné body.
Úloha č. 3
Střechu si rozdělíme na několik útvarů, u kterých snadno spočítáme objem. Nejprve si povšimněme části vyčnívající vlevo dole. Jde o rovnoběžný hranol, u něhož snadno umíme spočítat objem -- stačí vynásobit výšku střechy s jednou polovinou obsahu základny.
Nyní si uvědomme, že můžeme rozdělit střechu na tři takovéto hranoly s podstavami 12\times6, 10\times12, 12\times8 a na dva jehlany se čtvercovou podstavou délek 10 a 8. No ale takto jsem započítali jednu část dvakrát, a tak nezbývá než odečíst malý jehlan se čtvercovou podstavou délky 4.
Nakonec zbývá zjistit výšky výše popsaných útvarů. Což je však díky sklonu střechy snadné, stačí si vždy v kolmém průřezu, rozdělit trojúhelník na dva pravoúhlé rovnoramenné. Dostaneme tak postupně výšky -- 3,5,4 pro hranoly a 5,4,2 pro jehlany.
Celkem tedy dostáváme objem V=108+300+192+500/3+256/3-32/3=2524/3\doteq 841.
Úloha č. 4
První věc, kterou je třeba si uvědomit je to, že se král musí při každém pohybu posunout o 1 sloupec doprava. Může se posouvat šikmo dolů a šikmo nahoru tak, aby rozdíl pohybů nahoru a dolů byl 2.
Nejvhodnější postup je nakreslit si šachovnici (obr. vz241) tím způsobem, že na každé políčko si napíši počet cest, kterými se na něj dá dostat.
Tuto mřížku vyplňujeme následujícím způsobem:
1.krok:
Z políčka A3 se můžu dostat na políčka B2, B3, B4 - zapíši: 1
2.krok:
Na políčko C5 se dá dostat pouze z políčka B4 -- zapíši: 1.
Na políčko C4 se dá dostat z políček B3 a B4 -- zapíši: 1+1=2.
Na políčko C3 se dá dostat z políček B2, B3 a B4 -- zapíši: 1+1+1=3.
Na políčko C2 se dá dostat z políček B2 a B3 -- zapíši: 1+1=2.
Na políčko C1 se dá dostat pouze z políčka B2 -- zapíši: 1.
3.krok:
Na políčko D6 se dá dostat pouze z políčka C5 -- zapíši: 1.
Na políčko D5 se dá dostat z políček C4 a C5 -- zapíši: 2+1=3.
Na políčko D4 se dá dostat z políček C3, C4 a C5 -- zapíši: 3+2+1=6.
Na políčko D3 se dá dostat z políček C2, C3 a C4 -- zapíši: 2+3+2=7.
Na políčko D2 se dá dostat z políček C1, C2 a C3 -- zapíši: 1+2+3=6.
Na políčko D1 se dá dostat z políček C1 a C2 -- zapíši: 1+2=3.
Atd. Nakonec na políčko H5 napíšeme 50 + 90 + 126 = 266, takže král se z pole A3 na pole H5 může sedmi tahy dostat právě 266 různými způsoby.
Komentář: Nejčastější chybou bylo nesprávné stanovení prostoru, kde se může král pohybovat. Je třeba si uvědomit, že král může klesat pod úroveň cíle v případě, kdy dokáže včas vystoupat. Druhou nejčastější chybou byl pokus o počítání výčtem všech možností. U tohoto příkladu se šlo časem dopracovat k výsledku. U jiných byste mohli strávit pár století.
Úloha č. 5
Označíme součty jednotlivých řádků R_{1}, R_{2}, R_{3}, R_{4} a sloupců S_{1}, S_{2}, S_{3} a S_{4}. Součet všech sloupců S (S = S_{1} + S_{2} + S_{3} + S_{4}) je roven součtu všech řádků R (R = R_{1} + R_{2} + R_{3} + R_{4}). Pokud je tento součet sudý, pak R + S je sudé, jelikož součet dvou sudých čísel je sudý. Pokud je tento součet lichý, pak R + S je opět sudé, jelikož součet dvou lichých čísel je také sudý. Tedy součet všech dílčích součtů (myšleno součet řádku či součet sloupce) je sudý. Ale 5 lichých +\,3 sudé = liché. Dostáváme spor. Tedy výsledek 5:3 nemohl nastat a soused lhal.
Jiné možné řešení: Na hrací plán vepíšeme pouze sudá čísla, pak máme 8 sudých součtů a 0 lichých. Pokud jedno sudé číslo změníme na liché pak máme výsledek 6:2. Když budeme takto pokračovat, vždy změníme počet sudých i lichých řádků o dva (sloupec se změní ze sudého na lichý a řádek také ze sudého na lichý -- nebo naopak), nebo nezměníme žádný počet (řádek se změní ze sudého na lichý, ale sloupec z lichého na sudý). Proto bude výsledné skóre obsahovat pouze sudé součty.
Komentář: Tato úloha vyžadovala důkaz, který zdůvodní odpověď. To, že si zkusím několik her a výsledek 5:3 mi nevyjde, není důkaz. Důkazem by bylo prozkoumání všech možných výsledků, u takového množství (i kdybychom se omezili jen na hodnoty 1 a 2) nepředpokládám, že to někdo udělal. Pokud ano, je nutné tyto možnosti vypsat.
Spousta z vás řešila otázku: Jaký bude výsledek hry, pokud oba budou hrát nejlíp jak mohou? Tedy zkoumala optimální strategii pro oba hráče. Úloha se ale ptala na to, zda může v takovém čtverci být právě 5 lichých a 3 sudé součty. Nikde nebylo zmíněno, že oba hrají nejlépe, jak mohou. Kdyby například oba doplňovali čísla podle toho, co jim padne při hodu kostkou, může hra skončit 5:3? Za takové řešení jsem většinou dával 3 body (\pm 1 bod podle zdůvodnění).
Úloha č. 6
Jako první najdeme minimální řez (obr. vz262). Minimální řez je taková křivka, která rozdělí potrubí na dvě části s tím, že pramen a altán se nachází v opačných částech. Velikost řezu je rovna součtu maximálních průtoku trubek na tomto řezu. V našem potrubí je minimální řez vidět na obrázku. Jeho velikost je rovna součtu maxim všech protnutých trubek, tedy 5+1+3+4+2+4=19 l/s. Větší množství vody potrubím nemůže protéci, neboť touto hranicí jich více neproteče.
Pomocí Fordova-Fulkersonova algoritmu vytvoříme návrh toku vody a tím ověříme, zda jsme opravdu našli minimální řez. Tento algoritmus spočívá v tom, že si pokaždé vybereme libovolný tok z P do A. Na tomto toku najdeme nejmenší průtok. Tento průtok odečteme od všech průtoků na této trase, jeho velikost nám navíc udává, kolik vody jsme touto cestou dopravili do altánu. To opakujeme do okamžiku, kdy již neexistuje žádný nenulový tok. Poté již jen stačí sečíst objem vody dopravený všemi toky. V našem případě je to též 19 l/s.
Maximálně dokáže potrubí od pramene do altánu dovést 19 l/s.
Komentář: Mnoho z vás pouze hledalo optimální cestu. V případě, že jste to správně popsali, tak jste i tak dostali po pěti bodech, ale za samotný obrázek jsem dávala pouze tři body. Musím pochválit ty z vás, co použili i minimální tok. Velmi častým problémem bylo špatné pochopení zadání, kdy jste se domnívali, že čísla udávají dopravované litry nebo jste hledali pouze jednu trubku místo procházení celé sítě.
Úloha č. 7
Osová souměrnost podle přímky p nám zobrazí bod A do bodu A'. Nechť X je půsečík přímky p a úsečky DA'. Dokážeme, že cesta DXA je nejkratší. Mějme jinou cestu, která se dotkne potoka v libovolném bodě Y různém od X. Získáme tedy situaci jako je na obrázku (obr. vz272).
Z osové souměrnosti vyplývá, že XA = XA' a YA = YA'. Z trojúhelníkové nerovnosti v trojúhelníku DYA' plyne: DY + A'Y > DA'. Odtud
Cesta DXA je tedy kratší než DYA. A jelikož Y bylo libovolné, tak nalezená cesta je opravdu nejkratší.
Komentář: Úloha je poměrně známá, proto jsem bodoval přísně. Jedna velká skupina řešitelů zapomněla jakkoliv zdůvodnit svou konstrukci. I při takto jednoduché konstrukci není zřejmé, že vede k nejkratší cestě. Druhá velká skupina řešitelů konstrukci tipnula. Je možné konstrukci tipnout a pak dokázat, že je správně. To však nikdo neudělal. Poslední velká skupina se snažila k výsledku dojít metodou pokus--omyl. Metoda pokus--omyl funguje, pokud máme konečně mnoho variant a vyzkoušíme je opravdu všechny. Bodů na přímce je ale nekonečně mnoho, proto je po jednom vyzkoušet nejde.
Opravovali: 1. Jakub Ucháč, 2. Jan Hrůza, 3. Jiří Erhart, 4. Jiří Pelc, 5. Jiří Štrincl, 6. Eliška Vítková, 7. Martin Zimen a Kateřina Nová.
