STRATEGIA 0:

Dla nieśmiertelnych więźniów: Numerują dni 0 ... 98 0 ... 98 ... mod 99, poczynając od pierwszego dnia nastawiania żarówki. Każdego dnia 0 mod 99 więzień zapala żarówkę. Każdego innego, gdy jest zgaszona, to więzień pozostawia ją zgaszoną. Gdy jest zapalona, to więzień ją gasi, gdy był w pokoju wcześniejszego dnia w ramach danych 99; jeżeli był pierwszy raz (w ramach 99), to pozostawia żarówkę tak jak była. Dnia 0 mod 99, ale nie początkowego, gdy żarówka była zapalona, to więzień - o ile nie był w pokoju w czasie poprzednich 99 dni - oświadcza, że wszyscy (licząc też jego) byli w pokoju. Wtedy wszyscy będą wypuszczeni na wolność.

O! Mogę wpisać odp! Podałem metodę w komentarzu, ale zapomniałem dodać "wolność-hurra!". Otóż każdy więzień ma swój licznik. Pierwszego dnia wszyscy nastawiają na 1 (po najpierwszej wizycie więźnia wylosowanego jako pierwszego). W następnych dniach, więzień, który zostawił światło w pokoju, po wizycie innego więźnia dnia poprzedniego, dodaje tego dnia 1 do swojego licznika (czyli za każdą oświetloną przez siebie serię swoich kolejnych dni dodaje 1, nie więcej). Więzień, który na liczniku ma 100, krzyczy "wolność!" Jest to dobre rozwiązanie, bo:

A. pierwszego dnia był jeden więzień w pokoju ze swiatłem;

B. po pierwszej wizycie każdego innego wieźnia, co najmniej 2 było w pokoju;

C. w okresie pomiędzy dwoma kolejnymi wizytami danego więźnia, gdy pierwszy raz zostawił pokój ciemny, a drugi raz jasny, pewien (inny) więzień musiał złożyć w pokoju swoją pierwszą wizytę.

UWAGI:

• Kto zastał ciemność w czasie swojej 1' wizyty, może (po zapaleniu światła) nastawić swój licznik na 3.
• Rozwiązanie działa dla dowolnej liczby więźniów n (w miejsce 100).

STRATEGIA 1:

Więźniowie rozdają sobie numery w = 0 ... 99. Dni wizyt w pokoju są ponumerowane n=0 1 ... Każdy więzień-gość w, który odwiedzi pokój w dniu n=w mod 100 zostawia zapalone światło. W przeciwnym wypadku gość w zostawia światło zgaszone.

Każdy więzień w prowadzi swój notesik, w którym notuje dni n-1 mod 100, gdy w dniu n > 0 zastał światło zapalone (nie ważne, czy w=n mod 100 - zapisuje w notesiku tak samo). Gdy wejdzie do pokoju, i w notesiku otrzyma komplet 100 liczb (dołączając ewentualnie siebie, w, niezależnie od zachodzenia kongruencji n=w mod 100 tego dnia), to woła "wolność!".

ANALIZA (zmiast nowej strategii)

Pytanie jest niby z życia, czyli naukowe, ale nie (czysto) matematyczne. Rozwiązanie składa się z 2 etapów, A & B. Na pierwszym należy wyliczyć (oraz zauważyć, zorganizować i zrozumieć) jak najwięcej jak najsilniejszych środków, prowadzących do modelu matemaycznego o jak najsilniejszyc założeniach (pomagających więźniom). Etap ten jest naukowy - nie matematyczny. Drugi etap, to możliwie optymalne rozwiązanie w ramach uzyskanego modelu.

Etap A (naukowy):

1. Więźniowie mogą przydzielić sobie numery 0 ... 99, po jednym na głowę.
2. Więźniowie mogą numerować dni, od początkowej wizyty w pokoju z żarówką: 0 1 2 ...
3. W dniach 0 ... 98 więźniowie przekazują następnemu tylko 1 bit informacji: światło lub ciemność. Poczynając od dnia 99 przekazują więcej: (a) wychodzimy na wolność (b) światło (c) ciemność.

Uwagi o etapie A:

• Tylko umowa co do podziału więźniów na dwie rozłączne grupy pozwala więźniowi-gościowi w dniu 0 przekazać pewną informację gościowi z dnia 1. Podział, a najprościej i najlepiej pełne ponumerowanie więźniów, jest pomocne wielu sytuacjach.
• Posiadanie więcej niż 1 bitu, opisane w powyższym punkcie (c), jest trudne do wykorzystania. Pozwala na przykład ulepszyć STRATEGIĘ 0, z pierwszej odpowiedzi niniejszego wątku.

Etap B (matematyczny)

Matematycznie poprawne rozwiązanie wciąż a priori może być nie do wykonania. Można założyć, że więzień w pokoju z żarówką ma do podjęcia decyzji tylko 23h. Strategia musi być z tego powodu względnie prosta. Następująca strategia, gdyby była poprawna matematycznie (nie wiem czy jest), mogłaby być za mało konstruktywna: w dniu n > 0 więzień zostawia światło, jeżeli jest w pokoju po raz pierwszy, lub gdy wydedukował większą liczbę więźni, którzy odwiedzili pokój, niż za poprzednią wizytą w pokoju. A jak nie, to nie. Coś w tym guście. Może dla poprawności potrzebna jest jakaś bardziej złożona wariacja tego podejścia. Chodzi o to, że tego typu strategia (o ile poprawna) mogłaby więźniów wyprowadzać na wolność chyba optymalnie wcześnie, gdyby potrafili ją stosować za każdą wizytą w ciągu 23h, ale to może być niemożliwe, ze względu na złożoną iterację. Dlatego należy w tym duchu starać się o konstruktywne przybliżenia takiej strategii.

Strategia Postępu

Numerujemy dni wizyt w pokoju z żarówką w kólko 0 ... 99 0 ... 99 0 ... czyli mod 100, poczynając od zera. Czyli dni podzielone są na kolejne setki. W ramach każdej setki dni więzień-wizytor w dniu d zostawia światło, gdy wie, że w pokoju było więcej niż d różnych więźniów (wliczając jego samego). Więzień, który złożył więcej niż jedną wizytę liczy się wszystko jedno pojedynczo. Gdy więzień będzie wiedział przy swojej wizycie, że przez pokój przewinęła się (wraz z nim) cała setka więźniów, to ogłasza wygraną.

Mogę tę metodę opisać detalicznie i pedantycznie, ale zamiast tego planuję napisanie programu-symulacji. Jednym z powodów jest także to, że od ręki nie potrafię podać sensownych oszacowań efektywności niniejszej Strategii Postępu. Czuję (łudzę się? :-), że tym razem mój algorytm jest sensowny. Wiedza więźniów rośnie przy tym algorytmie żwawo (mówiąc probabilistycznie). Zakładamy, że więźniowie nie są głupkami.

Wyzywam też wszystkich na (nieformalny :-) pojedynek czy też raczej na zawody. Wymyślcie strategię. Zaprogramujcie. Będziemy programy puszczać dla tej samej funkcji pseudolosowej, z tymi samymi początkowymi "ziarnami", które będą wybrane losowo. W czasie pojedynczych zawodów sprawdziło by się programy dla 10 różnych ziaren.

Każdy program w zawodach powinien podawać feedback (powinien prowadzić tak zwany log) o sensownym rozmiarze, tak by było widać jak algorytm działa i sobie radzi.

Oczywiście zamierzam swój program podać na naqnaq (gdzie? jak? chyba można w dowolnym języku? Zacznę od perla, a potem napiszę raz jeszcze w C++, tak planuję).