C¨®mo salvar seguro a 29 presos

Ya hay ganador del sexto desaf¨ªo que organiza EL PA¨ªS en el primer centenario de la Real Sociedad Matem¨¢tica Espa?ola. Esta semana, el ganador de una biblioteca matem¨¢tica como la que se ofrece el domingo con EL PA?S ha sido Mariano Madrid Mataran, inform¨¢tico que trabaja en Las Rozas (Madrid). En esta ocasi¨®n se recibieron 1.700 respuestas dentro del plazo previsto, pero s¨®lo el 25% daba la soluci¨®n correcta. Este domingo, el libro que se entrega con EL PA?S, a un precio de 9,95 euros, es La cuarta dimensi¨®n, de Ra¨²l Ib¨¢?ez.

Vayamos con la soluci¨®n al problema que nos planteaba Javier L¨¢zaro, estudiante de 4? de matem¨¢ticas de la Universidad de Zaragoza (ver planteamiento en el v¨ªdeo de la izquierda y la soluci¨®n en el de la derecha). Recordemos el enunciado. Se informa a 30 presos de que se les va a colocar formando una fila y se les va a poner un sombrero en la cabeza a cada uno, blanco o negro, sin especificar cu¨¢ntos gorros se pondr¨¢n de cada color. Cada preso s¨®lo ver¨¢ los sombreros de los prisioneros que tiene delante pero no el suyo ni los de detr¨¢s. Un guardia ir¨¢ preguntando sucesivamente a cada uno de los presos desde el ¨²ltimo (el que ve todos pero no el suyo) al primero (que no ve ninguno) de qu¨¦ color es su sombrero. Los presos s¨®lo pueden contestar blanco o negro: si aciertan son liberados y si no, son ejecutados. Todos los presos pueden escuchar las respuestas anteriores a las suyas.

Antes de llevar esto a cabo, los presos, que conocen la prueba a la que van a ser sometidos pero no naturalmente de qu¨¦ color ser¨¢n sus sombreros, tienen un tiempo para hablar entre ellos y pensar una estrategia de grupo. No vale hacer inflexiones de voz, ni cambiar el tono o el volumen en la respuesta: deben responder sin m¨¢s blanco o negro ?Cu¨¢l es la mejor estrategia para salvar SEGURO al mayor n¨²mero de prisioneros? ?Cu¨¢ntos se salvan seguro con esa estrategia?

Hay una estrategia para salvar seguro a 29 presos. El primer preso al que pregunten, el que ve todos los sombreros menos el suyo, debe contar cuantos sobreros blancos hay (tambi¨¦n podr¨ªa hacerse con los sombreros negros, es indiferente). Si hay un n¨²mero par de sombreros blancos contestar¨¢ blanco (ser¨ªa como si contestase par). Y si hay un n¨²mero impar de sombreros blancos contestar¨¢negro (ser¨ªa como si contestase impar). Como ¨¦l ha contestado en funci¨®n de los sombreros que ha visto sin poder ver el suyo y sin ninguna pista las probabilidades de que se salve son del 50%.

El siguiente preso al que le pregunten contar¨¢ de nuevo el n¨²mero de sombreros blancos. Si ve un n¨²mero par de sombreros blancos y el anterior preso dijo blanco (par) quiere decir que su sombrero es negro as¨ª que diciendo negro se salvar¨¢; sin embargo si ve un n¨²mero par y el anterior dijo negro (impar) entonces su sombrero es blanco, diciendo blanco se salvar¨¢. De igual forma debe actuar si al contar los sombreros que ve este segundo preso hay un n¨²mero impar de sombreros blancos. En este caso deber¨¢ decir negro si el anterior dijo negro (impar) y deber¨¢ decir blanco si el anterior dijo blanco (par).

El resto de presos deber¨¢ actuar de forma equivalente, sabiendo gracias a la respuesta del primer preso si el n¨²mero de sombreros blancos es par o impar y teniendo en cuenta el color de los sombreros de los presos que les preceden (que aunque no los vean lo saben porque oyen las respuestas siempre acertadas de los presos anteriores). De esta forma 29 presos se salvar¨¢n seguro y uno (el primero que habla) tiene un 50% de probabilidades de salvarse.

Otros lectores se han acercado a la soluci¨®n con razonamientos correctos pero sin llegar a salvar a 29 (luego las respuestas no son v¨¢lidas). Por ejemplo, quienes han propuesto que los primeros presos codifiquen en binario el n¨²mero de sombreros de cada color que llevan los restantes. La versi¨®n m¨¢s sencilla propone que los 5 primeros presos en hablar codifiquen en binario el n¨²mero de sombreros blancos que ven entre los otros 25. Digamos que blanco=0 y negro =1. As¨ª, si dicen, de atr¨¢s hacia adelante, BBNBN, por ejemplo, el n¨²mero binario ser¨ªa 10100, que representa el 20. Sabiendo que hay entre ellos 20 sombreros blancos los 25 presos restantes pueden salvarse. Algunos lectores han afinado m¨¢s el razonamiento, permitiendo salvar seguro a 26 presos: los 4 primeros presos codifica en binario el color menos frecuente entre los 26 restantes (no pasa nada si hay 13 blancos y 13 negros).

La respuesta m¨¢s com¨²n ha sido que se salvan seguro 15 presos (y el resto al 50%), diciendo, por ejemplo, los presos 1, 3, 5,... el color del sombrero del 2, 4, 6,... respectivamente. As¨ª se salvan todos los presos en posici¨®n par y el razonamiento es correcto, aunque se queda corto. Una paso m¨¢s all¨¢ lo han dado quienes han conseguido salvar a 20 presos agrup¨¢ndolos de 3 en 3. En cada grupo el primero en hablar dice blanco si los otros dos sombreros son del mismo color y negro si son distintos, lo que permite salvarse a sus dos compa?eros.

El razonamiento que no es correcto es el de quienes han propuesto que cada preso diga el color del sombrero que tiene delante, y concluyen que se salvar¨ªan 29. Con este procedimiento podr¨ªa salvarse s¨®lo el primer preso si, por ejemplo, los colores se alternan: BNBNBN...

Algunos lectores nos han reprochado que el enunciado del problema era excesivamente macabro. As¨ª que para quitar hierro a un problema tan truculento hemos decidido destacar la respuesta de Luis J. Fern¨¢ndez de las Heras, que se declara contrario a la pena de muerte y que seg¨²n sus propias palabras, no ha parado hasta salvar a los 30 presos. Y as¨ª, tras dar la respuesta correcta, a?ade esta coletilla:

"Pero resulta que el suministrador de los sombreros, como buen sombrerero loco de Lewis Caroll, era aficionado a las matem¨¢ticas, y no se resisti¨® a conocer las discusiones entre los presos. En secreto, escuch¨® cu¨¢l era el plan de los presos para salvarse [en su soluci¨®n el primer preso en hablar deb¨ªa decir blanco si ve¨ªa un n¨²mero impar de sombreros]. Ni que decir tiene que el sombrerero, como buen matem¨¢tico contrario a la pena de muerte, suministr¨® a los verdugos un n¨²mero par de sombreros blancos y s¨®lo 30 sombreros en total. Conseguido el final feliz. Los 30 presos salvados".

El pr¨®ximo jueves platearemos un nuevo desaf¨ªo.

As¨ª se salvan 29 presos

Una cuesti¨®n de sombreros