» Main » Messages  101000001001100101 

Ještě jsem si jednou pozorně přečetl zadání a nejsem si jistý, zda oněch 200 resp. 198 dnů, jak bylo správně podotknuto není špatná odpověď - jestli náhodou by tento speciální případ, kdy by byl každý druhý den "náhodně" vybrán "sčítač" a v liché dny všichni ostatní vězni neodporoval zadání v tom, že výběr má být náhodný s rovnoměrným rozložením.
Na druhé straně závěrečná otázka zní "Za kolik dnů nejméně se mohou všichni vězňové osvobodit?" - není tam napsáno "S JISTOTOU". Odpověď by mohla znít, že když Bůh dá tak je to za 100 dní. Vykašlou se na jakoukoliv strategii a rozsvěcení či zhasínání a stý den prostě vybraný vězeň řekne, že tam byli všichni. Takto se MOHOU (ale samozřejmě nemusejí) osvobodit již za 100 dnů.

Ne, je to 198 dní. Na zapsání každého vězně jsou potřeba 2 dny. 1, kdy jde do místnosti s žárovkou a zapne ji a druhý, kdy ho pověřená osoba přičte. To ovšem neplatí pro onu osobu pověřenou sčítáním, bo ta sama ví, že v místnosti byla tedy zbývá 99 vězňů. Čekání na stého by bylo jednoduše nezapočítání sebe sama. Mno a 99*2 je 198.

Jeden z vězňů je sčítač, který vždy, když bude on v místnosti, uvede světlo do výchozího stavu - např. vypnuto. Ostatní vězni mají za úkol rozsvítit, přijdou-li do zhasnuté místnosti a udělat toto pouze jedné návštěvě. Při ostatních návštěvách pak nedělají vůbec nic. Sčítač si započítá jednoho vězně vždy, když vejde do rozsvícené místnosti. Když vejde po 99 do rozsvícené místnosti, může z jistotou říci, že se všichni již vystřídali. Nejmenší počet dní, za které je toto realizovatelné je 200. A to tak, že jako první jde místnosti NEsčítač - ví že je první a ať je výchozí stav jakýkoliv, tak nechá na konci rozsvíceno. Druhý den jde sčítač, započítává si automaticky vězně z prvního dne a začnou postupovat výše popsaným postupem. Náhoda jim musí přát, aby sčítač byl v místnosti každý sudý den a v liché dny se tam postupně vystřídali ostatní vězni. To je tedy ten minimální počet dnů. S jakou pravděpodobností by se tento scénář mohl odehrát je však otázka druhá.

Otázka je formulována tak, že postup počítání vězňů nestačí, ale je nutnou podmínkou. Je třeba pro nalezený postup spočítat také nejmenší počet dnů (když všechna náhoda bude hrát pro ně), za který se mohou osvobodit.

Závěrečná otázka by měla jednodušeji znít, jakým způsobem vězni (vězeň zjistí) že už v místnosti byli všichni ... protože zde není napsáno řešení tak přikládám: protože je losování náhodné tak si vězni si mezi sebou zvolí koordinátora, který bude mít pokaždé, když přijde do místnosti mít za úkol vypnout lampičku. Jamile někdo ze vězňů přijde do místnosti poprvé a lampička bude vyplá vždycky ji zapne. Pak se jen je vždy počká až přijde koordinátor a tu vypne. A bude si zapisovat čárečky. Ti co přijdou do místnosti poprvé a lampička už svítí, budou holt muset počkat na jinou příležitost. Jakmile někdo lampičku zapne, už ji nikdy po druhé nezapíná. Pak se snadno jednoho dne koordinátor dopočítá, že už byli v místnosti všichni. Otázka za jak dlouho se to dá stihnout je nesmyslná vzhledem k náhodě losování, některý vězeň nemusí být vylosován třeba 10 let.