Presos con sombrero

Enunciado

Se pueden salvar todos menos, eventualmente, el primero.

Una estrategia que pueden seguir es codificar la paridad, por ejemplo, de gorros blancos.

Imagina que el primero ve 25 gorros blancos, que es un número impar. No sabe de qué color es el suyo, así que no puede estar seguro de qué tiene que decir para salvarse. Como la cantidad de gorros blancos es impar y ha llegado a un acuerdo con sus compañeros, dice "negro".

El segundo, como ha oído "negro", sabe que el total de gorros blancos que ha visto el primero es impar, de forma que los cuenta y si ve una cantidad par, su gorro es blanco, y si es impar, su gorro es negro. Así que lo dice.

El tercero, sabe que, originalmente, la cantidad es impar (porque la primera información es que el color es negro, en caso contrario, sería par). Si el anterior a él ha dicho blanco, contando el suyo, debe quedar una cantidad par, y si ha dicho negro, impar. Estudiando la paridad de los que él ve, puede saber de qué color es el suyo. Negro, si la información que calcula coincide con la que ve, blanco en caso contrario.

En definitiva, la información que el primero trasmite es la paridad de la cantidad de blancos que él ve (negro es impar, blanco es par). Cada uno debe cambiar la paridad de par a impar cada vez que uno de los presos que habla dice "blanco", y contar los que ve. Si la paridad que él calcula coincide con la información que le trasmiten, su gorro es negro, y si no coincide es blanco.

Este sistema es muy dependiente de la información que se trasmita. Un único error en la cadena provoca que todos los siguientes mueran, y otro error, restaura el orden. En especial, dependen del primero, que no gana nada ni pierde en ningún caso.

No hay un sistema mejor, ya que no hay forma de que el primero pueda conocer el color de su gorro, así que tendrá un 50% de probabilidad de fallar, se siga la estrategia que se siga.