La sala de la bombilla

Hay 100 prisioneros. Cada día, el guardia elige uno al azar y lo lleva a una sala con una bombilla (con interruptor de encendido/apagado).

El prisionero puede accionar el interruptor o no. Luego vuelve a su celda.

No saben cuándo volverán a ser elegidos. En cualquier momento, un prisionero puede declarar: 'Todos hemos estado en la sala al menos una vez'.

Si es cierto, todos quedan libres. Si es falso, todos mueren.

Al principio la bombilla está apagada. ¿Qué estrategia garantiza la libertad?

1. Protocolo: si alguna vez entra y ve la luz apagada por primera vez, la enciende.
2. Protocolo: cada vez que entra y ve la luz encendida, la apaga y suma 1.
3. Estrategia del contador único.

**Respuesta:** Estrategia del contador único.

{ width=700px align=center }

**Protocolo:**

1. Se designa un único **contador**.
2. Cada no-contador:

• si alguna vez entra y ve la luz apagada por primera vez, la enciende;
• después, no vuelve a tocarla nunca.

1. El contador:

• cada vez que entra y ve la luz encendida, la apaga y suma 1;
• al llegar a 99, declara que todos han pasado.

**Por qué es correcto:**

• Cada no-contador aporta a lo sumo un "token" (una encendida).
• El contador registra exactamente esos tokens al apagarlos.
• Contar 99 tokens implica que los otros 99 ya visitaron la sala.

La estrategia garantiza acierto, aunque el tiempo esperado puede ser muy alto bajo selección aleatoria.

---