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

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

Zadání naleznete zde.


Úloha č. 1

Přepsat zadání do počtu hráčů zvládli všichni řešitelé a měli to správně, proto to nebudu rozebírat a jen vypíši:

Ze 30 účastníků orangutana hrálo 6 hráčů, jezevce 11 hráčů, křováckou obranu 8 hráčů, bez zahájení hrálo 10 hráčů – (tedy nějaké zahájení hrálo 20 hráčů) a žádný hráč nehraje více než dvě zahájení (tato poznámka občas chyběla a je dost důležitá).

Dále bylo několik postupů, jak se dopočítat výsledku, vypíšu základní tři (které jste použili). Abych ušetřil místo, orangutana zkrátím na O, jezevce na J a křováckou obranu na K. Počty hráčů, kteří hrají pouze tato zahájení budou mít hvězdičku, (abych tím odlišil hráče, kteří hrají orangutana a jen orangutana), takže například OJ^{\ast}=2, protože dva hráči hrají orangutana i jezevce.

  • Jedna varianta byla zkusit dopočítat všechny dvojice zahájení (s Vennovým diagramem a rovnicemi (Obr. vz111)). Protože víme, že nikdo nehraje tři zahájení a O s J hrají dva hráči (OJ^{\ast}=2), x označíme počet hráčů, kteří hrají O i K (OK^{\ast}=x) a počet KJ^{\ast} označím y, tedy (KJ^{\ast}=y). Potom si vypíši všechny možnosti, jaká zahájení mohou hráči hrát, a vím, že dohromady to musí vyjít 20, tedy: 20=O^{\ast}+J^{\ast}+K^{\ast}+OJ^{\ast}+OK^{\ast}+JK^{\ast}=((4-x)+(9-y)+(8-x-y)+(2)+(x)+(y)), z této rovnice mi vychází, že 20=23-x-y. To sice není úplně hezký výsledek, protože mi zbyly dvě neznámé (x+y=3, popř. OK^{\ast}+JK^{\ast}=3, ale mě zajímá jen součet všech dvojic, tedy že OJ^{\ast}+OK^{\ast}+JK^{\ast}= 2+3=5.

  • Další variantou bylo rovnou z počtu hráčů a počtu hraných zahájení určit, kolik hráčů hraje dvě zahájení. Tady se hodilo zopakovat, že nikdo nehraje více než dvě zahájení. Potom úvahou vidím, že hráčů se dvěma zahájeními je tolik, o kolik je více hraných zahájení, než je hrajících hráčů, tedy 6+11+8-20=5.
  • A třetí variantou, kterou jste používali nejčastěji, i když je celkem komplikovaná, byla kombinace mezi těmi dvěma postupy. Tedy napřed odečíst dvojici, která hrála jezevce a orangutana a potom přejít na druhou variantu a rovnou určit, kolik dalších hráčů hraje dvě zahájení. Konkrétně mezi zbylými 18 hráči se hrálo O^{\ast}=4, J^{\ast}=9K^{\ast}=8, dohromady 21 hraných zahájení (člověkozahájení), takže dvě zahájení museli kromě dvou odečtených hrát další tři hráči. Takže to opět vychází pět (2+3).

Hráčů, kteří hrají dvě zahájení je tedy 5.

Komentář: Úlohu většina řešitelů měla správně a žádné chyby se příliš neopakovaly. Problémy dělala jen informace, že dva hráči hrají zároveň O i J, ale nebyly tam informace o dalších dvojicích zahájeních, takže někteří tuto dvojici započítali dvakrát, někteří dokonce třikrát a někteří ani jednou, takže řešení úlohy vycházelo 3, 5, 7 i 9.

Úloha č. 2

Nejprve spočítáme rovnostranné trojúhelníky, jež jsou na jedné stěně čtyřstěnu, potom ty, jejichž vrcholy jsou na více stranách.

Protože stěny pravidelného čtyřstěnu jsou shodné, tak nám stačí spočítat trojúhelníky, které jsou na jedné z nich, a výsledek vynásobit čtyřmi. Zároveň stěna samotná je rovnostranný trojúhelník.

Vyberme jednu stěnu čtyřstěnu. Její vrcholy označíme A, B a C. Body, které dělí její strany na třetiny, označíme X_{Y}, pokud leží na straně XY a jsou blíže X.

Na jedné stěně najdeme 9 rovnostranných trojúhelníků, samotnou stěnou daný a ještě těchto 8:

Nyní dokážeme, že tyto trojúhelníky jsou skutečně rovnostranné.

Ty na prvních dvou obrázcích (Obr. vz122 a Obr. vz122) mají určitě jeden úhel 60 stupňů. Zároveň poměr stran, které tento úhel svírají, a hran čtyřstěnu, na nichž leží, je pro obě stejný. Tím pádem jsou ty trojúhelníky podle věty sus podobné stěně čtyřstěnu, která je rovnostranný trojúhelník.

Víme, že platí |AA_{B}|=|BB_{C}|=|CC_{A}|=1/3|AB| (Obr. vz122). Také platí |AC_{A}|=|BA_{B}|=|CB_{C}|=2/3|AB| a |\angle C_{A}AA_{B}|=|\angle A_{B}BB_{C}|=|\angle B_{C}CC_{A}|=60^{\circ}, takže trojúhelníky C_{A}AA_{B}, A_{B}BB_{C} a B_{C}CC_{A} jsou shodné podle věty sus. Tím pádem |A_{B}B_{C}|=|B_{C}C_{A}|=|C_{A}A_{B}|, takže trojúhelník A_{B}B_{C}C_{A} je rovnostranný. Obdobně dokážeme, že trojúhelník A_{C}B_{A}C_{B} je rovnostranný.

Nyní dokážeme, že na jedné stěně už žádné další rovnostranné trojúhelníky nejsou. Ke každé dvojici bodů existují jen dva body, které s nimi mohou tvořit rovnostranný trojúhelník. Na naší stěně se ale může nacházet jen jeden z nich.

Na jedné stěně existuje 9 vyznačených bodů. Mezi nimi najdeme 36 dvojic. Vrcholy trojúhelníku jsou dohromady tři dvojice bodů. Našli jsme 9 trojúhelníků. Dohromady jsme tedy již našli rovnostranný trojúhelník pro 27 dvojic. Zbylých devět dvojic je vrchol a jeden z bodů na protější straně a dva body na jedné straně. Pro ty rovnostranný trojúhelník s vrcholy v našich bodech nenajdeme, takže jsme hotovi.

Trojúhelníky, které jsou rovnostranné, jsou ty, které leží v rovině, která je rovnoběžná s rovinou některé ze stěn čtyřstěnu. Pro každou stěnu existují dva takové trojúhelníky: jeden, který má své vrcholy ve dvou třetinách hrany od vrcholu čtyřstěnu, a druhý, který je má v jedné třetině. Jsou rovnostranné, protože jsou obrazem stěny čtyřstěnu ve stejnolehlosti se středem v protějším vrcholu čtyřstěnu.

Zbývá dokázat, že nenajdeme žádné další rovnostranné trojúhelníky, které nejsou celé na jedné stěně. Nejprve uvážíme ty, jejichž strany leží na stěnách. Pokud by takový trojúhelník existoval, nemohl by být v rovině, která je rovnoběžná se stěnou, protože všechny takové už jsme započítali. Potom ale jeho úhly nemohou být rovny 60 stupňů, což je nutná podmínka pro to, aby byl trojúhelník rovnostranný.

Když jedna strana trojúhelníku leží na stěně, tak na stěně leží i jeho zbylé strany, neboť potom neexistuje hrana čtyřstěnu, která by neměla nějaký bod společný s hranou, na které leží nějaký bod tohoto trojúhelníku.

Pokud trojúhelník nemá strany na stěnách, musí jeho vrcholy ležet na hranách čtyřstěnu, které nemají společný vrchol. Ke každé hraně existuje jen jedna taková. Potom musí dva vrcholy ležet uvnitř jedné z nich, což znamená, že délka jeho strany je 1/3 hrany čtyřstěnu. Druhá hrana, na které vrchol trojúhelníku má ležet, je ale určitě dál. Tím je důkaz hotov.

Úloha č. 3

Jako na každou kombinatorickou úlohu i na tuto se dalo podívat z několika různých pohledů. Rád bych zmínil dva nejčastější a zároveň nejelegantnější. Spravný je libovolný z obou popsaných a samozřejmě i mnoho dalších.

Rád bych nejdříve vysvětlil poznámku v zadání. Skok jezdce se skládá z jeho vodorovné složky a z jeho svislé složky. Celkovou délku skoku spočítáme pomocí Pythagorovy věty:

x^{2} + y^{2} = (\sqrt{5})^{2}=5.

Jelikož musí jezdec skákat o celočíselné vzdálenosti v obou složkách směru, musí být x i y celočíselné. Jedinou vyhovující možností je dvojice 1 a 2. Proto se jezdec musí hnout o jedna v jedné složce směru a o dva v druhé složce směru.

Začneme pozorováním, které se nám bude hodit v obou řešeních. Všimneme si, že kůň se musí v každém skoku přiblížit cíli o dvě políčka. Celkově tedy provede 6 skoků. Jinak by to nestihl.

Schéma podobné Pascalově trojúhelníku

Do šachovnice zakreslíme všechna políčka, na kterých se kůň může během cesty vyskytnout (Obr. vz131). Poté si šipkou zakreslíme možné postupy mezi políčky. Získáme tak jakousi síť, která se odborně nazývá orientovaný graf. Nepleťme si to však s grafy funkcí. Toto jsou grafy kombinatorické a jistě se s nimi během studia matematiky nebo informatiky setkáte. Nyní začneme do políček vpisovat hodnoty. Začínajícímu políčku přiřadíme jedničku. Představme si to tak, že se na start můžeme dostat pouze jedním způsobem. Nyní pro každé jiné políčko spočítám, kolika způsoby se do něj dá dostat. To bude součet počtů možností, jak se mohl dostat na políčka předcházející. Podívám se tedy na políčka, z kterých vede na aktuální políčko šipka a sečtu jejich hodnoty. Postupem času se tak dostanu na cílové políčko, kterému přiřadím číslo 20.

V našem případě je struktura velmi podobná Pascalově trojúhelníku (Obr. vz132). Pascalův trojúhelník vytvořím tak, že na první řádek napíšu jedničku a o řádky níže budu vždy psát součet čísel těsně nad ním.

Počítání počtu permutací směrů

Všimneme si, že k tomu, abychom přešli šachovnici, musíme udělat stejný počet skoků nahoru a skoků dolů. Kůň musí skočit právě šestkrát. Musí tedy skočit třikrát nahoru a třikrát dolů. V jakém pořadí to udělá, je však zcela na něm. Mohu tedy tyto směry libovolně přeházet. Mám tedy za úkol spočítat, kolika způsoby za sebe můžu naskládat tři šipky nahoru a tři šipky dolů. Jednou z možností je například:

\uparrow\downarrow \uparrow \uparrow\downarrow \downarrow

Počet permutací dvou trojic symbolů můžu spočítat jako permutaci s opakováním. Představím si nejdřív, že jsou všechny symboly různé. Mám celkem 6! způsobů, jak je za sebe uspořádat. Jelikož jsou ale tři symboly stejné, mohu je mezi sebou permutovat a počet způsobů se nezmění. Jelikož jsem je ale do původního počtu započítal, musím ho nyní vydělit 3!. To stejné platí i pro druhou dvojici. Celkově je tedy počet způsobů, jak za sebe poskládat šipky, roven \frac{6!}{3!\cdot3!}=20.

Můžeme si všimnout, že to je stejné jako kombinační číslo {6 \choose 3}. To je logické, protože ze šesti míst vybírám tři místa pro jeden druh šipek a zbylá místa vyplním druhým druhem šipek.

Obě dvě řešení nás tedy dovedla k počtu možností 20, což je správná odpověď.

Komentář: Většina řešitelů postupovala jedním ze vzorových řešení. Jak už to u kombinatorických úloh bývá, mnoho řešitelů se vydalo směrem zkoušení možností. Tato řešení zpravidla nevedla k cíli. Jen málokdy člověk nezapomene na nějakou možnost. Kombinatorické úlohy vyžadují systematický přístup. Navíc i kdyby byl výsledek správně, není možné za takové řešení udělit plný počet bodů, protože je to vlastně nezdůvodněný tip.

V úloze bylo důležité zmínit, že v každém skoku se musí posunout o dvě políčka k cíli. To nám vylučuje možnou návštěvu většiny políček. Při řešení pomocí schématu je také důležité zmínit, že hodnota v políčku je součtem hodnot v předcházejících políčkách. Pokud tato zdůvodnění (nebo jiná) chyběla, strhával jsem body.

Za pokus o systematické počítání počtu možností jsem pár bodů udělil, i když nevedla ke správnému výsledku.

Úloha č. 4

Chceme-li přesunout celou pyramidu z pneumatik z jednoho sloupku na druhý, určitě během našeho postupu budeme chtít přesunout i největší pneumatiku. Abychom přesunuli největší pneumatiku, musíme nejprve přesunout všechny nad ní na třetí sloupek, protože nemůžeme hýbat s pneumatikou, která má jiné pneumatiky nad sebou, a zároveň ji nemůžeme přesunout na žádnou jinou. K dokončení pak stačí přesunout největší pneumatiku na druhý (volný) sloupek a opět přesunout všechny všechny ostatní pneumatiky na největší. Z tohoto vidíme, že nejmenší počet přesunů pěti pneumatik je o jeden tah více než dvojnásobek nejmenšího počtu tahů na přesun čtyř pneumatik.

Pokud si označíme pneumatiky od nejmenší po největší čísly 15, pak pro přesun čtvrté pneumatiky ze sloupu a na sloup b, potřebujeme nejprve přesunout všechny menší pneumatiky na třetí sloup, pak přesunout čtvrtou na sloup b a následně na ni tři menší pneumatiky přesunout. Tento postup platí obecně, můžeme tedy spočítat nejefektivnější způsob přesunu n pneumatik z nejefektivnějšího způsobu přesunu n-1 pneumatik. Ale pokud přesouváme dvě pneumatiky, stačí nejefektivněji přesunout první na odkladný sloupec, pak přesunout druhou, a nakonec na ni vrátit první. Přesun dvojice pneumatik jde tedy nejlépe udělat na 3 tahy.

Pokud si označíme t(n) nejmenší počet tahů pro přesun n pneumatik, můžeme spočítat:

\eqalign{t(2)&=3,\cr t(3)&=2\cdot t(2) + 1=7,\cr t(4)&=2\cdot t(3) + 1=15,\cr t(5)&=2\cdot t(4) + 1=31.\cr}

Nejmenší počet tahů na přesun pěti pneumatik je tedy 31. Z tohoto výpočtu také můžeme vypozorovat, že t(n)=2^{n} - 1.

Komentář: Většina účastníků se dostala ke správnému výsledku, pokud ne, často šlo jen o chybu z nepozornosti. Hodně řešitelů našlo algoritmus jak přesunout pneumatiky na 31 tahů, ale často chyběl komentář, proč to nemůže být méně, proto taková řešení většinou dostala 4 body. Řešení, ve kterých byl pouze výsledek bez postupu méně bodů.

Úloha č. 5

O hledaném čísle víme, že je dělitelné pěti a sudé, tedy dělitelné dvěma, takže je dělitelné i deseti 2 \cdot 5 = 10. To znamená, že jeho poslední číslice je 0. Číslo, které je o jedna menší, proto končí na 10 - 1 = 9. Podle zadání má být dělitelné třemi a sedmi, takže můžeme říci, že je dělitelné 3 \cdot 7 = 21. Aby poslední cifra násobku 21 byla 9, druhý činitel musí končit na 9 \div 1 = 9. Nejmenší přirozené číslo splňující tuto podmínku je 9. Číslo o jedno menší než hledané je tedy 21 \cdot 9 = 189 a hledané číslo je 189 + 1 = 190.

Komentář: Většina řešitelů úlohu vyřešila správně, ať už postupem podobným vzorovému řešení nebo zkoušením možností hledaného čísla, popřípadě čísla o jedno menší. Body jsem strhával hlavně za chybějící postup, nenalezení hledaného čísla a nevyzkoušení některých možností.

Úloha č. 6

Nejprve si musíme říct, co se stane, pokud se dvě osoby setkají. V naší úloze si je můžeme představovat jako totožné objekty, které mají jen nějaké označení, aby se nám nepletly. Pokud se srazí, tak se oba otočí a vyrazí opačným směrem. Protože oba jdou stejnou rychlostí a opačným směrem, než jakým přišli, a tento směr je stejný jako původní směr toho druhého, tak nás vlastně počet srážek nezajímá. Protože z našeho pohledu jde stále jeden z účastníků vlevo a druhý vpravo a pokud si u výměny prohodí svoje označení, tak bychom ani nepoznali, že k něčemu došlo. Proto nezáleží na počtu účastníků ale na délce trati, protože pokud se jeden z krajních rozhodně jít přes střed, tak ji musí přejít celou (lépe: jeho informace musí přejít celou silnici). V našem případě, kdy je silnice dlouhá \def\m{{\rm m}}300\m a účastníci chodí rychlostí 1\m/s, tak nejdéle může hra trvat 300 minut.

Komentář: Tato úloha byla poměrně jednoduchá. Nejčastější chybou bylo sčítání časů účastníků. Vzhledem k jednoduchosti úlohy jsem 5 bodů dávala jen v případě, že jste správně odůvodnili, proč hra potrvá opravdu nejdéle 300 minut, a jak jste k tomu došli.

Úloha č. 7

Mějme trojúhelník ABC. Vezmeme si dvě těžnice, například z A a B, a označíme jejich průsečík T. Body S_{AC} a S_{BC} jsou středy stran AC a BC, tedy úsečka S_{AC}S_{BC} je střední příčka trojúhelníku ABC. Musí tedy platit, že je rovnoběžná se stranou AB a její délka je polovina délky strany AB.

Dále si středy úseček AT a BT označíme jako S_{AT} a S_{BT}. Úsečka S_{AT}S_{BT} je pak střední příčka trojúhelníku ABT a platí pro ni, že je rovnoběžná s AB a její délka je polovina délky AB. Z toho plyne, že S_{AC}S_{BC} a S_{AT}S_{BT} mají stejnou délku a jsou navzájem rovnoběžné (Obr. vz171).

Protože jsou rovnoběžné, úhly TS_{AT}S_{BT} a TS_{BC}S_{AC} jsou shodné. Stejně tak úhly TS_{BT}S_{AT} a TS_{AC}S_{BC}. Podle věty usu jsou tedy trojúhelníky S_{AT}S_{BT}T a S_{BC}S_{AC}T shodné. Tedy |S_{AT}T| = |S_{BC}T|. Zároveň ale víme, že |AS_{AT}| = |S_{AT}T|, protože S_{AT} je střed AT.

Z toho plyne, že těžnice z vrcholu B dělí těžnici z A na 1/3 a 2/3. To samé můžeme dokázat i pro těžnici z C. Jestliže ale těžnice z B i těžnice z C protínají těžnici z A ve stejném místě, znamená to, že se všechny tři protínají v jednom bodě, což jsme chtěli dokázat.

Komentář: Většinu řešitelů zmátla „očividnost“ tvrzení a neuvědomili si, že tvrzení, že se těžnice protínají v jednom bodě, vůbec není samozřejmé a je třeba ho dokázat. Část řešitelů se sice o nějaký důkaz pokusila, ale využívali při něm vlastnosti těžiště. Pokud ale chceme dokázat, že těžiště existuje, nemůžeme používat jeho vlastnosti, protože je v tu chvíli ještě „neznáme“.

Správná řešení nejčastěji využívala nějaké pokročilejší poznatky jako je Cevova věta nebo stejnolehlost. Jak je ale vidět ze vzorového řešení, na dokázání stačí i velmi elementární znalosti.

Opravovali: 1. František Steinhauser, 2. Magdaléna Mišinová, 3. Martin Černý a Martin Zimen, 4. Jan Hrůza, 5. Tomáš Flídr, 6. Eliška Vítková, 7. Kateřina Nová.