Malá matematická hádanka: Jak se dostat z vězení?
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. Každý vězeň vstoupí do pracovny a bude moci něco provést s lampou..
Sdílet
***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.
Komentáře
08.02.2011, 21:18 pepaxxxx
pepa
Postup s kápem pro jednodušší případ: - kápo spočítá vězně = n - kápo je jediný kdo lampu rozsvítí - ostatní pouze lampu zhasínají - každý z ostatních zhasne lampu pouze jednou - až kápo rozsvítí lampu n-krát, pak ví jistě, že všichni vězni už byli
02.02.2011, 11:35 lukas-havrda
Nejednoznačné zadání
Není mi ze zadání jasné, jestli si šéf věznice vězně nejprve volá ze dvora nebo vždy jenom z cely.
31.01.2011, 10:15 starej-bambula
Třeba mi něco uniklo, ale...
Ten kdo jde poprvé změní stav, ten kdo už tam byl, na nic nehrabe?
30.01.2011, 11:33 sashacz
To hrnec84
A kdo tedy oznámí (a hlavně,jak to zjistí), že každý už navštívil místnost?
29.01.2011, 05:57 hrnec84
Řešení
Zfravím, ta úloha není zase tak těžká, řešení je myslím následovné: Pokud víme, že lampa svítí, vězni se domluví takto: každý, kdo jde poprvé, enchá lampu rožlou, kdo jde po druhé, zhasne. Vysvětlím na vzorku třeba 5 vězňů A, B, C, D. E. Jde A, jde poprvé, nechá lampu rožlou, jde C, taktéž poprvé, nechá lampu rožlou, jde E, poprvé, lampa zůstane po odchodu svítit. Jde znovu A, ví že jde podruhé, lampu zhasíná, jde B, ví, že jde poprvé, lampu rozsvicuje, jde E, ví že podruhé, lampu zhasíná, jde D, poprvé, lampu rozsvěcuje. Jde třeba znovu B, podruhé, lampu zhasíná, jde C, vidí, že je lampa zhaslá, tudíž ví že už bylněkdo podruhé, lampu nechává zhaslou..Atd. Jelikož je tu možnost oznámit i pozdějc, stačí určit maximální počet návštěv každého vězně (se domluví předem mezi sebou). Pro sichr se můžou domluvit na tom, že po 3. ánvětěvě lampu opět rozsvítí. Snad jsem to napsal srozumitelně Hezký den Roman
28.01.2011, 19:10 mrtvak
Uvaha
pokud by se jednalo o mensi pocet osob, tak bych volil prideleni cisel jednotlivym veznum (kterym bych to napsal nesmazatelnou barvou na prave predlokti :) ) a kazdy vezen by na lampu napsal to svoje - u 10 osob zadny problem pripadne by bylo mozno pristoupit na jednoduche posouvani lampy po stole od jednoho konce k druhemu a v okamziku kdy lampa stoji na druhem konci, je mozno zahlasit - uz tu neni zadny novacek - ma to ale dve mouchy. 1) reditel by nesmel byt neprejicnym clovekem, ktery si protoci 3 lidi ze 7 behem nekolika dnu a 2) je to nejdulezitejsi - je potreba, aby vsichni vedeli, kde byla lampa na zacatku kazdopadne je dle meho pohledu tato uloha dost komplikovana nevyslovenim jedna podminky - velitel se nezminil o tom, ze s lampou nebude nadale nic delat
28.01.2011, 14:13 anonym
nedokonalost úlohy
Úloha je algoritmicky korektně řešitelná, ale bohužel není úplně řešitelná. Tj. vězni se můžou vystřídat, ale nikdy na to nepříjdou. Například velitel si zavolá všechny vězně právě jednou a pak bude volat již jen jednoho vězně. V úloze by měla být třeba podmínka, že vězeň volaný v čase n bude znovu zavolán i v nějakém čase m>n.
Napsat vlastní komentář
Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.