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.

autor Pavel Houser

Další články z rubriky

Související články

Tagy

hádanka · hádanky

pridat Linkuj | Jagg | Delicious | Facebook | vybrali.sme.sk

Komentáře

13.02.11, 11:55 DaliborPech

Řešení?

Vězni se domluví, že lampa zůstane rozsvícená, dokud bude někdo z nich na dvoře. Proto žádný z těch, kdo odejdou ze skupiny na dvoře, ani žádný z těch, které velitel předvolá znovu ze samotek, lampu nezhasne. Lampa bude svítit tak dlouho, dokud bude někdo na dvoře, tj., dokud bude alespoň jeden, kterého velitel ještě nepředvolal. Ti, kdo přijdou na další předvolání ze samotek, proto poznají z rozsvícené lampy, že ještě u velitele nebyli všichni. Teprve když bude předvolán poslední vězeň ze dvora, ten lampu zhasne a může oznámit veliteli, že již byli předvoláni všichni. Anebo mu to může oznámit ten vězeň, který bude předvolán ze samotky po něm, když uvidí lampu zhasnutou.

Toto řešení mi ale připadá jako příliš jednoduché, takže se domnívám, že autor má jiné. Bohužel, toto mi vyšlo jako optimální z jím uvedeného zadání.

08.02.11, 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

07.02.11, 14:22 KOffi

Možné řečení

Vězni si mohou vyměňovat jen jeden bit informace. Takže si myslím že řešení by mohlo vypadat třeba takto:
Vězni se domluví že pokud bude každý zavolán již třeba potřetí, lampu zhasne. Další je přivolán teprve potruhé, takže jí zase rozsvítí. Pokud nekterý vezeň bude přivolán tolikrát, že uvidí již potřetí zhaslou lampu. Je určitá pravděpodobnost, že byli přivoláni všichni. Samozřejmně je možná pravděpodobnost že jeden nebyl u šéfa ani jednou. Tomu se nechá zamezit zvětšením počtu návštěv u rozsvícené lampy.

02.02.11, 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.11, 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.11, 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.11, 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

29.01.11, 01:22 pavelhouser

skoda

skoda, ze pri presunu redakcniho systemu se smazaly starsi komentare :-(.
tak kazdopadne dekuji vsem, kdo se nad tim zamysleji nyni a doufam, ze tehdy (cca pred 5 lety) tu ulohu necetli a nediskutovali nad ni zde ti sami.
ono vubec - nakolik si ty clanky "znovupublikovane" pamatujete (a tedy vas rozciluji, resp. jsou pro vas neprinosne)?

28.01.11, 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.11, 15:13 lmecir

Re Nedokonalost úlohy

To je spíše chyba čtení zadání, protože je napsáno:
"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í")." Tím je samozřejmě zaručeno, že každý vězeň se v pracovně ocitne kolikrát je potřeba

28.01.11, 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.

28.01.11, 09:20 lmecir

Řešení (rovnou pro složitější případ)

Určí se jeden "kápo", který vězně spočítá. Každý z vězňů bude mít za úkol jednou lampu zhasnout, ale smí tak udělat jen v případě, že:

1) lampa zrovna svítí
2) vězeň ještě lampu nikdy sám nezhasnul
3) už byl předtím v pracovně velitele, a viděl lampu zhasnutou

kápo má za úkol:

1) spočítat spoluvězně
2) pamatovat si, co naposledy s lampou dělal
3) vždy při příchodu do pracovny lampu zhasnout, pokud je rozsvícená
4) vždy při příchodu do pracovny lampu rozsvítit, pokud byla zhasnutá, a:
4a) pokud už předtím byl v pracovně a lampu rozsvítil, započítá si, že jeden ze spoluvězňů lampu zhasnul. (spoluvězeň lampu nemůže zhasnout, pokud ji předtím neviděl zhasnutou, tudíž, pokud ji kápo předtím nerozsvítil). Jakmile se kápo ujistí, že všichni spoluvězni už lampu zhasli, oznámí to veliteli.

Tento postup je o poznání rychlejší, než postup, kdy (skoro) každý vězeň musí (zbytečně) lampu zhasnou dvakrát.

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.

Science World