10. príklad - Vzorové riešenie
Zadanie
Vedúci majú 6 navzájom rozoznateľných typov mincí s hodnotami 1, 2, 5, 10, 20, 50 (z každej ľubovoľne veľa), ale nevedia, ktorá má akú hodnotu. Automat, ktorý našli, im vie poskytnúť cukríky, každý s cenou 1. Keď hodia do automatu nejaké mince, dostanú cukrík a výdavok, teda sumu o 1 menšiu ako vhodili. Výdavok dostanú iba v rovnakých typoch mincí ako mali na začiatku.
Koľko najmenej cukríkov si potrebujú kúpiť, aby bez ohľadu na to, ako bude automat vydávať, vedeli s istotou určiť hodnotu každej mince?
Vzorové riešenie
Ak by sme do automatu hodili štyri alebo menej mincí, tak by sa mohlo stať, že sme mali smolu a nehodili sme dvadsiatku ani päťdesiatku. V takom prípade by sme ale nemohli vedieť, ktorá minca je dvadsiatka a ktorá päťdesiatka. Ešte sme ich totiž nehodili do automatu a ani automat nám ich určite nevydal (nemal z čoho tak veľa vydávať). Preto štyri cukríky stačiť nemôžu.
Skúsme teraz hodiť päť rôznych
Najľahšie zistíme, keď sme do automatu hodili jednotku - vtedy nám totiž nevydá nič. Aj keby sme ju do automatu nehodili, vieme, že zo všetkých ostatných nám niečo vydal a teda tá posledná musí byť jednotka.
Keď už poznáme jednotku, je ľahké zistiť, ktorá minca je dvojka. Automat nám z nej totiž musí vydať iba jednotku. Ak nám zo žiadnej jednotku nevydá, vieme, že tá posledná minca musí byť dvojka.
Keď už poznáme jednotku a dvojku, je ľahké zistiť, ktorá je päťka. Automat nám z nej totiž musí vydať 4 a môže vydať iba v jendotkách a dvojkách, ktoré už poznáme. Takisto ako predtým, ak nám zo žiadnej mince nevydá 4, tak to musí byť tá posledná minca.
Takto vieme nájsť každú mincu. Ak už poznáme všetky menšie mince, vieme ju nájsť, lebo automat z nej môže vydávať iba menšími mincami (napríklad ak vieme, ako vyzerajú všetky mince od desiatky nižšie, vieme spoznať dvadsiatku, lebo automat z nej vydá 19 v menších minciach).
Príklad
Povedzme, že nám automat vydal takto.
Vieme ľahko spoznať jednotku - je to žltá minca. Z nej nám totiž automat nevydal nič.
Keď už toto vieme, vieme ľahko spoznať aj dvojku - to je ružová minca. Z nej nám totiž automat vydal 1.
Nevidíme žiadnu mincu, z ktorej by automat vydal 4. Preto vieme, že päťka musí byť tá minca, ktorú sme do automatu nehodili - čiže fialová minca.
Teraz už vieme, že jednotka je žltá, dvojka ružová a päťka fialová. Vieme teda nájsť desiatku - oražovú. Vidíme totiž, že z nej automat vydal 9.
Teraz vieme nájsť dvadsiatku - je to zelená minca, lebo vidíme, že z nej vydal 19.
Posledná, ktorá nám ostala je päťdesiatka, ktorá je modrá. Vidíme, že z nej automat vydal 49.
Takto teda vieme ísť od najmenšej mince a postupne ich zistiť všetky. Potrebujeme teda kúpiť päť cukríkov.