Zurditorium

Después de bastante tiempo, hoy os vuelvo a traer la solución de uno de los problemas pendientes en el blog: Los 100 presos y los cascos de colores III. En realidad la solución aparece en los comentarios de dicha entrad, y si ya sabías resolver el problema los 100 presos y los cascos de colores I,  tampoco debería de ser muy difícil, pero quiero aprovechar hoy para poner la solución puesto que resulta que este mismo problema ha sido propuesto como el sexto desafío matemático de El País, cambiando el número de presos y para el que se podía mandar la solución hasta ayer (lo siento, no sería justo publicar la solución antes). Bueno, resumamos el enunciado:

Se les dice a 100 presos que al día siguiente se les va a colocar en una fila con un caso en la cabeza cada uno, que podrá ser azul o rojo. Cada preso podrá ver los cascos de los que tiene delante pero en ningún caso podrá volverse a ver los de detrás. Se le irá preguntando a cada preso, empezando por el último que puede ver a todos sus compañeros, el color de su casco. El preso que acierte será libre y el que no morirá ejecutado. Suponiendo que todos los presos tienen buena vista (así que el último podrá ver sin problemas el color de todos los cascos) y que tienen buen oído (para poder escuchar las respuestas dadas), ¿qué estrategia podrían planear para salvar seguro al mayor número posible?

Pues vamos con la solución. Antes de nada aclaro que los presos no pueden hacerse ningún tipo de señas de ninguna forma, solo pueden decir en su turno un color y en un tono neutro. Está claro que el primer preso no podrá estar seguro del color de su casco, ya que aunque pueda ver el color del casco de los demás, como no sabía cuántos hay de cada color, no le sirve de nada. Sin embargo su respuesta va a ser la clave para que TODOS los demás se salven. Es decir, con una buena estrategia se podrán salvar todos, salvo el primero que tendrá un 50% de posibilidades de salvarse. ¿Qué estrategia pueden seguir? Veámosla.

El primer preso en hablar dirá por ejemplo que su casco es rojo si ve un número par de cascos rojos y azul en caso contrario. Lo mismo se salva, lo mismo no, pero con esto le está dando información al resto de presos sobre lo que él ve.

Tras saber el segundo preso si el número de cascos rojos que ve el primer preso es par o impar lo tiene fácil. Si su casco es azul, verá los mismos cascos rojos que el primer preso y si su casco es rojo verá uno menos. Así que le basta con contar el número de cascos rojos y ver si salen pares o impares. Si la paridad es la misma que la del primer preso su casco será azul y en caso contrario será rojo.

Y así se irán salvando todos. Por ejemplo si llegamos al preso X y todos los presos anteriores se han salvado (salvo quizá el primero), este también podrá salvarse. ¿Cómo? El preso X sabe que los cascos rojos que ha visto el primer preso son los cascos rojos que él puede ver junto a los cascos rojos de los presos que había entre él y el primero (y este número lo conoce porque ha ido escuchando los presos que decían rojo) y quizá el suyo. Así que le basta con sumar los cascos rojos que ve al número de rojos que ha oído después de hablar el primer preso (el casco del primero no se cuenta) y si el número que obtiene tiene la misma paridad que la dicha por el primero, su casco es azul, en caso contrario será rojo.

Y con esta estrategia se librarían todos los prisioneros salvo quizá el primero.