El problema de los 100 presos

Hoy os traigo un problema que me ha propuesto el marsupial, un lector de Gaussianos, a través del correo del blog, gaussianos (arroba) gmail (punto) com.

Como se ha molestado en redactarlo convenientemente casi me siento en la obligación de respetar dicha redacción. Aquí os la dejo.

El problema de los 100 presos

A menudo, el proceso de resolución de un problema tiene poco que ver con la forma escrupulosamente estructurada en que suele presentarse la solución. Es más bien un batiburrillo de conjeturas (casi siempre incorrectas) y aventuradas propuestas:

¿Y si probamos tal cosa?…¡No, no!, subdivídelo en seis casos y dale la vuelta…¡pero esos seis casos se pueden reducir a dos!…¡vaya!, son incompatibles. ¿En qué nos hemos equivocado?…

Y así, cuando hay suerte, se van deduciendo las piezas del puzzle que una vez convenientemente dispuestas constituyen una flamante e impecable demostración.

Os presento a continuación un problema que, por lo que a mí respecta, es un perfecto ejemplo de lo anterior. Pocas veces me he sentido tan desarmado de entrada ante un problema. Por supuesto, no sentirse desarmado no significa que el problema vaya a ser fácil, significa más bien que por lo menos sabes (o crees que sabes) por dónde empezar. Muchas veces el planteamiento del problema porporciona claramente los elementos con los que hay que jugar…y luego hay que ponerse a trabajar con ellos. Pero en este caso lo cierto es que yo no vi muchas vías de ataque. Por ahora no digo más. El problema es el siguiente:

En una cárcel hay 100 presos condenados a muerte numerados del 1 al 100. El director de la cárcel les ofrece una última posibilidad de salvarse consistente en lo siguiente: coloca aleatoriamente cien papeles con cada uno de los números del 1 al 100 en cien cajones distintos (también numerados del 1 al 100) de su despacho, uno en cada cajón. Mientras tanto los presos están en sus celdas totalmente incomunicados con el mundo exterior y sin posibilidad de hablar entre ellos.

La prueba consiste en, para cada , seguir los pasos siguientes:

1. Llamar a su despacho al preso -ésimo,
2. dejarle abrir los 50 cajones que él quiera,
3. comprobar si alguno de los cajones abiertos contiene el número ,
4. volver a cerrar todos los cajones, y
5. devolver al preso a su celda sin dejarlo hablar con nadie.

Lo que propone el director es que si todos los presos abren el cajón con su propio número entonces todos se salvan, pero con sólo uno que falle todos mueren.

Una vez informados los presos de la propuesta del director, se les permite reunirse unos minutos antes de dar comienzo la prueba. Evidentemente, si todos los presos actúan al azar, la probabilidad que tienen de salvarse es un mísero , lo cual es casi como decir que están muertos antes de empezar. La pregunta que se hace en este problema es la siguiente:

¿Es posible acordar una estrategia que mejore estas funestas expectativas?

Os rogamos que, para mantener vivo el interés del problema, publiquéis solamente la probabilidad a la que vuestra estrategia conduce, pero no la estrategia explícita. Por ejemplo, si creéis que vuestra estrategia otorga a los presos probabilidad de salvarse, podéis publicar (junto con los comentarios que creáis conveniente, pero que no desvelen la estrategia usada).

Segunda contribución para la Edición 3.1 del Carnaval de Matemáticas, que en esta ocasión tiene como anfitrión a Scientia potentia est.