Pamiętacie jeszcze zagadkę o dziesięciu więźniach i lampie?
Dziś czas na kolejną zagadkę o tematyce więziennej. Tym razem jednak zamiast lampy mamy pudełka, a zamiast dziesięciu więźniów - całą ich setkę.
A więc tak: w pewnym więzieniu siedzi stu osadzonych. Któregoś dnia naczelnik ogłosił:
– Panowie, macie szansę wyjść na wolność. Jednak nie ma nic za darmo: jeżeli szansy tej nie wykorzystacie, wszyscy zostaniecie skazani na śmierć.
Więźniowie słuchali z rosnącym niepokojem, ponieważ z tego, co dalej mówił naczelnik wynikało, że w zasadzie już mogą iść na krzesło elektryczne. Szanse bowiem na uwolnienie mają kosmicznie małe.
Warunki, jakie postawił naczelnik, są takie:
Każdy z więźniów zostanie wpuszczony - pojedynczo - do pokoju, w którym znajduje się sto pudełek ustawionych w równym rządku jedno koło drugiego.
Każde pudełko ma w środku karteczkę z numerem i nazwiskiem więźnia.
Każdy z więźniów może zajrzeć do pięćdziesięciu wybranych przez siebie pudełek, i ani jednego więcej. Zaglądając, nie może jednak niczego przesuwać, przestawiać ani ogólnie zmieniać.
Jeżeli wśród tych (maksymalnie) pięćdziesięciu pudełek znajdzie swój numer i nazwisko, wychodzi z pokoju i od tej pory nie ma już możliwości skontaktowania się z innymi więźniami. Specjalnie przeszkolony strażnik sprawdza też na wszelki wypadek, czy więzień ów nie poprzestawiał pudełek ani nie pozostawił jakichś wskazówek dla kolejnych więźniów. Krótko mówiąc, nie ma żadnej możliwości, żeby więźniowie przekazywali sobie jakiekolwiek sygnały czy informacje. Kolejny więzień wchodzi do pokoju i może zajrzeć do pięćdziesięciu wybranych przez siebie pudełek. I tak dalej.
Jeżeli którykolwiek z więźniów nie znajdzie "swojego" pudełka w maksymalnie pięćdziesięciu próbach, wszyscy więźniowie zostają skazani na śmierć. Jeżeli natomiast wszyscy znajdą swoje karteczki, cała setka wychodzi na wolność.
Zanim jednak zaczną, naczelnik łaskawie pozwolił więźniom opracować strategię, dzięki której mogą oni próbować zwiększyć swoje szanse na przetrwanie.
Pytanie: jaką strategię powinni przyjąć więźniowie, aby zmaksymalizować swoje szanse na przeżycie?
Pytanie bonusowe #1: Jeżeli więźniowie przyjmą najlepszą możliwą strategię, jakie mają szanse na przeżycie?
Pytanie bonusowe #2: Jeden ze strażników po kryjomu sympatyzuje z więźniami. Tuż przed wpuszczeniem pierwszego więźnia ma on możliwość zajrzenia do wszystkich stu pudełek. Może też zamienić zawartość dwóch wybranych przez siebie pudełek miejscami. Co powinien zrobić ów strażnik, żeby znacząco poprawić szanse więźniów na wypuszczenie na wolność?
Na zakończenie przedstawię jeszcze jedno obliczenie, żeby "zastartować" mózg Czytelnika, który chciałby się podjąć rozwiązania zagadki. Otóż jeżeli każdy z więźniów zajrzy do losowo wybranych pięćdziesięciu pudełek, wówczas szansa pojedynczego więźnia na trafienie na "swoje" pudełko wynosi 1/2, co podniesione do setnej potęgi (prawdopodobieństwa się mnoży) daje \(0.5^{100}\) czyli niecałe \(7.9*10^{-31}\). Raczej słabo. Można lepiej.
P.S. Wyłączam możliwość komentowania pod tym wpisem - jeżeli masz pomysł na odpowiedź, zapraszam do kontaktu.
Ale czy jeżeli dany więzień znajdzie pudełko ze swoim numerem, to czy to pudełko zostaje usunięte z puli, tak że następny więzień ma o jedno mniej?
Usunięcie pudełka oznaczałoby przekazanie informacji kolejnym więźniom, co jest wbrew warunkom zagadki. Każdy więzień ma do wyboru 100 pudełek. Niczego nie usuwamy.