***pravidelné páteční „přetištění“ staršího článku
Velitel věznice si pozve vězně na dvůr a oznámí jim, že mají šanci se dostat z vězení. Ovšem za určitých podmínek. V případě neúspěchu je naopak čeká smrt.
Velitel věznice nejprve rozsvítí lampu ve své pracovně. Pak si bude zvát náhodně (skutečně náhodně) jednotlivé vězně do své pracovny. Každý vězeň může být pozván i vícekrát (tj. případ „tažené míčky jsou vraceny do osudí“). Každý vězeň vstoupí do pracovny a bude moci něco provést s lampou (zhasnout jí, pokud zrovna svítí, rozsvítit, je-li zhasnutá, nebo ji nechat být). Poté bude odveden do své cely (v naší věznici jsou pouze samotky) a zavolán bude další vězeň. A tak dále.
Vězňové mají za úkol zjistit (ze stavu lampy), že už byli alespoň jednou povoláni všichni, a oznámit to veliteli věznice. Pokud ale někdo z vězňů prohlásí, že už byli voláni všichni, aniž to bude pravda, budou namísto propuštění všichni zastřeleni.
Vězni nyní stojí na dvoře a musejí se domluvit na optimální strategii týkající se zacházení s lampou. Pak už spolu mluvit nebudou moci. Jak mají postupovat?
Poznámky:
– Cílem je najít spolehlivý postup, jak zjistit, že se všichni vystřídali. Malá pomůcka – není ale nutné to říct přesně ve chvíli, kdy k tomu dojde, lze to oznámit i později.
– Hledáme ovšem konkrétní algoritmus. Pokud jsou vězni vybíráni opravdu náhodně, je jasné, že stačí počkat nekonečný (respektive co nejdelší) čas a všichni se vystřídají s pravděpodobností blížící se jedné. To ale není řešení.
Složitější případ:
Velitel věznice vězňům při této zkoušce neřekne, zda lampa bude na počátku rozsvícená nebo zhasnutá. Možné je oboje.
