Problema dels 100 presoners

En el dilema dels 100 presoners, cada presoner deu trobar el seu número en un dels 100 caixons, pero cada u només pot obrir 50 caixons.

El dilema dels 100 presoners i 100 caixons és un problema en la teoria de la provabilitat i la combinatòria. Consistix que cada u de 100 presoners deu trobar el seu número en un dels 100 caixons per a sobreviure i si algun no ho troba, tots moriran; i, cada presoner pot obrir només 50 caixons i no pot comunicar-se en els demés presoners, llevat en el debat previ de l'estratègia.

A primera vista, la situació és desesperada, pero existix una estratègia que oferix als captius una oportunitat de supervivència aproximadament del 30%. El científic en computació danés Peter Bro Miltersen va ser el primer en propondre este problema en el 2003.

Problema

En la lliteratura es troben diferents enunciats d'este problema. A continuació es mostra la versió de Philippe Flajolet i Robert Sedgewick:

El director d'una presó oferix a un centenar de condenats a mort (numerats de l'1 al 100) una última oportunitat. En una sala hi ha un armari en 100 caixons. El director coloca aleatoriamente en cada caixó un dels números d'1 a 100. Els presoners entren en la sala, un darrere l'atre. Cada u dels presoners pot: obrir i comprovar només 50 caixons en qualsevol orde, i despuix tanca tots els caixons. Si en esta busca tots els presoners han trobat respectivament el seu número, tots els presoners són perdonats; si un presoner no trobara el seu número, tots els presoners seran eixecutats. Ans que el primer presoner busque el seu número, els presoners poden discutir l'estratègia, pero no poden comunicar-se a partir d'este moment. ¿Quin és la millor estratègia dels presoners? ^{cita requerida}

Si el presoner selecciona 50 caixons de 100 a l'encert, la provabilitat de que trobe el seu número és el 50%. La provabilitat de que tots els presoners, buscant aleatoriamente en els caixons de dit armari, troben els seus números, és el producte de la provabilitat d'èxit individual de cada presoner, és dir, (Plantilla:Sfrac)¹⁰⁰ ≈ 0,0000000000000000000000000000008, un número significativament menut. La situació sembla desesperada.

Solució

L'estratègia

Sorprenentment existix una estratègia que proporciona la provabilitat de supervivència de més del 30%. La clau de l'èxit radica en el fet de que els presoners no necessiten decidir de bestreta quins caixons obrir: cada presoner pot utilisar l'informació rebuda del contingut dels caixons ya oberts, per a decidir quin obrir despuix. Una atra important observació és que l'èxit d'un presoner no és independent de l'èxit d'atres presoners, ya que tot depén de cóm es varen distribuir els números en els caixons.

L'estratègia descrita cobrix no només els presoners, sino també els caixons numerats de l'1 al 100 (per eixemple, renc per renc, a partir del primer caixó del cantó superior esquerra de l'armari). L'estratègia a seguir és:

1. Cada presoner, primer obri el caixó en el seu número.
2. Si este caixó conté el seu número, el presoner ha conclós en èxit.
3. En cas contrari, el caixó conté un número d'un atre presoner, i s'obri el caixó en dit número.
4. El presoner repetix els passos 2 i 3 fins que trobe el seu número o fins a obrir els 50 caixons.

Començant en el seu propi número el presoner es garantisa de seguir una seqüència d'obertura de caixons en el que puga finalment trobar el seu número. L'única qüestió residix en si la seqüència és major de 50.

Vore també

• Dilema del presoner