Vzorové řešení bonusové série 31. ročníku

Úloha č. 1

„Ve městě se nám tu začali roztahovat Galbaniovci. Nevím, jaký mají přesvědčovací metody, ale každej den každej člen jejich klanu k nim přetáhne jednoho novýho člověka. Jestli to takhle půjde dál, tak 31. května budou všichni lidi ve městě patřit ke Galbaniovcům. Šéf si proto myslí, že by ses do toho měl s dalšíma chlapama vložit a během zítřejšího rána naráz půlku z nich odstranit. Tvrdil, že je to zpomalí. Ale víš, kdy by pak Galbaniovci zaplnili město, i kdyby se vám to povedlo?“

Řešení: Každý den každý Galbaniovec nabere jednoho nového člena. To znamená, že se každý den počet členů gangu zdvojnásobí. Pokud jeden den Tonyho parta pobije polovinu Galbaniovců, bude jich právě tolik jako předchozí den. Dá se tedy říct že akce zpomalí nábor o jeden den, tedy místo aby Galbaniovci ovládli město 31. května, ovládnou ho 1. června.

Někteří z vás kromě této základní úvahy zahrnuli do řešení i fakt, že počet obyvatel v Chicagu se Tonyho akcí sníží a v jistých případech se díky tomu nábor nezpomalí vůbec.

Nechť C je celkový počet lidí v Chicagu a g původní počet lidí Galbaniho gangu ve chvíli, kdy začal nábor. G_{k} označím počet Galbaniovců k-tý den náboru, tedy G_{0} = g, G_{1} = 2g, G_{2} = 2^{2} \cdot g = 4g, \ldots , G_{k} = 2^{k} \cdot g, \ldots

Teď si rozebereme, jak by probíhal nábor poslední den s pořadovým číslem n. Galbaniovci tento den mohou nabrat až G_{n-1} nových členů. Občanů Chicaga však už nemusí zbývat tolik, s velkou pravěpodobností jich bude méně. Jejich počet označím neznámou Z. Vím o ní jen to, že Z \leq G_{n-1} a že platí rovnost:

g+2^{1}g+2^{2}g+\ldots+2^{(n-1)}g+Z=C.

Podle této rovnice by probíhal nábor bez Tonyho zásahu. Jenže naplánovaná akce naráz sníží počet obyvatel Chicaga o zabité Galbaniovce. Mohou pak nastat dvě situace. Pokud zemře míň lidí, než je Z, nábor se opravdu zpozdí o jeden den přesně podle předchozí úvahy. Pokud ale zemře víc lidí než Z, pak by dle původní rovnice měl nábor skončit v den n-1, tedy 30. května, a toto datum se díky masakru posune na 31. května. Správná odpověď tedy je, že se nábor buď vůbec nezpozdí, nebo skončí o jeden den později, tedy 1. června.

Komentář: Úvahu o změně počtu obyvatel správně formulovalo jen několik řešitelů, pochvalu si zaslouží i ti, kteří se o to alespoň pokusili. Body jsem nestrhával, ani pokud tato úvaha úplně chyběla. Naprostá většina z vás správně vydedukovala, že nábor se zpozdí o jeden den. Body jsem strhával v případech, kdy to nebylo dostatečně zdůvodněno. Dejte si pozor na to, že pokud něco ukážete na konkrétních číslech, neříká to nic o tom, jak by se situace vyvíjela například při jiném počtu obyvatel Chicaga. Není to proto dostatečné řešení úlohy.

Úloha č. 2

Tony ví, že don Galbani by určitě neplýtval svým časem, takže z vily do administrativní budovy jezdí zásadně jen tou nejkratší možnou cestou. Určete, kolik je na přiloženém plánku různých nejkratších cest.

Řešení: Chceme-li se na plánku dostat z bodu A do bodu B, který je umístěn vpravo nahoře od bodu A, co nejrychlejší cestou, nesmíme si zacházet. Zacházka je pro nás jakákoli cesta doleva či dolů. Všechny takové cesty můžeme z plánku tedy vymazat, pouze by nás mátly.

Dále si spočteme vzdálenost bodu A od bodu B: Z bodu A musíme jít celkem třikrát nahoru a sedmkrát doprava, abychom se dostali do bodu B. V plánku máme ale i šikmé cesty – pokud použijeme jednu šikmou cestu doprava nahoru, je to kratší, než kdybychom ji obcházeli po pravoúhlých cestách. Dokázat to lze třeba jen trojúhelníkovou nerovností – představme si trojúhelník z jedné vodorovné, jedné svislé a jedné úhlopříčné cesty – aby šel sestrojit, musí platit, že součet délek dvou cest musí být delší než cesta třetí. Tedy součet délek cesty doprava a nahoru bude delší než délka cesty šikmé. Proto se pokusíme co možná nejvíc cest jít šikmo nahoru. Můžeme tak jít třikrát, protože bod B je od bodu A vzdálen tři cesty nahoru. Všechny je tedy nahradíme cestami šikmými, a cesty nahoru můžeme z plánku opět vymazat. Nejkratší cesta z bodu A do bodu B bude tedy dlouhá tři šikmé cesty a čtyři vodorovné (tři vodorovné z původních 7 jsme zahrnuli do šikmých cest). Náš plánek tedy nově vypadá jako na obrázku bonus11.

Nyní si probereme úvahu, kterou máme zobrazenou na obrázku bonus12: Potřebuji se dostat z bodu K do bodu M. Nelze to přímo, proto musím přes nějaké jiné body, říkejme jim uzlové. Do bodu M se z bodu K můžu dostat buď přes bod L, nebo přes bod N. Do bodu N se z bodu K dostanu pouze jednou cestou, do bodu L také pouze jednou. Pokud tyto možnosti sečtu, dostanu celkem dva způsoby, kterými se můžu dostat z bodu K do bodu M. Tuto úvahu nyní použijeme pro náš plánek. Budeme postupovat od bodu A a v každém uzlovém bodě si napíšeme, kolika různými způsoby se do něj mohu dostat. Tento počet bude dán součtem všech možností, kterými se můžu dostat do bodů, které přímo předchází mému uzlovému bodu. Plánek tedy bude vypadat následovně:

Z obrázku je tedy patrné, že z bodu A do bodu B se můžu dostat přesně osmi různými cestami. Že jsou nejkratší jsem zdůvodnila na začátku.

Komentář: Vzhledem k tomu, že se jednalo o bonusovu sérii, hodnotila jsem velmi mírně, skoro bych řekla, že jsem dávala body zadarmo. Přišla spousta řešení, která obsahovala pouze číslo, ne vždy správné. Ta jsem hodnotila bodem za snahu. Dva body získali ti, kteří k tomu připsali aspoň odpověď. Za tři body byl správný počet cest, další bod byl za jejich nakreslení. Plným počtem jsem hodnotila řešení, které obsahovalo více či méně rozsáhlé vysvětlení. Řešitelům se čtyřmi či pěti body gratuluji!