1. Perníková chalúpka

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Edovi “Baklažánovi” Batmendijnovi na

Janko a Marienka sú väzňami v perníkovej chalúpke a radi by ušli. Marienka už aj vymyslela plán. Ježibaba totiž každý deň chodí spolu s Marienkou do lesa zbierať čarovné bylinky. V tom čase by Janko mohol ujsť a kým by sa Ježibaba s Marienkou vrátili, stihol by už byť dostatočne ďaleko a zavolať nejakú pomoc pre Marienku.

Celý plán však má jeden háčik. Marienka sa totiž s Jankom môže dohadovať iba večer (keď upratuje okolo chlievika) a Ježibaba sa až ráno rozhodne, kedy pôjde na bylinky (vtedy sa to dozvie aj Marienka). Ak by sa Janko pokúsil o útek, keď je Ježibaba v chalúpke, zle-nedobre by sa mu povodilo a Ježibaba by sprísnila opatrenia. Preto musí Marienka čas Ježibabinho odchodu do lesa Jankovi zakódovať do toho, ako mu naservíruje raňajky.

Úloha

Janko máva každý deň na raňajky niekoľko koláčov, z ktorých každý je buď makovník, alebo orechovník. Marienka mu ich vždy v kuchyni poukladá do jedného radu na podlhovastý podnos, pričom sa sama rozhodne, na ktorých pozíciách v rade budú makovníky a na ktorých orechovníky (Ježibaba má vždy v zásobe napečenú hŕbu makovníkov aj orechovníkov, takže ak by Marienka chcela, mohla by Jankovi naservírovať samé makovníky, alebo samé orechovníky). Následne Ježibaba podnos odnesie Jankovi. Keďže z jedného konca Ježibabinho podnosu je kúsok odštiepený, vie Janko jednoznačne určiť na ktorej strane je začiatok radu koláčov a na ktorej strane je jeho koniec.

1. (2 body) Janko máva na raňajky vždy 5 koláčov. Ježibaba chodieva na bylinky niekedy medzi 11:00 a 14:50. Marienka by Jankovi chcela zakódovať čas Ježibabinho odchodu s presnosťou na desať minút, teda chce vedieť zakódovať ľubovoľný z časov 11:00, 11:10, 11:20, …, 14:50 (spolu 24 možností). Navrhnite spôsob, ako to urobiť. Presnejšie, navrhnite dve veci:

   • Postup, podľa ktorého sa Marienka na základe času Ježibabinho odchodu rozhodne, ktoré z koláčov majú byť makovníky a ktoré orechovníky.
   • Postup, podľa ktorého Janko na základe donesených koláčov zistí, v ktorom čase Ježibaba odíde.

   Nezabudnite, že Janko s Marienkou sa môžu večer na spôsobe kódovania dohodnúť, od rána sa však už rozprávať nemôžu.

2. (2 body) Janko máva na raňajky 8 koláčov. S akou veľkou presnosťou mu Marienka vie zakódovať čas Ježibabinho odchodu? Presnejšie povedané, koľko rôznych možností môže do ôsmich koláčov zakódovať? Svoju odpoveď zdôvodnite!

3. (1 bod) Ježibaba odchádza do lesa vždy medzi 10:00 a 16:59. Keďže každá minúta je drahá, Marienka by chcela čas jej odchodu zakódovať s presnosťou na minútu (chce teda vedieť rozlíšiť 420 rôznych možností). Koľko najmenej koláčov by Janko musel mať na raňajky, aby sa jej to mohlo podariť? Svoju odpoveď zdôvodnite!

4. (5 bodov) Ježibaba si vypestovala jeden veľmi nepríjemný zvyk: keď ide podnos s koláčmi odniesť Jankovi, najprv jeden z koláčov zje. Potom sa zapýri a na miesto zjedeného koláča doplní nejaký koláč zo zásoby – možno rovnakého druhu ako ten zjedený a možno opačného. Marienka chce Jankovi vedieť zakódovať 240 rôznych možností (časy medzi 11:00 a 14:59 s presnosťou na minútu) tak, aby:

   • V prípade, že Ježibaba zjedený koláč nahradila rovnakým, Janko normálne zistil, kedy Ježibaba odíde a ušiel v správnom momente.
   • V prípade, že Ježibaba zjedený koláč nahradila opačným, Janko zistil, že sa niečo pokazilo a útek radšej odložil na nasledujúci deň.

   Opäť teda treba navrhnúť dva postupy, prvý pre Marienku, podľa ktorého na základe času Ježibabinho odchodu poukladá na podnos koláče a druhý pre Janka, podľa ktorého na základe koláčov na podnose buď zistí čas Ježibabinho odchodu, alebo aspoň zistí, že Ježibaba niektorý koláč vymenila za koláč opačného druhu. Váš spôsob kódovania musí fungovať vo všetkých prípadoch, bez ohľadu na to, ktorý koláč Ježibaba vymení.

   Počet koláčov, ktoré Janko dostane na raňajky, si tento raz môže určiť Marienka. Tento počet však musí Ježibabe oznámiť ešte večer, nemôže sa teda o počte koláčov rozhodnúť až na základe času Ježibabinho odchodu. Snažte sa vymyslieť riešenie používajúce čo najmenej koláčov. Za ľubovoľné funkčné riešenie tejto podúlohy môžete získať až 3 body. Plných 5 bodov môžete dostať, ak bude vaše riešenie využívať iba 9 koláčov (áno, dá sa to :)).

5. (5 bodov) Ježibaba má rovnaký nepríjemný zvyk ako v podúlohe d), tentoraz však Janko s Marienkou navyše vedia, že sa chystá Janka upiecť už pozajtra ráno a teda si nemôžu dovoliť čakať ešte jeden deň. Preto sa musia dohodnúť na takom spôsobe kódovania, aby Janko vedel zistiť čas Ježibabinho odchodu, aj keby ktorýkoľvek koláč zjedla a nahradila koláčom opačného druhu. Čas Ježibabinho odchodu chcú tentoraz vedieť kódovať s presnosťou na sekundu (každá sekunda predsa môže byť rozhodujúca!), pričom Ježibaba môže ísť do lesa kedykoľvek medzi 9:00:00 a 20:59:59, musia teda vedieť rozlíšiť \(43\,200\) rôznych možností.

   Podobne ako v podúlohe d), aj v tejto podúlohe si môžete počet koláčov zvoliť sami, pričom opäť je cieľom použiť čo najmenej koláčov. Vaše riešenie však musí fungovať vždy, bez ohľadu na to, ktorý koláč Ježibaba vymení. Za akékoľvek funkčné riešenie môžete dostať až 3 body. Plných 5 bodov môžete dostať, ak vaše riešenie nepoužíva viac ako 34 koláčov.

6. (3 bonusové body) Bonusové body môžete získať, ak vyriešite podúlohu e) iba s pomocou 25 koláčov, ktoré však tentoraz Marienka nebude servírovať v jednom dlhom rade, ale v štvorci \(5 \times 5\) na štvorcovom podnose (ktorý má v jednom rohu kúsok odbitý, takže Janko vie povedať, kde je ľavý horný roh :)).