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:
- Llamar a su despacho al preso
-ésimo,
- dejarle abrir los 50 cajones que él quiera,
- comprobar si alguno de los cajones abiertos contiene el número
,
- volver a cerrar todos los cajones, y
- 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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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…
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… Lee más »
Con una estrategia sencilla se hace evidente conseguir
… pero yo diría que hay alguna muuucho mejor.
Revisando mis cálculos veo que he sido algo optimista. con mi estrategia actual la probabilidad que consigo es de 0,000000153…
Interesantes progresos, os invito a explicarme vuestras estrategias en
elmarsupialextinto@gmail.com
…pero se puede mejorar.
@el_marsupial
JJGJJG, la dirección de la cárdel es como las matematicas… no tiene piedad. 😉
Información Bitacoras.com…
Valora en Bitacoras.com: 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 ……
Las posibilidades de que se salven todos es 1/4 = 0.25
1/4
Me has ganado por 1 minuto @Car_CG 🙁
ufffff, perdónnnn aguilui, lo consideramos empate si es correcto 🙂
caramba! 1/4, eso ya es increiblemente alto… (habrá que comprobarlo) por favor, enviadme vuestras estrategias a
elmarsupialextinto@gmail.com
@el_marsupial
os doy las gracias por hacerme repasar …. probabilidad de 0.311827821
0.3118…. aquí también
Subo a 0,495
Mi probabilidad actual es de 0.00000000289448 pero mejorara
Si, ya mejoro, es 1/4 habia que pensar un poco y ya esta.
1/4
[intuyo que lo más improbable es que haya un matemático condenado a muerte (: ]
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.
Mi probabilidad esde 45.2%
¡Sorprendente! 31,18278206898%
Con infinitos presos la probabilidad sería 1-ln2.
45,2%? Wauuu, ya quiero saber como lo han conseguido
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. 😉
Hechaste por tierra mi preciado 25%. Vuelta a pensar, pensar y pensar…
[…] Gaussianos nos dejan un reto! Un problema de cálculo de probabilidades muy […]
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 🙂
Pues lo más que la mejoro yo es 9.5×10^-74…..Ya veré si hay algo mejor…
Otra cosa: no me creo probabilidades mayores al 50% porque es la probabilidad que el primer preso tiene de atinar……
Ya me lo pille es casi del 50%(hay que hacer una trampita pero en el enunciado nadie dice que no puede hacerse)….
Hola chicos, no le busqueis gazapos al enunciado. No hay ninguna trampa, solo mates!.
Aquí uno que tiene mucha curiosidad porque se publiquen razonamientos ¿Cuánto hay que esperar?
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.
¿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.
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.
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 Por dar una pista… tiene algo que ver con algo que a los programadores de C los trae de cabeza y a los… Lee más »
@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).
Tranquilos, pronto publicaré la solución 🙂
http://www.springerlink.com/content/c1107q6614555085/
Interesante, es el mismo problema.
Creo que ya sé cuál es la estrategia que deben seguir, pero no sé la probabilidad que obtienen… lo trato de calcular…
Según el enunciado primero se abren todos los cajones y después se mira…
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 . 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: . Si los 50 primeros aciertan los 50 siguientes automáticamente aciertan así que la probabilidad de que acierten todos sería con dicha estrategia. es un… Lee más »
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
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).
Zurditorium, creo que es 50!*50!/100!
Esa probabilidad de 50!*50!/100! equivale a 9.91165302e-30. No es una buena estrategia.
@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).
Pensanding en como conseguir ese treinta y fraccion%
Siendo muy generoso en la estimación, y con un argumento para revisar, no paso por ahora de del 2.083 %.
una pista para los que andais tras el 0.3118… . Intentad utilizar los ciclos de la permutación.
Wau, se me abrio todo un mundo de informacion. Gracias @elmarsupial