Es un problema de disciplina colectiva bajo una restricción feroz: una sola palabra por persona y casi ninguna segunda oportunidad. La belleza aparece cuando el grupo deja de intentar salvarse uno a uno y empieza a pensar como conjunto.
Los cien prisioneros con sombreros
Enunciado
Hay 100 prisioneros en fila. A cada uno le colocan al azar un sombrero rojo o azul.
Cada prisionero puede ver los sombreros de todos los que están delante, pero no el suyo ni los que quedan detrás. Empezando por el último de la fila y siguiendo hacia delante, cada uno debe decir en voz alta una sola palabra: “rojo” o “azul”. No pueden decir nada más.
Si alguien acierta el color de su sombrero, sobrevive; si falla, muere.
Antes de empezar pueden acordar una estrategia.
¿Cuál es la mejor estrategia posible y cuántas vidas garantiza?
Ver solución
Solución
Respuesta: pueden garantizar que sobrevivan 99 prisioneros, y esa garantía es óptima.
Antes de empezar acuerdan interpretar las palabras «rojo» y «azul» también como un código de paridad.
El último prisionero de la fila —que es el primero en hablar— cuenta los sombreros rojos que ve delante:
- dice «rojo» si la cantidad es impar;
- dice «azul» si la cantidad es par.
No está intentando salvarse a sí mismo. Como no puede ver su propio sombrero, utiliza su respuesta para transmitir un bit de información global al resto.
A partir de ahí, cada prisionero conoce:
- la paridad anunciada al principio;
- los sombreros que todavía ve delante;
- los colores que ya han deducido y pronunciado quienes hablaron antes.
Comparando esos datos puede determinar con certeza el color de su propio sombrero. Después, su respuesta proporciona también la información necesaria para que continúe el proceso.
Así, los 99 prisioneros que hablan después del primero aciertan con seguridad.
¿Por qué no puede garantizarse la supervivencia de los 100?
Fijemos los 99 sombreros que ve el primer prisionero. Consideremos ahora dos situaciones idénticas salvo por su propio sombrero: en una es rojo y en la otra es azul.
El primer prisionero ve exactamente lo mismo en ambas situaciones y, por tanto, cualquier estrategia le obliga a pronunciar la misma palabra en las dos. Esa respuesta será incorrecta en una de ellas.
Por tanto, ningún método puede garantizar que el primero acierte siempre.
Conclusión: 99 supervivientes es la mejor garantía posible.