4: Diez prisioneros y una bombilla

Si existe un problema cuyo enunciado me haya dejado turulato, es este: el problema de los diez prisioneros y la bombilla.
Antes de exponerlo, me gustaría puntualizar un matiz, que para los ajedrecistas es muy conocido: los problemas se pueden enfrentar con mentalidad táctica o con mentalidad estratégica.

Si piensas "Poniendo aquí el caballo, el rival lo eliminará con su álfil; y a continuación, yo podré eliminar su álfil y un peón, con lo que saldré ganando" tienes mentalidad táctica; buscas maniobras que te den un resultado tangible y a corto plazo.

Si piensas "Creo que la primera columna que se va a quedar libre de peones es la columna del álfil de dama (columna c); para cuando llegue ese momento, voy a ir colocando una mis torres en esa columna" tienes mentalidad estratégica; buscas ventajas invisibles y a largo plazo.

Aprovecho la ocasión para añadir que las jugadas de un buen estratega son incomprensibles para el jugador ocasional (que suele ser táctico al 95%), de modo que aparcar la mentalidad táctica y desarrollar la capacidad estratégica es lo que hace que crezca el número de personas que después de la partida le dicen a sus amigos en voz baja "Me ha ganado y es que no sé ni cómo".

¿Y cómo se desarrolla la visión estratégica? Obvio: resolviendo situaciones que carezcan de componente táctica: no hay piezas que comer, no hay casillas que ocupar, no hay elementos tangibles que mover de un sitio a otro... jugando a juegos que sean estrategia pura.

O resolviendo problemas estratégicos. Como el problema de los diez prisioneros y la bombilla. Estrategia en estado puro.
El enunciado dice así:

Diez prisioneros, han sido llevados a una sala con aspecto de aula de escuela, 
donde se les ha dicho que tomen asiento.  
El director de la prisión se coloca frente a ellos y les dice:
"Todos vosotros tenéis por delante una condena de cinco años.
Pero puede que os marchéis de la prisión mucho antes.
Cuando salgáis de esta sala, 
se os llevará a celdas separadas e incomunicadas. 
Empezando mañana, cada día, antes del desayuno, 
se elegirá a uno de vosotros al azar, y se le llevará a una habitación 
en la que no hay más que una bombilla y un interruptor. 
La bombilla no admite más opciones: o apagada o encendida. 
El prisionero que vaya mañana se la encontrará apagada 
y deberá decidir si la deja apagada o la enciende. 
Cada prisionero, cuando vaya a la habitación de la bombilla, 
puede dejarla como se la encuentre o puede pulsar el interruptor 
y cambiarla de estado, no pudiendo tocar absolutamente nada 
excepto el interruptor.
Si algún día, un prisionero cualquiera, al llegar a la habitación de la bombilla,
afirma "Ya hemos pasado los diez por la habitación" y es verdad, 
los diez serán puestos en libertad de forma inmediata.
Si algún día, un prisionero cualquiera, al llegar a la habitación de la bombilla,
afirma "Ya hemos pasado los diez por la habitación" y no es verdad, 
los diez serán ejecutados de forma inmediata.
Disponéis de una hora para deliberar y acordar una estrategia.
Pasado ese tiempo, se os llevará a la celda incomunicada".

Creo que es mi enunciado favorito. ¿A quién se le ha podido ocurrir? Lo pregunto a sabiendas de que no hay constancia de quién es el autor.

Y bien... ¿qué estrategia propones?
Si fueses uno de los diez... ¿qué dirías?
¿Puede ser lo mejor no arriesgarse y dejar pasar los cinco años de condena?
¿Dejamos que decida el azar, sorteamos un prisionero, y cuando lo lleven por tercera vez a la sala de la bombilla que diga "Ya hemos pasado todos por esta habitación"? Si alguien va por tercera vez, parece lo más probable que todos los demás ya hayan ido al menos una vez... ¿o mejor que lo diga a la cuarta?
¿O nos limitamos a dejar pasar un año y en cuanto pase "nos la jugamos"?
Hay demasiado en juego: si metemos la pata nos ejecutan ese mismo día.
¿Qué es lo mejor?

Vamos a pensarlo.
Dentro de unos días, colgaré una solución que me parece muy buena.
(Al final, han sido meses y no días lo que he dejado pasar... ¡Quién iba a contar con un accidente en el autobús, precisamente cuando se pone a escribir sobre PROBABILIDADES!)


SOLUCIÓN

Empezaremos con el “Enfoque erróneo número uno”. Dice así:

“Todos sabemos que al lanzar un dado común, la probabilidad de que salga un número cualquiera es un sexto. Por tanto, el número de lanzamientos teóricos necesarios para que salga un número cualquiera será seis. Si queremos que salgan los seis números, ¿cuántas tiradas deberemos esperar?

Fácil de calcular. En la primera tirada nos sirve cualquier número; en la segunda, cinco de seis; en la tercera, cuatro de seis... Como el tiempo que debemos esperar para que algo ocurra (o el número de tiradas que debemos hacer) es inversamente proporcional a su probabilidad, el número de tiradas necesarias para que salgan los seis números es:

Por tanto, cabe esperar que todos y cada uno de los seis números del dado hayan salido al cabo de 15 tiradas.

Aplicando el mismo razonamiento a los prisioneros, nos quedaría:

De donde concluiríamos que los diez habrán pasado por la habitación de la bombilla al cabo de 29’3 días. Añadimos una semana de margen de seguridad... El que entre el día 36º que diga “Ya hemos pasado todos por aquí” y listo; todos libres.”

¡¡ERROR!!

En el caso de los dados, 14’7 es “El valor frontera” que determina a partir de qué momento las probabilidades están a mi favor.

Si apuesto a “Con 13 tiradas voy a lograr los seis números”, a largo plazo acabaré perdiendo.

Si apuesto a “Con 10 tiradas voy a lograr los seis números”, a largo plazo acabaré perdiendo hasta las pestañas.

Si apuesto a “Con 16 tiradas voy a lograr los seis números”, a largo plazo acabaré ganando.

Si apuesto a “Con 20 tiradas voy a lograr los seis números”,  y encuentro incautos que acepten, a largo plazo acabaré ganando y mucho. Es más, como 20 es 15 incrementado un 33’3%, podemos redondear a lo bruto que voy a ganar al menos el 80% de los juegos, así que podría ofrecer 3:1 y a largo plazo seguiría ganando yo.

Inciso: hay gente que se mete en bwin sin saber qué es el valor frontera; los que están detrás de la maquinita sí que lo saben; luego pasa lo que pasa: a la larga, siempre ganan los dueños de la maquinita. Eso no quiere decir que los espíritus matemáticos no entremos en bwin; lo que quiere decir es que no apostamos ni un céntimo a probabilidades ridículas por mucho que se paguen mil a uno. De hecho, los dueños de bwin saben perfectamente que una pequeña parte de sus clientes cierran cada mes con ganancias (son los que hacen apuestas de sistema 3/7 o 4/7 sobre sucesos que se paguen 1’4:1 o 1’3:1). Y a los dueños de bwin les da igual. ¿Por qué? Pues porque también saben que son mayoría los que apuestan a lo loco. Y el que apuesta a lo loco puede acertar algún día una apuesta rara del tipo "Roger Federer cae derrotado en dos sets contra un esquimal desconocido", pero a la larga siempre va a perder; y el negocio, para los dueños, que razonan a muy largo plazo, seguirá siendo redondo.

Pues eso es precisamente la cifra 29’3. El valor frontera de nuestro problema de los prisioneros. Arriesgarte antes del día 29º sería una temeridad; antes del 20º, directamente se llama intento de suicidio. A partir del día 30 las probabilidades empiezan a estar a tu favor... ¡¡¡pero te estás jugando la vida!!! ¿A alguien le apetece poner su vida en manos de la buena suerte? Habrá que calcular algo más valioso que el valor frontera.

Veamos el “Enfoque erróneo número dos”.

“Si sabemos calcular el valor a partir del cual las probabilidades pasan a ser más del 50% a mi favor, también podré calcular a partir de qué día las probabilidades a mi favor alcanzan el 99%”; y ese día..., adiós a la cárcel.”

Claro que se puede calcular. Hagámoslo.

En principio, en lugar de un problema con 10 prisioneros y d días, ataquemos algo más simple: hagamos las cuentas del caso 3 prisioneros (A, B, C) y 3 días.
Casos FAVORABLES (Entran los tres): tres letras DIFERENTES ordenadas en tres posiciones:

O sea: Permutaciones de 3 sin repetición: 3!=3.2.1=6.

En efecto, ABC, ACB, BAC, BCA, CAB, CBA: 6.  

Casos DESFAVORABLES (Algún prisionero se queda sin entrar):

Habrá quien piense que viene dado por “Combinaciones con repetición de 3 sobre 3”:

Hagamos el recuento, a ver si tienen razón:

AAB, BBA, CCA, AAC, BBC, CCB, ABA, CBC, BCB, ACA, CAC, BAB, ABB, ACC, BAA, BCC, CBB, CAA: 18

y además AAA, BBB, CCC: 3.

Total: 21.

Pues no; no tienen razón. (Por supuesto, los casos totales son tres al cubo, 27; 6+21=27) 
Las fórmulas de combinatoria que se estudian (supuestamente) en secundaria sólo son de fiar cuando se trata de elegir subconjuntos de elementos con menor cardinal que el conjunto de partida; o sea, con menos elementos.

En nuestro caso, con 3 prisioneros y cinco días, un subconjunto posible sería: AACBA. Cinco elementos. Y el conjunto de partida sólo tiene 3: {A,B,C}. Más vale que en las fórmulas de combinatoria clásica tengamos una fe moderada: aquí no valen.

Hay que proceder de otro modo: para obtener ese “21” hay que calcular los casos en que han entrado dos prisioneros distintos o menos [ (combinaciones de 2 sobre 3)  multiplicadas por las formas en que pueden ordenarse sus visitas a la celda durante tres días (variaciones con repetición de 3 sobre 2) y restarle los casos en que han entrado un prisionero  distinto o menos (los casos AAA, BBB, CCC) porque si no los estaríamos contando dos veces ]. O sea:

¿Lo podemos generalizar para p prisioneros y d días?

Claro que sí; ¿por qué no se va a poder?

Generalizando Casos posible y Casos favorables, obtenemos esta preciosidad de fórmula, que no creo que nadie haya visto escrita en ningún sitio antes de hoy:

Y por supuesto, se cumple P(hayan entrado todos)=Cf dividido por Cp.

Ahora podemos fijar P(hayan entrado todos)=0’99, p=10 y calculamos d (por tanteo, obviamente... esa d no la despeja ni Batman). Resultado: d=66.

Así que con esperar dos meses y una semana, listo... Las probabilidades de éxito serían del 99%. Al legar el día 66, decimos que ya hemos pasado todos y listo; a casa. 

¡¡ERROR!!

Sigue habiendo un 1% en tu contra y lo que te estás apostando es la vida.

Una bolsa con 99 bolas blancas y una bola negra... Sólo hay una, sí, sólo una, es enormemente improbable... pero si metes la mano y sacas la bola negra te dejan fumarte tu último pitillo y te matan. ¿Te arriesgarías? 

Dado que nos jugamos la vida, lo correcto es buscar una estrategia que nos permita tener la certeza total de acierto.

¿Se puede?

Claro que sí... vamos a pensar un poco.

Supongamos que sólo puedo hablar yo. Para decir “Ya hemos pasado todos por esta habitación”, lo que necesito es que mis compañeros me dejen el mensaje de que ya han estado: o sea, que enciendan la bombilla; cuando la vea encendida, yo – que soy el único que tiene derecho a apagarla – la apago. Cuando la apague por novena vez puedo decir con certeza absoluta que todos hemos pasado por la habitación de la bombilla. Por supuesto, cada uno de mis compañeros debe encender la bombilla sólo la primera que le ocurra el suceso “entro en la habitación y me encuentro la bombilla apagada”. El resto del tiempo ya no tiene que hacer nada.

No sabemos si  saldremos de la cárcel el día 58º, el 79º, el 84º o el 136º o el que sea... De hecho las probabilidades no empiezan a ponerse a nuestro favor hasta bien avanzado el cuarto mes; o sea que lo más probable es que pasemos enchironados cinco meses y pico; pero sabemos que vamos a salir vivos, que no es poco.

Y este método, ¿se puede mejorar?

Claro.  

Hemos partido de la base de que soy yo el único que puede hablar. Pero... ¿y si pasa el primer mes completo – el azar es MUY caprichoso – y siguen sin llamarme a mí? Menudo desperdicio de tiempo. De entre los diez prisioneros, hay que elegir como “portavoz” a aquel cuya fecha de entrada en la habitación nos permita ahorrar más tiempo.

¿Y eso cómo se hace?

Aplicando dos subrutinas distintas.

> Subrutina de los primeros diez días: “Un prisionero cualquiera A sólo encenderá la bombilla si es la segunda vez que entra en la habitación y se la encuentra apagada. Dicho prisionero quedará nombrado “portavoz”. El único que tiene derecho a apagarla es el prisionero B que entre a la habitación el día 10º; y en ese momento, dejando la bombilla apagada, empezará la subrutina del resto de los días.

¿Hay que modificar algo si A=B? Nada.

¿Qué hace el prisionero B si al entrar en la habitación el día 10º con intención de apagar la bombilla, llega allí y se la encuentra apagada? Pues darle las gracias a todos los santos del cielo por haber tenido tantísima suerte (es prácticamente imposible), decir en voz bien alta “Ya hemos pasado todos por esta habitación”. Y luego ponerse a gritar “Nos vamos a casita, chicos”. Doy por hecho que todo el mundo ve como una obviedad que si el 10º se encuentra la bombilla apagada quiere decir que ya han pasado los otros nueve.

> Subrutina del resto de los días. La misma que hemos visto cuando “el portavoz era yo”.

¿Hemos ganado algo? Claro que sí. Si el que enciende la bombilla lo hace al entrar por segunda vez el día 8º, sabe que ya han pasado por la habitación SEIS de sus compañeros. Durante la segunda fase ya no tendrá que contar hasta NUEVE. Sólo tendrá que contar hasta TRES.

De esta manera – calcular el valor  exacto es muy complicado y yo ya me hago viejo, pero debe estar alrededor de 85 días – lo más probable es que no lleguemos a completar un trimestre en la cárcel. Comparado con cinco años...