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

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

Zadání naleznete zde.

---

Úloha č. 1

Řekněme, že první mince váží n, druhá mince bude vážit 2n, třetí 4n, až do poslední mince, která váží 512n. Když sečteme hmotnosti všech mincí kromě poslední, dostaneme se k 511n, což je méně, než hmotnost poslední mince. Tím pádem víme, že poslední mince vždy převáží všechny ostatní.

Během každého vážení chceme vyřadit co nejvíce mincí, proto mince rozdělíme na dvě skupiny po pěti. Lehčí skupinu dáme pryč a těžší rozdělíme na dvě a tři mince. Lehčí skupinu opět vyřadíme. V horším případě nám zbude skupinka, ve které jsou 3 mince, tu rozdělíme na jednu a dvě mince. V horším případě bude těžší hromádka se dvěma mincemi, tu už jen rozdělíme napůl a těžší z mincí bude ta nejtěžší. Tím jsme našli nejtěžší minci na 4 vážení.

Komentář: Úloha byla dost jednoduchá, takže ji vyřešili téměř všichni správně.

Úloha č. 2

V zadání dělalo problém slovíčko „musí“. Většinou jste jej interpretovali jako „může“. Rozdíl je v tom, že v prvním případě je potřeba i dokázat, že zvýrazněním jiných než určených hran určeným směrem Eduard prohraje. V druhém případě je potřeba jen najít jednu hranu takovou, že jejím zvýrazněním určitým směrem Eduard vyhraje. Avšak i tato druhá varianta se ukázala být poměrně dost obtížnou. Ukážu zde tedy řešení obou interpretací.

Druhá interpretace

Nejprve ukážu řešení druhé, jednodušší interpretace. Zakládá se na myšlence, že Eduard nedá Markovi možnost vybrat si, jakou stranu zvýrazní.

První Eduardův krok bude vypadat jako na (Obr. vz421):

Marek nyní má na výběr dvě možnosti, které jsou ale symetrické podle osy čtverce. Proto stačí vybrat jednu z nich a ukázat pro ni, že Eduard dokáže Marka donutit, aby prohrál. Plánek bude vypadat jako na (Obr. vz422), kde černé šipky jsou Eduardovy tahy, šedé šipky jsou Markovy tahy.

V dalším tahu už musí Marek prohrát, takže řešení je hotovo. Existují i další řešení, za všemi ale stojí stejná myšlenka.

První interpretace

První interpretace má dvě řešení. V obou budeme používat očíslování vrcholů tabulky jako na obrázku (Obr. vz423):

• První řešení je asi složitější na sepsání. Jsou na něm ale dobře vidět další zajímavé myšlenky. V řešení podobných úloh, kde se něco děje a není jasné, jak se to bude dít, to může dost pomoci. V první z nich jde o hledání věcí, které navzdory změně zůstávají pořád stejné. Říká se jim invarianty. Jak uvidíte, tohoto cizího názvu se nemusíte vůbec bát.

První invariant v této úloze je následující. Pokud jeden hráč zvýrazní stranu z nuly do jedničky, tak další hráč musí zvýraznit stranu z jedničky do nuly. Protože hráči jsou dva a po tahu se střídají, tak jeden hráč bude zvýrazňovat pouze z nul do jedniček a druhý pouze z jedniček do nul.

Nyní si všimneme, že jedniček je v tabulce více než nul. Když Eduard začne zvýrazněním strany z nuly do jedničky, tak ubere sobě jednu jedničku, kam může zvýrazňovat a Markovi jednu nulu. Když zvýrazní dál Marek, tak ubere jen sobě nulu. V dalším tahu ubere Eduard sobě jedničku a takto se střídají až do konce. Jedniček, které nejsou součástí žádné zvýrazněné strany, proto bude pořád víc, než takových nul. To je další invariant.

Nyní bychom rádi řekli, že se tedy musíme dostat do situace, kdy zbývá právě jedna volná jednička, takže nezbývá žádná nula. Tudíž Eduard může táhnout a Marek ne. Vůbec ale není jasné, že Eduard na tu jednu volnou jedničku táhnout může. Dokážeme, že buďto tomu tak je, nebo zbývá právě jedna jednička a žádná nula v uzavřeném prostoru, kam můžou oba hráči táhnout (kde skončila poslední zvýrazněná strana).

Aby se zvýrazňováním dostali do omezeného prostoru, kde je více nul než jedniček, museli někdy rozdělit původní hrací plán tak, aby se do jedné volné části už nedokázali dostat. Ukážeme, že tomu Eduard dokáže zabránit.

Nyní provedeme další často používaný trik. Vezměme si případ, kdy se hrací plán rozdělí poprvé. Pokud se plán rozděluje, někdy to poprvé být musí. Pokud v kroku, kdy bude zvýrazněna strana buďto do jedné, nebo do druhé části, táhne Eduard, tak si určitě umí vybrat tu část, kde je více jedniček než nul. Pokud by se měl rozhodovat v tomto kroku Marek, podívejme se na předchozí tah. Mohl to Eduard změnit? Co znamená, že to změnit nemohl? To znamená, že mohl táhnout jen do částí, kde je více nul než jedniček. To by ale znamenalo, že před jeho tahem muselo být v části plánu, kam ještě můžou táhnout, alespoň tolik nul co jedniček. Volných nul ale vždycky musí být méně než volných jedniček. Takže plán se už jednou musel rozdělit. To je ale divné, vždyť jsme řekli, že jsme vzali první rozdělení! Zjistili jsme, že ať se podíváme na jakékoli rozdělení, které způsobí Eduardovu prohru, tak muselo být nějaké takové rozdělení už předtím. Nemůže to tedy nastat poprvé, takže to nemůže nastat nikdy.

Došli jsme k tomu, čemu se říká v matematice spor. To se používá tak, že když chceme něco dokázat, předpokládáme opak a ukážeme, že to nejde. Tady jsme předpokládali, že existuje situace, v níž Eduard může prohrát, a navíc jsme si řekli, že se díváme na první moment, kdy se do této situace hra dostane. Potom jsme došli k tomu, že ten moment nemůže být první a to je požadovaný spor.

V podstatě stejně dokážeme, že Eduard vyhraje, pokud začne na zvýrazněných stěnách a zvýrazní stranu do jedničky. Jen je potřeba si rozmyslet, že po Markově tahu je více volných jedniček než nul a po Eduardově je stejně, a díky tomu pořád fungují ty věci, kde používáme, že volných jedniček je více než volných nul.

Pokud by Eduardův první tah nevedl do jedničky, tak prohozením jmen dokážeme, že Eduard nemůže vyhrát.

Odpovědí tedy je, že Eduard musí začít zvýrazněním strany do některého vrcholu, který je označený jedničkou.

• V druhém řešení si vrcholy rozdělíme do dvojic. V jedné dvojici budou vždy sousední vrcholy, tedy nula a jednička. Jedniček je o jedna více než nul, takže nám jedna jednička zbude. Opět využijeme toho, že když Eduard začne zvýrazněním do jedničky, bude už vždy zvýrazňovat do jedničky a Marek do nuly.

Eduardova taktika bude následující. Začne buďto zvýrazněním jedné dvojice z nuly do jedničky nebo zvýrazněním strany od okraje do přebývající jedničky. Potom Marek zvýrazní vždy stranu do nové dvojice, takže Eduard určitě dokáže zvýraznit další stranu. Hrací plán je konečný, takže hra musí někdy skončit. Eduard vždy dokáže na Markův tah odpovědět, takže nemůže prohrát. Tudíž musí vyhrát.

Ještě si ukážeme, že Eduard může začít zvýrazněním kterékoli strany z nuly do jedničky. Rozdělení dvojic může vypadat jako na obrázku (Obr. vz424).

Otáčením nebo překlápěním tohoto uspořádání dokážeme dostat každou stranu jako úsečku mezi vrcholy, které jsou ve stejné dvojici.

Toto řešení dokončíme stejně jako to předchozí. Pokud by Eduard začal jinak, tak prohozením jmen získáme, že Marek umí vždy vyhrát. Odpověď je také tedy stejná.

Komentář: Většinu komentáře jsem už napsala do řešení. Úloha byla těžká, proto jsem body udělovala i za částečné náznaky řešení. Pokud máte tři a více bodů, znamená to, že vaše řešení patřilo k jedněm z nejlepších. Obtížné se ukázalo hlavně to, abyste se jasně a srozumitelně vyjádřili.

Úloha č. 3

Při řešení geometrické úlohy je vždy vhodné začít náčrtkem (Obr. vz431) a rozborem, při kterém si stručně sepíšeme, co o objektu víme. Z něho je lépe vidět, jak objekt sestrojit (a v některých soutěžích se za to dává podstatná část bodů).

V tomto příkladě je třeba vědět, co jsou to těžnice. Tedy, že vedou z vrcholu trojúhelníku do středu protější strany a že je těžiště dělí na jednu a dvě třetiny. Do náčrtku si tedy doplním i zbylé části těžnice. Potom v náčrtku vidím, že u trojúhelníku ATC_{1} znám dvě strany a úhel, takže jsou nejvýše dvě možnosti, jak ho zkonstruovat, a pokud bych měl tento trojúhelník, tak snadno dodělám zbytek.

Zápis konstrukce:

• AA_{1}; |AA_{1}| = 3\cdot|TA_{1}| = 3\cdot2{,}5 \def\cm{\,{\rm cm}} \cm= 7{,}5 \cm
• T; T \in AA_{1} a |TA_{1}| = 2{,}5 \cm
• p; A \in p a |\angle pAA_{1}|=30°
• k; k = (T; r = 6/2 \cm = 3 \cm)
• C_{1}, C_{1}^{\prime }; C_{1}, C_{1}^{\prime } \in p \cap k (mám tedy ten trojúhelník, který má právě dvě možnosti)
• B; B \in p a |AC_{1}| = |C_{1}B| a B \neq A
• B^{\prime }; B^{\prime } \in p a |AC_{1}^{\prime }| = |C_{1}^{\prime }B^{\prime }| a B^{\prime } \neq A
• C; C \in {\mapsto} BA_{1} a |BA_{1}| = |A_{1}C| a B \neq C
• C^{\prime }; C^{\prime } \in {\mapsto} B^{\prime }A_{1} a |B^{\prime }A_{1}| = |A_{1}C^{\prime }| a B^{\prime } \neq C^{\prime }
• \triangle ABC; \triangle AB^{\prime }C^{\prime }

Pokud někdo nezná matematické značky a postup píše slovně, může vypadat nějak takto:

• Narýsujeme úsečku AA_{1}, která má délku 7{,}5 \cm, neboť je to trojnásobek vzdálenosti těžiště od středu strany a.
• Vyznačíme bod T (těžiště), který náleží úsečce AA_{1} a pro který platí |TA_{1}|= 2{,}5 \cm.
• Narýsujeme přímku p, které náleží bod A a pro kterou platí |\angle pAA_{1}|=30°.
• Narýsujeme kružnici k se středem v bodě T a poloměrem 3 \cm.
• Body C_{1} a C_{1}^{\prime } náleží průniku přímky p a kružnice k (mám tedy ten trojúhelník, který má právě dvě možnosti).
• Bod B náleží přímce p, jeho vzdálenost od bodu C_{1} je stejná jako |AC_{1}| a nerovná se bodu A. Bod B^{\prime } náleží přímce p, jeho vzdálenost od bodu C_{1}^{\prime } je stejná jako |AC_{1}^{\prime }| a nerovná se bodu A^{\prime }.
• Bod C náleží polopřímce BA_{1}, jeho vzdálenost od bodu A_{1} je stejná jako |BA_{1}| a nerovná se bodu B. Bod C^{\prime } náleží polopřímce B^{\prime }A_{1}, jeho vzdálenost od bodu A_{1} je stejná jako |B^{\prime }A_{1}| a nerovná se bodu B^{\prime }.
• Nakonec pouze spojíme všechny potřebné body, čímž vzniknou trojúhelníky ABC a AB^{\prime }C^{\prime }.

Zadání splňují dva neshodné trojúhelníky (Obr. vz432).

Komentář: Nejčastějším kamenem úrazu byl rozbor. Drtivá většina řešitelů úlohu vyřešila správně i sepsala konstrukci, ale v řešeních často chyběl náčrtek s vyznačenými částmi, které víme, aby bylo vidět, jak jsme na dané řešení přišli.

Úloha č. 4

Budeme si schématicky znázorňovat, jak se jednotlivé partie mohly postupně vyvíjet (Obr. vz441).

První partii mohl Robert hrát s černými, nebo s bílými. Pokud hrál s černými, musel ve druhém kole hrát s bílými. Pokud hrál s bílými, v následujícím kole měl dvě možnosti (černé, nebo bílé). Tento možný vývoj znázorňují jednotlivé šipky ve schématu. Jednotlivá čísla udávají, kolika způsoby se do té situace mohl dostat.

Například pokud hrál v pátém kole s bílými, pak se turnaj mohl vyvíjet 8 způsoby. Tj. ve čtvrtém hrál s černými (3 možnosti), nebo s bílými (5 možností). Počet možností u obou barev sečteme. Hrál-li v pátém kole s černými, pak ve čtvrtém musel hrát za bílé (5 možností), tady číslo pouze přepíšeme.

Nyní stačí sečíst možnosti pro devátou partii: 55 + 34 = 89. Zkušenější řešitelé si mohou všimnout, že se zde nachází Fibonacciho posloupnost.

Jiná možná řešení

Úloha šla řešit i mnoha jinými způsoby pomocí kombinatoriky. Zde nastíním jeden z těchto postupů a na co si v nich dát pozor.

Nejvhodnější bylo použití kombinací a triku, že umisťuji do harmonogramu dvoupartii (bílá–černá) místo jednotlivých „černých“ partií. Takto zabráním opakování „černých“ partií po sobě. Zde však musím rozlišit případ, kdy Robert začíná hrát s černými, protože zde dvoupartii neumístím.

Někteří řešitelé úlohu řešili pomocí principu inkluze a exkluze. Tj. spočítáme všechny možnosti, poté odečteme špatné (z nichž některé odečteme vícekrát), ty které odečteme vícekrát, zase znovu přičteme (mezi nimi zas některé přičteme vícekrát)…

Toto není zrovna vhodný postup, protože se musí ošetřit opravdu velké množství možností.

Komentář: Každý z řešitelů na to šel vlastní cestou. Nejúspěšnější metodou byla ta výše popsaná s Fibonacciho posloupností. Vzhledem k různým postupům a spoustě možných míst (zvláště u principu inkluze a exkluze), kde šlo udělat chybu, bylo velmi obtížné určit jasné meze pro jednotlivá bodová ohodnocení.

Úloha č. 5

Prvního hráče můžeme usadit na kterékoli ze sedmi míst kolem stolu, druhého pro každé usazení prvního hráče na libovolné ze zbývajících šesti a tak dále, takže počet možností umístění kolem stolu je 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 7! (čteno 7 faktoriál).

Pro každého hráče máme dvě další možnosti – usazení čelem, nebo zády ke stolu. Počet možností tohoto otáčení nezávisí na tom, jak jsou hráči rozmístění, takže pro každé umístění je stejný počet možností. Zároveň to, jestli hráč sedí ke stolu čelem, nebo zády, neovlivní ostatní hráče, takže každý má dvě možnosti nezávisle na ostatních a počet možností otočení je 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^{7}. Z toho vyplývá, že celkový počet možností je 7! \cdot 2^{7} = 5\,040 \cdot 128 = 645\,120.

Komentář: Výsledky se sice pohybovaly mezi desítkami až desítkami milionů, ale většina došlých řešení byla správná.

Úloha č. 6

Situáciu máme nakreslenú na obrázku (Obr. vz461). Aby sa nám lepšie popisovali kocky, označíme si 3 osi.

Veľmi dôležité sú prázdne miesta. Ak z hora nevidíme žiadnu kocku, tak vieme, že v tom stĺpci nie je žiadna. Podobne aj zleva. Preto si vyznačíme všetky miesta, kde nemôže byť kocka ve vrstvách i, ii, iii (Obr. vz462, vz463, vz464).

Máme teraz niekoľko miest kde môže byť kocka. Vyznačíme si tie, kde kocka byť musí. Napríklad jediné miesto, kde môže byť kocka v zadnom riadku na poschodí ii, je miesto 1, c, ii. Podobne nad ním je tiež jediné miesto, kde môže byť kocka v riadku c v poschodí iii. Keďže teleso musí byť spojité, a jediné miesto kde sa tieto 2 kocky môžu napojiť na zvyšok je 1, b, iii. Ďalej sa dá napojiť iba cez 2, b, iii a 3, b, iii. Týchto 5 ďalej napojíme na 3, a, iii a tým máme horný pohľad „hotový.“ Pokračujeme pohľadom zľava. Napojíme 3, a, ii spolu s 3, a, i, lebo v prednom riadku musia byť 3 kocky, a v stľpcoch a, 1 a a, 2 byť nemôžu. Keďže zľava vidíme ešte jednu ďalšiu kocku, musíme ju pridať do 3, b, i. Tým je „hotový“ aj pohľad zľava. Ostali nám 2 miesta (Obr. vz465), kde kocky byť môžu, ale nemusia (a to 2, b, i a 1, b, i). Kocky môžu byť buď na žiadnom, jednom z nich (2, b, i) alebo na oboch. Preto máme 3 riešenia.

Komentář: Väčšina z vás ktorá úlohu pochopila mala správne riešenie. Body sa strhávali hlavne za nedostatočné zdôvodnenie, prečo tam niektoré kocky musia byť.

Úloha č. 7

Stranu Čtverce budeme značit a. Stranu Čtverečku budeme značit b.

Nejdříve zanalyzujme podmínku ze zadání, která mluví o ploše. Ta se dá ekvivalentně zapsat následovně: Součet plochy Čtverce, Čtverečku a dvou Obdélníků je 100 \def\m{\,{\rm m}}\m^{2}. Pokud útvary šikovně poskládáme, snadno vidíme, že a + b = 10 \m (Obr. vz471).

Stejného výsledku můžeme dosáhnout i algebraicky pomocí vzorce pro druhou mocninu součtu.

Nyní se podíváme na podmínku ze zadání, která mluví o obvodu. Platí, že součet obvodů Čtverce, Obdélníku, Čtverečku a Kolečka je roven 100\m. Pokud si vyjádříme jednotlivé obvody pomocí a, b a průměru Kolečka d, získáváme, že

Pokud vše sečteme a částečně vytkneme 6, získáváme následující rovnici:

Součet a+b ale známe, můžeme ho proto do rovnice dosadit:

Po jednoduchých úpravách tedy získáváme, že

Nejdelší rozměr Šachovničky je její úhlopříčka. Tu spočítám následovně:

Pokud tedy umístím Šachovničku do Kolečka soustředně, musí se tam vejít.

Komentář: Až na malé chyby a špatně přečtená zadání byla všechna došlá řešení správně.

Opravovali: 1. David Hájek, 2. Magdaléna Mišinová, 3. Klára Hubínková a František Steinhauser, 4. Jiří Štrincl, 5. Tomáš Flídr a Martin Černý, 6. Martin Smolík, 7. Martin Zimen a Jan Hrůza.