Question

La o inchisoare, deoarece era prea mare inghesuiala, gardienii au decis sa faca "curatenie" printre prizonieri. Au strans 100 de prizonieri, i-au pus intr-o sala si i-au informat urmatoarele
- Maine este ziua in care fie veti muri, fie veti fi eliberati
- Veti fi aranjati in sir indian
- Vi se vor pune palarii pe cap, de culoare fie alba, fie neagra
- Nu veti sti numarul de palarii albe sau negre, dar stiti numarul de palarii: 100
- Nu veti avea voie sa vorbiti intre voi
- Nu veti avea voie sa va uitati in jur
- Nu veti avea voie sa va uitati la palaria de pe capul vostru
- Al 100-lea prizonier va vedea in fata 99 de palarii, al 99-lea prizonier va vedea in fata 98 de palarii, si tot asa pana la al doilea prizonier care va vedea o singura palarie, pe a primului, care nu va vedea nimic.
- Vom incepe cu al 100-lea prizonier. Il vom intreba ce culoare are palaria lui. Daca raspunde corect, va fi eliberat, daca nu, impuscat. Apoi il intrebam pe al 99-lea, apoi pe rand, pe fiecare, pana ajungem la primul.
- In aceasta noapte veti sta impreuna si veti decide daca si cum sa va salvati. Succes!

Construiti un algoritm logic, prin care sa se salveze cat mai multi prizonieri. Se stie ca prizonierii s-au salvat toti, folosindu-se de o conventie pe care au gandit-o in acea noapte. 99 de prizonieri au avut 100% sanse de a se salva, al 100-lea a avut numai 50% sanse de a se salva (el a avut noroc). Ce algoritm au folosit?

Answer 1

M-am mai gandit, iar pe la ora 1 noaptea, am gasit solutia :)))

E nevoie de putina teorie de logica matematica, mai exact: Negatia negatiei unei propozitii este echivalenta cu propozitia initiala: ¬(¬p) ⇔ p.

Astfel, multimea raspunsurilor prizonierilor se extine de la 2 elemente (alb, negru) la 4 elemente (alb, NU alb, negru, NU negru).

Acum, cei 100 (pe care ii voi numerota cu numerele naturale: 1 (primul) ,2,3,...100 (ultimul) de prizonieri vor proceda in felul urmator:

Daca prizonierul cu numarul A (A∈N*) da unul din raspunsurile "x" sau "NU x" (unde x∈{alb, negru}), atunci prizonierul cu numarul A+1 va sti ca palaria sa are culoarea neagra.

Cu alte cuvinte: Daca raspunsul prizonierului cu numarul A contine cuvantul "x" (indiferent daca este afirmativ sau negativ, atunci, cel din fata va sti ca palaria sa are culoarea neagra.

Voi lua un exemplu: 1-alb 2-negru 3-negru 4-alb. Numarul 1 nu va sti ce culoarea are palaria sa (50% de supravietuire), astfel ca va da un raspuns la intamplare, dar asta in functie de culoarea palariei numarul 2 (negru sau NU negru). Acum, auzind cuvantul cheie "negru", numarul 2 va sti ca palaria sa are culoarea neagra, si va da un raspuns in functie de culoarea palariei lui 3 (negru). Acum 3 va sti ca palaria sa este neagra si va raspunde cu "NU alb", etc.