Keďže Vás včerajšia úloha očividne veľmi nezaujala, možno Vás zaujme nasledovná jednoduchá, ale zábavná klasika.Ali Baba zajal 40 zbojníkov (trochu sme si prispôsobili pôvodný dej), ale rozhodol sa niektorých z nich ušetriť. Ali sa rozhodol, že zoradí všetkých 40 zbojníkov do zástupu tak, že každý z nich bude vidieť na hlavu všetkých zbojníkov pred ním, no nebude vidieť na zbojníkov za ním; bude ich len počuť. Potom im všetkým Ali položí na hlavu buď bielu, alebo čiernu čiapku. Ušetrený bude ten zbojník, ktorý uhádne, akú čiapku má na hlave. Svoj tip, t.j. slovo "biela", alebo "čierna" bude môcť každý zbojník povedať len raz a okrem toho nebude môcť povedať nič iné. Poradie, v akom budú zbojníci vyhlasovať svoje tipy, si môžu zvoliť. Predtým však môžete poradiť úbohým zbojníkom stratégiu, ktorá ich zachráni čo najviac. Pokúste sa ju vysvetliť čo najjednoduchšie, pretože je známe, že zbojníci vedia počítať len na prstoch a pritom niektorým z nich už zostal len jeden.
14 komentárov:
aaa, tak toto poznam, aj ked ja som to zadanie povodne pocula s uz urcenym poradim, ako maju zbojnici tipovat farby svojich ciapok. tu poslednu vetu si myslel ako nenapadny hint? :-)
:) Áno, tú poslednú vetu možno považovať za hint. Celkom sa potešilo keď som si uvedomil, že každému zbojníkovi na realizovanie optimálnej stratégie stačí (okrem zrakového a sluchového vstupu) len jednobitová pamäť RAM.
Napadla mi nie celkom optimálna stratégia. Budú hovoriť od posledného smerom k prvému. Zbojník na párnej pozícii vraví farbu čiapky zbojníka pred ním. Nepárny vraví svoju farbu (lebo ju práve počul od toho za ním). Teda polovica stojaca na nepárnych pozíciách určite prežije, a z tej druhej "štatisticky" možno prežije ďalších niekoľko jedincov. Táto stratégia si však vyžaduje medzi zbojníkmi príliš veľký výskyt obetavých hrdinov na to, aby bola použiteľná... asi optimálne riešenie napadlo môjmu bratovi a napíšem ho do ďalšieho komentára:
Pozor,
nečítajte tento komentár, ak nechcete počuť riešenie.
Stačí jeden charakterný a obetavý zbojník. Ten bude stáť posledný v rade, teda bude vidieť všetky čiapky okrem svojej. Ak vidí párny počet bielych čiapok, nech povie "biela". Ak vidí nepárny počet bielych čiapok, nech povie "čierna".
Zbojník na pozícii 39 hľadí a dumá. Ak sa mu parita bielych čiapiek podľa zbojníka 40 zhoduje s tým, čo vidí pred sebou, vraví "čierna". Ak sa nezhoduje, vraví "biela". Ak povie "biela", všetci pred ním si v mysli zmenia aktuálnu "paritu bielej" a pokračuje sa v podobnom duchu až po úplne prvého v rade. (Na tieto prerátavania parity stačí vedieť počítať v Z2, teda jedným prstom...)
Ani zbojník na samom čele radu nemusí vedieť počítať. Stačí, aby si na tom svojom jednom prste prepínal 0 a 1. Počíta tak, že po odpovedi zbojníka 40 si nastaví 0. Potom pri každej bielej prepína stav prsta - strieda 0 a 1. Ak má byť počet bielych párny, tak má bielu na hlave práve vtedy, keď mu vtedy keď je na rade, svieti na prste 1. Ak má byť bielych nepár, tak on má bielu, keď má na prste 0.
Vďaka za peknú hádanku :-)
rasto: Tvojmu bratovi napadlo naozaj optimalne riesenie. Fajn.
Inak túto úlohu mi pripomenul Braňo Novotný vo štvrtok (už som ju kedysi dávno počul, ale nepamätal som si detaily) a v prvej chvíli som zaregoval: "no, polovica sa dá zachrániť určite", podobne ako Ty :-)
Som rád, že sa úloha páčila.
Je zaujimave ze tuto ulohu mi pre par tyzdnami predlozil kolega Carlo. Islo o verziu so 100 zbojnikmi (kazdy moze povedat akekolvek jedno slovo, ak o bude farba jeho klobuka, zostane nazive, ak nie, ide het)...
Moj prvy napad ako ju vyriesit bol nasledovny: posledny zakoduje vsetky farby pred sebou ako jedno velke cislo v dvojkovej sustave a povie ho. Ostatni si to prelozia a zachrania sa.
Rastove riesenie je vsak elegantnejsie.
Zaujímavý je aj prípad, keď je zobjníkov nekonečne (spočitateľne) veľa. A aj tam sú ešte dve verzie tohoto problému.
1. Svoje tipy hovoria postupne (tak ako v konečnom prípade). Viete to spraviť tak aby sa pomýlil max. jeden?
2. Všetci povedia svoj tip naraz, teda okrem toho čo vidia nik nemá žiadne informácie navyše (dokonca, ani nemusí vedieť koľký v tom rade je). Vedia sa dohodnúť tak, aby sa ich pomýlilo len konečne veľa?
Ondrej B.
pri pouziti n prstov, sa to da rozsirit na 2^n farieb, len si ich treba ocislovat :-)
Ondro: Zdá sa, že to je veľmi zaujímavý variant. Prosím, skús to zadanie (tie zadania) popísať trochu presnejšie a možno z toho spravíme samostatný príspevok.(napríklad: ktorých zbojníkov vidí ktorý zbojník [vidí ich nekonečne veľa?], aké operácie vie robiť každý zbojník a podobne. Tiež nie celkom chápem ako môže v druhej verzii nejaký zbojník vôbec niečo vedieť o svojej čiapke, keď nepozná žiadnu informáciu od žiadneho iného zbojníka.)
Máme nekonečne veľa zbojníkov rade: 1,2,3, ... Zbojník n vidí zbojníkov s väčším číslom ako on. Každému dáme jeden z dvoch možných farieb klobúkov na hlavu.
1. Pýtame sa ich postupne (od 1) na farbu klobúku. Ako sa majú dohodnúť ak chcú aby max. jeden odpovedal nesprávne?
2. Spýtame sa ich všetkých naraz. Ako sa majú dohodnúť, aby sa ich pomýlilo vždy len konečne veľa? (Áno, niko z nich v skutočnosti nevie akej farby má klobúk. Dokonca ani nemusí vedieť koľký je v rade, teda aké má číslo.)
V skutočnosti to poznám s väzňami, tak ma teda napadá, či tu už bol problém s 100 väzňami a 100 truhličkami s ich menami. Ten sa mi sice nepodarilo vyriešiť, ale fakt ma ten spôsob riešenia udivuje.
Ondro: To prvé zadanie je jasné; fajn. Tomu druhému však stále celkom nerozumiem. Čo sa myslí tým, že sa ich spýtame "všetkých naraz"? Napíšu každý nezávisle v tichosti na svoj papierik tip aký majú klobúk a ten papierik potom naraz odovzdajú na posúdenie správnosti? To asi nie, lebo v tom prípade nemajú žiadnu informáciu o ktorú by sa mohli oprieť. Alebo sa vopred dohodnú na tom v akom poradí budú odpovedať po tom, čo im všetkým naraz položíme otázku aký majú klobúk? To tiež nie, lebo to by sa vopred dohodli na fixnom poradí a situácia by bola ako v zadaní 1.(Asi si musím dať na to kávu, lebo mi to takto zrána nezapaľuje...)
Žiadny problém so 100 väzňami a truhličkami s ich menami tu ešte nebol a dokonca ma vôbec nenapadá, či som niečo podobné niekedy počul.
Onedlho (dnes, zajtra?) odštartujem takú malú súťaž o najkrajšiu úlohu od čitateľov QEDu, takže možno by si sa mohol zapojiť napríklad s týmito väzňami.
Áno, odpovedajú nezávisle, napr. na hlasovací papierik. Áno, nemajú žiadnu informáciu o svojom klobúku. A predsa, kežže z týchto úvah vyplýva, že stredná hodnota počtu tých čo sa pomýlia je nekonečno, existuje spôsob ako sa dohodnú tak, že vždy sa pomýli len konečne veľa z nich (tie dve veci sa nevylučujú).
Ten problém so 100 väzňami určite pridám do súťaže.
Ondro: No, už viem; veľmi pozoruhodný, ale ťažký a absurdne kontraintuitívny príklad. Je to niečo také, ako keby sme sa tu bavili o tom, ako je možné zo siedmych kúskov tangramu poskladať kačičku a Ty by si nám zadal úlohu, ako je možné zo siedmych kúskov gule poskladať dve nové gule s rovnakým priemerom ako má tá pôvodná guľa. :-)
Pre tých, ktorí by tento príklad chceli riešiť, je podľa mňa na mieste doplňujúci komentár a to napriek tomu, že bude istou nápovedou. Riešenie totiž predpokladá niekoľko skutočností, ktoré riešiteľ nemusí považovať za samozrejmé (práve naopak, môže považovať za samozrejmé, že neplatia; aspoň teda prvé dve):
1) Zbojníci sa vedia dohodnúť na nespočítateľne nekonečne veľa faktoch a každý zbojník si ich aj dokáže zapamätať; 2) Každý zbojník, ak má odpovedať v konečnom čase, musí vedieť vykonať v ohraničenom čase nespočítateľne nekonečne veľa "myšlienkových operácií"; 3) Akceptujeme platnosť axiómy výberu.
Teším sa na Tvoju úlohu o (konečnom počte) väzňov a truhlíc. :-)
Ano, ta strategia je dost... teoreticka. Priklad poslem najskor zajtra, ked budem mat viac ako chvilku pri pocitaci.
Zverejnenie komentára