Cien personas no pueden comunicarse entre sí. Su único vínculo con el exterior es una bombilla que pueden encontrar encendida o apagada. La dificultad está en que nadie sabe en qué estado se encuentra al empezar.
La sala de la bombilla
Enunciado
Hay 100 prisioneros. Antes de empezar, pueden acordar una estrategia. Después, quedan todos incomunicados.
A partir de entonces, cada día el guardia elige al azar a un prisionero y lo lleva a una sala con una bombilla, que puede estar encendida o apagada. Los prisioneros no conocen el estado inicial de la bombilla.
Cada prisionero puede entrar muchas veces. En cada visita solo le permiten una cosa: dejar la bombilla como está o cambiar su estado.
En cualquier momento, cualquiera puede declarar: “Todos hemos pasado por la sala al menos una vez.” Si tiene razón, todos quedan libres; si se equivoca, todos mueren.
¿Qué estrategia les permite declarar con certeza que todos han pasado por la sala?
Ver solución
Solución
Respuesta: designan a un contador. Cada uno de los otros 99 prisioneros envía exactamente dos señales: enciende la bombilla cuando la encuentra apagada, hasta haberlo hecho dos veces en total. El contador apaga la bombilla cada vez que la encuentra encendida y lleva la cuenta. Cuando llega a 198, declara que todos han pasado.
La estrategia en detalle:
Antes de empezar, designan a un prisionero como contador.
Cada no-contador mantiene su propia cuenta de señales enviadas, inicialmente en cero.
Si un no-contador entra, ve la bombilla apagada y ha enviado menos de dos señales, la enciende y suma uno a su cuenta.
Si ya ha enviado sus dos señales, no toca la bombilla.
Si entra y la bombilla está encendida, no hace nada.
El contador, cada vez que entra y encuentra la bombilla encendida, la apaga y suma 1 a su cuenta interna.
Cuando el contador llega a 198, declara que todos han pasado por la sala.
¿Por qué funciona?
Hay 99 prisioneros que no son el contador, y cada uno puede aportar como máximo dos señales:
El único riesgo es que la bombilla estuviera encendida al inicio: en ese caso, el contador registraría una señal falsa al principio, contando algo que ningún prisionero encendió. Hay que demostrar que incluso así, llegar a 198 garantiza que todos han pasado.
Supongamos que algún no-contador nunca ha entrado a la sala. Los 98 restantes pueden aportar como máximo:
señales reales. Sumando la posible señal falsa inicial, el contador podría alcanzar como mucho 197. No puede llegar a 198.
Por tanto, si el contador llega a 198, todos los no-contadores han pasado al menos una vez. Y el contador también ha pasado, pues él mismo ha entrado para contar. La declaración es segura.