Zadanie
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é.
(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.
(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.
(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.
Podúloha a.
Lucka vie svoje otázky prispôsobovať Evkiným odpovediam.
Asi najjednoduchšie by bolo pýtať sa na jednotlivé dátumy pekne zaradom. Narodila sa Evka prvého? Druhého? Tretieho? Takto sa však pri najhoršom spýtame 30 otázok, čo je pomerne veľa.
Prvým zlepšením by mohlo byť pýtanie sa na deň deň v týždni, v ktorom sa Evka narodila. Bol to pondelok? Utorok? V najhoršom prípade by sa nám však mohlo stať, že položíme Evke šesť otázok na zistenie dňa v týždni a potom ešte 4 otázky na zistenie presného dátumu, keďže v jednom mesiaci môže byť najviac päť rovnakých dní. Lucke teda stačí 10 otázok.
Keď sme v predošlej úvahe rozmýšľali nad dňami v týždni, každou otázkou sme vylúčili jednu sedminu možností. Čo keby sme vylúčili nejakú väčšiu časť? Napríklad rovno polovicu. Prvou otázkou sa spýtame, či má narodeniny v prvej polke mesiaca. To nám hneď vylúči polovicu dní. Ak Evka odpovie áno tak sa jej spýtame či ich má v prvej štvrťke. Naopak ak Evka odpovie nie, tak sa jej spýtame, či má narodeniny v Tretej štvrtine mesiaca. Podľa Evkinej odpovede prispôsobíme a vyberieme jednu z otázok: či sa narodila v prvej, tretej, piatej alebo siedmej osmine mesiaca. Rovnako sa potom spýtame na šestnástiny a neskôr aj na 32-tiny.
Po piatich otázkach sa dozvieme presnú 32-tinu mesiaca, v ktorej má Evka narodeniny, teda konkrétny deň.
Podúloha b.
V tejto podúlohe už Lucka svoje otázky prispôsobovať nevie, ale musí ich napísať všetky dopredu.
V predošlej podúlohe sa nám podarilo zistiť dátum Evkiných narodenín na 5 otázok, skúsme teda otázky trochu poupraviť tak, aby sme ich mohli použiť aj v tejto podúlohe.
Prvá otázka ostane rovnaká, ak chceme zistiť, v ktorej polovici sa nachádza dátum narodením, musíme sa spýtať otázku “Narodila si sa medzi 1. až 15. dňom mesiaca?”.
Druhá otázka sa však už líšila podľa prvej odpovede. Buď sme sa pýtali na prvú alebo tretiu štvrtinu. Skúsme sa preto spýtať iba prvú z nich: “Narodila si sa medzi 1. až 7. dňom mesiaca?”. Ak dostaneme odpoveď áno, štvrtinu máme určenú. V prípade nie sa vieme pozrieť na prvú odpoveď. Ak nám totiž napísala odpovede “áno” (v prvej polovici), “nie” (v prvej štvrtine), musela sa narodiť v druhej štvrtine. Problémom je však tretia a štvrtá štvrtina.
Skúsme sa spýtať komplikovanejšiu druhú otázku: “Narodila si sa buď medzi 1. až 7. dňom alebo medzi 16. až 23. dňom?”. Z odpovede “áno” nevieme zistiť, v ktorej z týchto štvrtín to bolo. Ak však zoberieme do úvahy aj odpoveď na prvú otázku, polovicu, odpoveď je jasná. Na tieto dve otázky sme mohli dostať štyri možné kombinácie odpovedí a to je aj počet štvrtín, ktoré určujú.
Zvyšné otázky potom vieme skonštruovať ľahko. Treťou sa spýtame, či sa narodila v prvej, tretej, piatej alebo siedmej osmine mesiaca. Opäť, spolu s odpoveďami na predchádzajúce určíme konkrétnu osminu. Toto isté ešte spravíme pre 16-tiny a 32-tiny.
Týchto 5 otázok môže Lucka položiť Evke naraz a z odpovedí vie určiť presný dátum narodenia.
Okrem toho existuje aj mierne jednoduchšia sada otázok, aj keď o niečo trikovejšia. Vyzerá takto:
- Dáva číslo tvojho dňa narodenia zvyšok najviac 15 po delení 32? (polovica)
- Dáva číslo tvojho dňa narodenia zvyšok najviac 7 po delení 16? (štvrtina)
- Dáva číslo tvojho dňa narodenia zvyšok najviac 3 po delení 8? (osmina)
- Dáva číslo tvojho dňa narodenia zvyšok najviac 1 po delení 4? (16-tina)
- Dáva číslo tvojho dňa narodenia zvyšok 0 po delení 2? (32-tina)
Rozmyslite si, prečo tieto otázky fungujú.
Podúloha c.
Označme si náš počet otázok \(n\). Chceme aby sme po ľubovoľnej kombinácii Evkiných odpovedí vedeli presne povedať, kedy má narodeniny. To znamená, že každá možná kombinácia, nám musí presne určovať jeden dátum. Teda najviac rôznych dátumov vieme našimi \(n\) otázkami pokryť, keď každá možná kombinácia odpovedí nás dovedie k inému dátumu.
Keďže na každú otázku máme dve možnosti odpovede, tak každou ďalšou otázkou sa nám zdvojnásobí počet možných kombinácií odpovedí na jednotlivé otázky. Takže vlastne pre \(n\) otázok môžeme mať najviac \(2^n\) možných kombinácií odpovedí.
Na to, aby sme vedeli určiť presný dátum narodenia musí platiť, že \(2^n \geq 31\), teda že vieme rozlíšiť každý možný dátum. A najmenšie \(n\), ktoré toto spĺňa je práve \(n = 5\). Z toho vyplýva, že 5 otázok je skutočne optimálny počet.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.