Dziś zabierzemy się za uwalnianie więźniów.
Wyobraźmy sobie taką oto - nieco abstrakcyjną i nijak się mającą do rzeczywistości - sytuację:
W więzieniu siedzi dziesięciu więźniów. Grube bandziory co to dużo mają za uszami i raczej nieprędko wyjdą.
Każdy z nich ma własną celę i nie ma możliwości skontaktowania się z pozostałymi więźniami.
Któregoś dnia naczelnik więzienia dochodzi do wniosku, że bandziory generują mu za duże koszty i postanawia się ich pozbyć. W tym celu organizuje grę, w wyniku której albo cała dziesiątka pójdzie do piachu, albo się ich zwolni. Warunki gry są następujące:
Począwszy od jutra, każdego dnia będzie losowany numer jednej z cel. Więzień z tej celi będzie prowadzony do specjalnego pomieszczenia, w którym znajduje się lampa.
Po wejściu do owego pomieszczenia więzień ma do wyboru trzy możliwości:
- Włączyć lampę (jeżeli była wyłączona) bądź też ją wyłączyć (jeżeli była włączona) lub
- Zignorować lampę i wrócić do swojej celi lub
- Oznajmić, że kończy grę.
Jeżeli którykolwiek z więźniów oznajmi, że kończy grę, gra się kończy w następujący sposób:
- Jeżeli podczas gry każdy z więźniów odwiedził pomieszczenie z lampą przynajmniej raz, więźniowie wygrywają i wszyscy wychodzą na wolność.
- Jeżeli chociaż jeden z więźniów ani razu nie był w pomieszczeniu z lampą, wszyscy dostają wyrok śmierci.
Więźniowie mają okazję spotkać się jednorazowo przed rozpoczęciem gry i ustalić strategię.
Pytanie brzmi: jaką strategię postępowania powinni ustalić więźniowie, aby wyjść na wolność bez ryzyka, w możliwie najkrótszym czasie?
Dla jasności:
- To jest "uczciwa" zagadka. Więźniowie nie mogą sobie przekazywać żadnych informacji, nie ma szmuglowania karteczek, skrobania nazwisk pod blatem itd. Jedyne co mają do dyspozycji to lampa i własne mózgi.
- Losowanie numeru celi odbywa się z rozkładem równomiernym (każdego dnia każdy więzień ma równe szanse na bycie wylosowanym)
- Przed rozpoczęciem gry lampa jest wyłączona.
- Nikt poza więźniami nie ma dostępu do lampy - lampa włączona jednego dnia pozostanie włączona dopóki któryś z więźniów jej nie wyłączy ( i vice versa).
Czas start...
Czegoś brakuje w zagadce. Czy stan lampy jest przez cały czas widoczny z cel?
Nie. Lampa jest widoczna jedynie po wejściu do pokoju z lampą. Więzień zamknięty w celi nie ma żadnego kontaktu ze światem zewnętrznym.
powiedzieć naczelnikowi, że losowanie ma być bez powtórzeń ;).
A serio: więzień może zmienić tylko stan z 0->1. Wybrany więzień zeruje flagę i zlicza.
Ale ile to potrwa…
Blisko, ale brakuje jednego szczegółu.
więźń może zmienić flagę tylko raz.
Zgadza się. Całe szczęście, że nie przewidziałem nagród za podanie poprawnej odpowiedzi, bo bym teraz musiał przyznać nagrodę 😀
Wybierają szefa ,który będzie zapalać lampy ,ten który jest pierwszy raz gasi światło jeżeli lampa jest zgaszona, a więźeń jest pierwszy raz to i tak ignoruje. Ci co byli ignorują. Szef musi liczyć ile razy zapalał lampę.
Zgadza się! Tu więcej szczegółów, średni czas trwania gry itd: https://xpil.eu/wiezniowie-i-lampa-rozwiazanie-zagadki/