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 i=1, \ldots , 100, seguir los pasos siguientes:

  1. Llamar a su despacho al preso i-ésimo,
  2. dejarle abrir los 50 cajones que él quiera,
  3. comprobar si alguno de los cajones abiertos contiene el número i,
  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 2^{-100}, 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 1/100 de salvarse, podéis publicar 0.01 (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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

51 Comentarios

  1. Se puede mejorar, aunque mi primera idea no parece demasiado brillante: consigo una probabilidad de 9,91165E-30 que aunque mejora doce veces y media al puro azar, sigue siendo demasiado baja…

    Publica una respuesta
  2. Una hermosa cualidad de las matemáticas es que permite plantear casos como el presente incompatibles con el normal comportamiento humano. Claro que hay estrategia para aumentar la probabilidad, pero, tal como se plantea, encuentro tan desmesurada la amenaza de muerte que, en la práctica, no se llegaría a poner en práctica salvo en el caso de que se salvaran todos. En cuanto un preso no encontrara su número en los cajones que abre no tendría el menor interés en cumplir la estrategia acordada por su esterilidad. Es más, para la dirección de la cárcel ya no tendría sentido continuar con el proceso, ya que ya conocía el final del experimento.
    Para darle más viabilidad yo propondría un castigo tolerable, por ejemplo, “se salvan si el número de fallidos es n o menos”. Cualquier n, por encima de 1 abre la puerta a la esperanza.
    Yo he conseguido, de momento, una estrategia que aumenta la probabilidad hasta algo más de 0,0000003.

    Publica una respuesta
  3. Con una estrategia sencilla se hace evidente conseguir 2^{-99} … pero yo diría que hay alguna muuucho mejor.

    Publica una respuesta
  4. Revisando mis cálculos veo que he sido algo optimista. con mi estrategia actual la probabilidad que consigo es de 0,000000153…

    Publica una respuesta
  5. JJGJJG, la dirección de la cárdel es como las matematicas… no tiene piedad. 😉

    Publica una respuesta
  6. ufffff, perdónnnn aguilui, lo consideramos empate si es correcto 🙂

    Publica una respuesta
  7. os doy las gracias por hacerme repasar …. probabilidad de 0.311827821

    Publica una respuesta
  8. 1/4

    [intuyo que lo más improbable es que haya un matemático condenado a muerte (: ]

    Publica una respuesta
  9. Increíble pero cierto: se puede conseguir una probabilidad de 0.31182782068980479676…, como ya algunos han apuntado antes. Lo que no sé cómo hacer es probar que no se puede mejorar esta cota.

    Publica una respuesta
  10. ¡Sorprendente! 31,18278206898%

    Con infinitos presos la probabilidad sería 1-ln2.

    Publica una respuesta
  11. gracias por enviar vuestras propuestas a elmarsupialextinto@gmail.com. Por ahora la probabilidad más alta recibida (aunque aun no comprobada) es 45.2%. ¿es tal probabilidad posible? ¿podeis mejorarla?

    Nota: por supuesto los presos no pueden manipular las papeletas… como tampoco pueden robarle las 100 llaves al director. 😉

    Publica una respuesta
  12. Lo he leído unas cuantas veces, y resulta que he encontrado una “trampa” en el enunciado. Con esta trampa se pueden librar el 100% de los presos! jaja
    Pero me gustaría saber cómo han calculado en los posts anteriores 🙂

    Publica una respuesta
  13. Pues lo más que la mejoro yo es 9.5×10^-74…..Ya veré si hay algo mejor…

    Publica una respuesta
  14. Otra cosa: no me creo probabilidades mayores al 50% porque es la probabilidad que el primer preso tiene de atinar……

    Publica una respuesta
  15. Ya me lo pille es casi del 50%(hay que hacer una trampita pero en el enunciado nadie dice que no puede hacerse)….

    Publica una respuesta
  16. Hola chicos, no le busqueis gazapos al enunciado. No hay ninguna trampa, solo mates!.

    Publica una respuesta
  17. Aquí uno que tiene mucha curiosidad porque se publiquen razonamientos ¿Cuánto hay que esperar?

    Publica una respuesta
  18. Yo también llego a algo más del 31%. La verdad es que es la única estrategia que se me ha ocurrido. Estaría bien ver algunas de las más interesantes.

    Publica una respuesta
  19. ¿Alguien puede dar alguna indicación? Lo digo porque por mucho que piense, si no hay posible flujo de información entre los presos, cada preso tiene un 50% de acertar.
    Asumiendo que todos mueren tan pronto como uno falle se podría pensar en un sistema para seleccionar cajones para cada preso, pero así lo único que se sabe es que en los 50 seleccionados está el número n-1, pero no sé para qué le sirve esa información al preso n.
    En definitiva, me parece ciencia-ficción probabilidades tan altas.

    Publica una respuesta
  20. Soñe que 100 presos muertos me perseguian porque no fue capaz de salvarlos -_-

    Lo de las trampillas del enunciado ya lo hecharon por tierra, asi que no vale eso de marcar las cajas y demases. Se que debe haber una solucion matematica y al igual que @Korudo77 pienso que el primer preso es el mas la tiene dificil porque si o si tiene 1/2 de acertar.

    Entonces, sin saber de matematicas puedo conjeturar que la interpretacion de lo que haga el primer preso es la clave de ejercicio, mas solo es una conjetura.

    Publica una respuesta
  21. Tal y como dices, no pueden intercambiar información una vez comenzada la prueba.
    Aunque en principio las probabilidades individuales son del 50% para cada uno, hay algo que es constante para todos ellos y esto es la colocación de los números en los cajones, que no cambia durante la prueba.
    Esto puede tenerse en cuenta para diseñar una estrategia de elección para cada preso de manera que al probabilidad de que todos acierten sea bastante mayor que
     2^{-100}

    Por dar una pista… tiene algo que ver con algo que a los programadores de C los trae de cabeza y a los de Java no…

    Publica una respuesta
  22. @Ivan, no sólo el primer preso, para que todo funcione todos tienen que seguir una estrategia común (con que uno se la salte se va todo al garete).

    Publica una respuesta
  23. Creo que ya sé cuál es la estrategia que deben seguir, pero no sé la probabilidad que obtienen… lo trato de calcular…

    Publica una respuesta
  24. Según el enunciado primero se abren todos los cajones y después se mira…

    Publica una respuesta
  25. No lo he pensado demasiado pero bueno, una indicación para los que no ven que se pueden seguir estrategias, una muy sencilla:

    Se dice que cada preso tiene 1/2 de posibilidades y por tanto sin estrategia la probabilidad sería 2^{-100}.

    Una estrategia (que desde luego no va a ser la óptima). Que los 50 primeros presos elijan las 50 primeras cajas y los 50 siguientes las otras 50.

    Probabilidad de que acierten los 50 primeros: 2^{-50}. Si los 50 primeros aciertan los 50 siguientes automáticamente aciertan así que la probabilidad de que acierten todos sería 2^{-50} con dicha estrategia.

    2^{-50} es un número muy pequeño, pero es más de 1000 billones (europeos) de veces más grandes que el 2^{-100} inicial (billinoes europeos, quintillones americanos o algo así).

    Vamos, que se puede mejorar con una estrategia muchísimo el puro azar. ¿Se puede mejorar tanto como dicen más arriba? Pues supongo que sí porque coinciden muchas respuestas, lo cierto es que estoy intrigado, así de primeras no se me ocurre ninguna estrategia que sea tan buena.

    Publica una respuesta
  26. Ups, en mi comentario anterior, me he equivocado, la probabilidad con la estrategia que digo es mucho mayor ya que la probabilidad del primero sería 1/2, pero la del segundo sería 50/99 suponiendo que el primero acierta, del tercero 50/98 y así, vamos, que quedaría

    \frac{50^50\cdot 50!}{100!}

    que no me apetece ver ahora cuanto de grande es, pero vamos, es un número muy pequeño pero aún así mucho más grande que el inicial (y más grande que lo que he dicho en mi comentario anterior).

    Publica una respuesta
  27. Esa probabilidad de 50!*50!/100! equivale a 9.91165302e-30. No es una buena estrategia.

    Publica una respuesta
  28. @Mmonchi, sí, es esa, luego me di cuenta.

    @Aupa, sé que no es una buena estrategia, era para ilustrar que se puede mejorar el simple azar.

    En cualquier caso lo confirmo, se puede alcanzar algo como 0.3118… como ya han puesto muchos y además, no se puede mejorar (así que los que ponen 0.4 y mayores en algo se han equivocado).

    Publica una respuesta
  29. Siendo muy generoso en la estimación, y con un argumento para revisar, no paso por ahora de del 2.083 %.

    Publica una respuesta
  30. una pista para los que andais tras el 0.3118… . Intentad utilizar los ciclos de la permutación.

    Publica una respuesta
  31. Venga que ya la tengo, despues de leer un paper que explicaba la magia de las permutaciones y realizar ejercicios y ejercios se porque es 0.311827821

    Nota: No puedo darme el credito de haberla descubierto yo mismo, pero aprendi mucha matematica hoy

    Publica una respuesta
  32. Teniendo en cuenta que para el primer preso la probabilidad es de 50%, me maravilla que con 99 personas más sólo baje hasta 31%. No soy capaz de imaginar cómo se logra una probabilidad tan alta.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Hoy os traigo un problema que me ha propuesto el marsupial, un lector de…
  2. Resumen del Carnaval de Matemáticas Edición 3.1 (actualizándose) | Scientia potentia est - [...] Gaussianos nos dejan un reto! Un problema de cálculo de probabilidades muy [...]
  3. Solución al problema de los 100 presos - Gaussianos | Gaussianos - [...] El problema de los 100 presos (16) [...]
  4. ¡A votar! (Carnaval de Matemáticas 3.1) | Scientia potentia est - [...] Gaussianos nos dejan un reto! Un problema de cálculo de probabilidades muy [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *