Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Timke na [email protected]

Lucka a Evka su veľmi dobré kamarátky. Nedávno mala Lucka narodeniny a Evka jej pripravila úžasnú párty. Lucka by to chcela Evke oplatiť, zabudla však, kedy má Evka narodeniny. Jediné, čo si pamätá je, že ich má v marci.

Úloha

Lucka sa nechce priznať Evke, že zabudla kedy má narodeniny. Radšej na to príde nejakým nenápadným spôsobom, aby si to Evka nevšimla. Rozhodla sa, že jej bude dávať nenápadné otázky, na ktoré jej Evka bude odpovedať áno alebo nie. Týchto otázok však nemôže byť priveľa, pretože potom by sa to Evke určite zdalo podozrivé.

1. (5 bodov) Lucka vie, že sa Evky môže spýtať postupne na všetkých 31 dní a zistiť tak, v ktorý má Evka narodeniny, ale to by bolo príliš nápadné. Pomôžte jej vymyslieť spôsob, akým sa dozvie kedy má Evka narodeniny tak, že jej položí čo najmenej áno/nie otázok.

Otázky sa Lucka pýta postupne, môže ich teda vymýšľať na základe Evkiných odpovedí. Evka je pravdovravná a Lucke nikdy neklame. Dajte si však pozor, že váš spôsob musí počítať so všetkými možnými odpoveďami a musí fungovať bez ohľadu na to, či sa Evka narodila 1., 12. alebo 31.

Lucka sa už chystala Evky opýtať niektorú z otázok, keď jej napadol oveľa rafinovanejší spôsob ako zistiť dátum Evkiných narodenín. Napíše všetky svoje otázky na papier a podstrčí jej ho v škole do lavice. Tak Evka nebude vedieť, kto jej otázky poslal, takže nepríde na to, že Lucka zabudla kedy má narodeniny. Stále jej však nemôže položiť priveľa otázok pretože potom by ju Evka mohla spoznať podľa písma a kvôli zdĺhavosti posúvania papierikov to musí zvládnuť jednou sadou otázok.

1. (6 bodov) Zmenia sa nejako otázky, ktoré musí Lucka klásť, ak ich musí všetky napísať dopredu? Na koľko najmenej otázok sa vie Lucka dozvedieť kedy má Evka narodeniny v tomto prípade?

Všimnite si, že v tomto prípade Lucka nevie otázky upravovať na základe Evkiných odpovedí. Napriek tomu má z jej odpovedí vedieť jednoznačne určiť, kedy sa narodila.

2. (4 bodov) Lucku by zaujímalo či použila najmenej otázok ako mohla (iba tak bude totiž najmenej nápadná). Ukážte jej, že váš spôsob zadávania otázok je najlepší možný, teda že pri ňom použijete najmenší možný počet otázok.