Am primit soluţii corecte de la: Ady Nicolae, Dan Florescu, Bogdan Burlacu, Horia Ciobanu, Valentin Ştefan, Zoltan Szabo, Irina Dinu.
Cu mici scăpări la concluzii: Ştefan Gaţachiu.
Cum toate soluţiile sunt similare, am ales-o pe cea a lui Horia Ciobanu:
În timpul mesei comune din ziua de Paste, deţinuţii aleg pe unul dintre ei - un Numărător - capabil sa numere până la 99 si stabilesc următoarele reguli:
· Fiecare deţinut (în afară de Numărător) va aprinde becul o singură dată, la prima ieşire când găseşte becul stins.
· Doar Numărătorul va stinge becul în momentul în care îl găseşte aprins şi va număra de câte ori l-a stins. Nu va aprinde becul dacă îl găseşte stins.
În momentul în care Numărătorul ajunge la 99 de stingeri, va cere să vorbească cu directorul închisorii şi va afirma cu siguranţă ca prin acea cameră au trecut - cel puţin odată - toţi cei 100 de deţinuţi.
Petre Cristina dă următoarea soluţie:
Fiecare detinut sa aprinda becul prima data cand intra in acea camera, incat sa ramana cu o arsura (pentru ca nu este izolatie).
La urmatoarea masa comuna isi vor putea da seama daca toti detinutii au o arsura de la bec sau nu. Si tot asa, pana cand la o masa comuna chiar vor avea toti arsura si vor sti ca toti au trecut prin acea camera.
Aurel Ionescu are ideea a trei echipe de deţinuţi, cu trei Număratori, fără să specifice cum face fiecare Nămărător distincţia că prin cameră trece un deţinut din echipa lui.
Zoltan Szabo consideră câteva extensii ale problemei:
1. Nu se stie starea initiala a becului din camera centrala.
In acest caz fiecare detinut va trebui sa aprindă becul de 2 ori. Numaratorul va trebui sa numere 2x99=198 de becuri aprinse. Astfel chiar daca becul initial aprins a fost numarat involuntar de numarator, va fi un detinut ce nu mai apuca sa aprinda becul a doua oara, iesind socoteala de 198 de becuri pentru numarator. Indiferent de starea becului initial, toata lumea va iesi cel putin o data din celula lui.
Sa observam, ca becul aprins "fura" o singura data o singura sansa de la un singur detinut. Chiar de aceea e nevoie ca toata lumea sa faca vizita de doua ori la bec.
2. Becul initial este stins, dar exista k gardieni si fiecare dintre ei pot actiona asupra becului (sa aprinda, sa stinga becul sau sa nu faca nimic )
Sa observam ca daca un gardian stinge lumina, "fura sansa" detinutului curent, care nu va mai fi contorizat de numarator.
Daca gardianul aprinde lumina, atunci va fi numarat pe nedrept un detinut in plus, "furand sansa" ultimului detinut din coada, care nu mai apuca sa fie numarat.
Daca gardienii nu lucreaza organizat, atunci unul aprinde lumina, celalalt stinge lumina, astfel doi cate doi se pot anula, iar eroarea in numarare devine mai mica.
In consecinta activitatea gardienilor este eficienta atunci cand intervin intre un detinut si numarator. Iar eficienta maxima ating atunci, cand toate actiunile dezavantajeaza acelasi detinut.
NU ESTE BUNA urmatoarea strategie, prin care fiecare detinut va cauta aprinda lumina de k+1 ori (poate unii nu vor apuca sa le faca pe toate), pentru ca:
1. Daca gardienii nu intervin, toate cele 99(k+!) de incercari ar fi numarate, din care daca scadem k numarari, la pasul 99k+99-k, deja se stie ca toti au iesit pe coridor.
2. Daca gardienii vor stinge luminile, toti furand sansa unui singur detinut (in total de k ori), atunci dintre cele 99(k+1) de aprinderi de becuri, numaratorul va vedea cu k mai putin, adica 99k+99-k, deci reuseste sa prinda ultima actiune a ultimului detinut, la pasul 99k+99-k.
3. Daca gardienii vor aprinde luminile, atunci numaratorul va numara k gardieni in loc de k detinuti. Daca si de aceasta data numaratorul va numara pana la 99k+99-k , atunci se pierd cele k numarari ale numaratorului pe care le ignora, la care se adauga cele k "furturi de sanse" cauzate de gardieni. Astfel detinutii sunt dezavantajati de 2k actiuni asupra becului, existan posibilitatea ca un detinut sa nu fi fost iesit din celula niciodata. Deci acesta strategie nu este buna.
De aici deducem ca dacă cei k gardieni pot afecta negativ 2k actiuni asupra becului, strategia optima va cere ca detinutii sa caute sa aprinda lumina de 2k+1 ori. Deci:
1. Presupunem ca gardienii nu intervin, toate cele 99(2k+!) de incercari ar fi numarate, din care daca scadem 2k numarari, la pasul 198k + 99 - 2k, deja se stie ca toti au iesit pe coridor.
adica de la 198k+99-2k pana la 198k+99 la fiecare timp numaratorul stie ca totii au iesit, iar momentul 198k+99+1 nu mai exista.
2. Presupunem, ca gardienii vor stinge luminile, si admitem cazul cel mai nefavorabil, ca toti "fura" sansa unui singur detinut (in total de k ori). Daca toti detinutii aprind de cate 2k+1 ori becul, dintre cele 99(2k+1) de aprinderi de becuri, numaratorul va vedea cu k mai putin, adica 198k+99-k becuri aprinse. In acest caz, momentul 198k+99-k+1 nu exista. iar noi putem fi siguri ca incepand de la pasul 198k+99-3k pana la pasul 198k+99-k toti detinutii au iesit cel putin o data.
3. Presupunem, ca gardienii vor aprinde luminile de k ori, si admitem cel mai nefavorabil caz, cand exceptand un singur detinut (cel nefavorizat), toti vor iesi de 2k+1 ori. Sa presupunem prin absurd, ca si cel nefavorizat iese la plimbare de 2k+1 ori, in acest caz numaratorul va contoriza 99(2k+1)+k aprinderi de becuri, adica 198k+99+k. Dintre toate acestea incepand de la pasul 198k+99-k pana la pasul 198k+99+k se va stie ca toti detinutii au iesit cel putin o data pe coridor.
Celelalte cazuri nu sunt cazuri extreme, deci intervalul de solutii de la cazul 1 nu se poate deplasa spre stanga sau spre dreapta cu mai mult decat in cazurile descrise la cazurile 2 si 3.
Pentru cele trei cazuri avem o singura solutie comuna: detinutii vor urmari ca sa aprinda de 2k+1 ori becul, iar la pasul 198k+99-k, numaratorul va sti sigur ca toti detinutii au fost iesiti din celula, indiferent de strategia gardienilor.