El martes pasado publicábamos en Gaussianos «el problema de los 100 presos, un interesante problema enviado por el marsupial a gaussianos (arroba) gmail (punto) com. De entrada el problema me pareció bastante interesante, y mi impresión se confirmó con vuestros comentarios, ya que el problema ha generado gran expectación. Bien, pues hoy publicamos su solución. De todas formas, si no viste el problema y quieres intentarlo te recomiendo que entres en la entrada donde aparece el problema y lo intentes. Los que quieran ver ya la solución que conitúen.
Recordemos de qué iba este problema. El enunciado era 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?
Bien, pues os dejo con la solución propuesta por el mismo el marsupial.
Solución al problema de los 100 presos
En primer lugar, vamos a codificar la información de la que disponemos en un lenguaje adecuado para razonar matemáticamente. Las constantes del problema son el número de presos (y cajones), , y la cantidad de cajones que cada preso puede abrir, 50. Por comodidad, llamaremos
, con lo que el número de presos será simplemente
.
Por otra parte, sabemos que hay escondidos en los cajones los números del
al
, uno en cada cajón. Esto no es más que el concepto matemático de permutación. Es decir, podemos pensar que tenemos los cajones también numerados del
al
y una aplicación biyectiva que a cada número (cajón) del
al
le hace corresponder un y sólo un número (papel) del
al
. Sea pues
, y consideraremos la permutación que a cada índice (cajón),
, le hace corresponder el número escondido en el cajón
-ésimo. En lo que sigue nos referiremos a esta permutación como la permutación (o disposición) inicial.
Si ahora hacemos que cada preso comience abriendo el cajón con índice igual al suyo (es decir, que el preso -ésimo empiece abriendo el cajón
-ésimo, para todo
) y después continúe la búsqueda abriendo sucesivamente los cajones indexados por el número escondido en el cajón anterior hasta tener
cajones abiertos, lo que cada preso estará haciendo es recorrer
pasos de un ciclo de la permutación inicial.
Entonces, si el preso encuentra su número durante los pasos, habrá completado el ciclo (que tendrá, por lo tanto, a lo sumo longitud
); y si no lo encuentra, el ciclo quedará incompleto después de
pasos (y por lo tanto tendrá una longitud estrictamente mayor que
).
Así, cada preso cumplirá con su parte si y sólo si el ciclo al que pertenece su índice consta de, como máximo, elementos. Dado que cada preso empieza por el cajón con su número, todos los cajones (y, por tanto, todos los ciclos) están involucrados.
En definitiva, procediendo según la estrategia propuesta, se conseguirá el reto colectivo si y sólo si todos los ciclos de la permutación inicial tienen longitud menor o igual que . O, lo que es equivalente (pero más rápido de calcular), si y solo si la permutación inicial no tiene ciclos de longitud mayor que
. Llamaremos
a este suceso::
{la permutación inicial no tiene ciclos de longitud
}
Veamos cuál es la probabilidad de . Observemos en primer lugar que el número de permutaciones de
elementos (como nuestra permutación inicial) con un ciclo de longitud
, es
![]()
(**¿Sabríais decir por qué?
)
Ahora, suponiendo equiprobables todas las disposiciones iniciales (eso es exactamente lo que entendemos por «el director coloca aleatoriamente los papeles en los cajones»), usando la fórmula de Laplace, tenemos que la probabilidad de que la permutación inicial tenga un ciclo de longitud es exactamente
(**De nuevo: ¿sabríais decir por qué? )
Y por último, como nos interesa considerar los ciclos de longitud estrictamente superior a
, es evidente que no se pueden dar dos en la misma permutación (**¿por qué?
). Es decir, los sucesos «tener un ciclo de longitud igual a
» son disjuntos dos a dos para
. De aquí ya es inmediato (**¿por qué?
) que la probabilidad de que la permutación inicial tenga algún ciclo de longitud estrictamente mayor que
(es decir, de longitudes entre
y
) es
Así pues, la probabilidad buscada, es
que para nos da
Es decir, sorprendentemente, con la estrategia indicada los presos pueden incrementar su esperanza de supervivencia de
a un
considerablemente más esperanzador.
Observemos que en el caso general es
donde es el
-ésimo número armónico,
.
Teniendo en cuenta que para suficientemente grande tenemos
, resulta que
para , tal y como bien se anticipaba en uno de los comentarios.
Una última cosa importante. Recientemente Eugene Curtin y Max Warshauer han publicado (Mathematical Intelligencer, 28(1):28-31, 2006) una demostración de que la estrategia que os he propuesto es óptima. No parece excesivamente difícil… ¿os atrevéis con ella?
Esperamos que os haya gustado la solución de el marsupial y os animamos a que intentéis resolver las cuestiones planteadas (veréis dos asteriscos, **, a su lado) en los comentarios. Gracias.
Esta es mi quinta 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á 😉
Información Bitacoras.com…
Valora en Bitacoras.com: El martes pasado publicábamos en Gaussianos “el problema de los 100 presos, un interesante problema enviado por el marsupial a gaussianos (arroba) gmail (punto) com. De entrada el problema me pareció bastante interesante,……
Una tontería… cambiemos el problema y supongamos que los presos acuerdan una estrategia, se la comunican al director y después éste decide cómo meter las papeletas en los cajones. ¿Hay alguna estrategia que sea mejor para los presos que abrir los cajones al azar?
Un par de cosas. Si no me equivoqué en la cuenta que hice ayer, no es solo que para n suficientemente grande la probabilidad se aproxime a 1-ln(2), sino que de hecho va a ser estrictamente mayor. Mi acotación la hice así. Comparando la integral de 1/x desde n+1 hasta 2n+1,conla suma Riemann inferior al dividir ese intervalo en n trozos iguales nos sale que la suma inferior (que es la suma de 1/k desde n+1 hasta 2n) es menor a la integral y por tanto: Y la otra cosa que quería comentar es que de primeras parece que el… Lee más »
Vaya, mi comentario no sale bien por culpa de que por usar símbolos parecidos a
parte del comentario lo toma el blog como una etiqueta html y no lo muestra. Indico aquí qué es lo que sale mal, que es la fórmula que aparece después de «es menor a la integral y por tanto:»
En vez d eso deberían de aparecer las 3 siguientes líneas:
Por tanto
Espero que ahora salga mejor aunque las desigualdades las haya puesto un poco raras 😀
No entendi ni pepa, pero encontre una explicacion mas didactica y de paso aprenden algo de permutaciones en –> http://www.uam.es/proyectosinv/estalmat/ReunionMadrid2009/la_magia_de_las_permutaciones.pdf
interesante para quien quedo sorprendido con el problema.
Entonces lo que tiene que hacer cada preso es:
El preso 1 abre el cajon 1 y segun el numero que le aparezca abre el cajon que corresponde (si le aparecio el 25 abre el cajon 25) asi lo hace hasta completar sus sus 50 cajones. Y asi con todos.
La posibilidad de que existan los numeros en ese ciclo es del 31%
zurditorium, respecto a la probabilidad de que el primer preso acierte:
si hay un ciclo de longitud 51, la probabilidad de acertar es 49/100 (es decir acierta si y solo si su numero no pertenece al ciclo)… y lo mismo para el resto de los casos. Verás que así sale un valor nada sorprendente.
Si, cierto, pensé que si su número estaba en el ciclo, en 50 casos de 51 lo encontraba, pero no, que hacer el ciclo completo. Estoy hoy espeso!!
«la probabilidad de que la permutación inicial tenga un ciclo de longitud es exactamente 1/k».
Esto es cierto para k>N, lo que en nuestro caso es suficiente, pero no cuando k<=N. Por ejemplo, para k=1 no vale 1/1 sino 1/(2N)!
Por supuesto mmonchi, en el cálculo solo interesan los ciclos de longitudes entre N+1 y 2N.
Aqui el paper, gato-docs.its.txstate.edu/mathworks/Locker_Puzzle.pdf
Por cierto mmonchi, la probabilidad para k=1 no puede ser la que has dicho, ya que obviamente hay mas de una permutacion que fija algun elemento. Es un problema bastante entretenido calcular esa probabilidad, te lo propongo como reto. Un saludo.
[…] Gaussianos vuelve a contribuir, esta vez con la solución al problema de los cien presos. […]
Llevas razón, interpretaba k como la longitud de la permutación más larga (que es lo que necesitaba para resolver el problema). En ese caso k sí vale lo que he dicho. Voy a ponerme con tu reto, no parece fácil.
Zurditorium… yo creo que en el caso de un preso, lo que te sale no es lógico. Te da un 84,4% de éxito para el primer preso con el método de reseguir ciclos. Pero intuitivamente… ¿qué más da el proceso que siga para elegir las cajas? Eligirá 50 cajas y su elección no será más prometedora que la del puro azar, siga la estrategia que siga, pues no tiene ninguna información sobre la colocación de los números en las cajas. Otra cosa será para los presos sucesivos. Está claro que si todos copiasen la misma elección de cajas que el… Lee más »
Muy bueno el problema. ¿Qué pasa si el preso 1 encuentra la siguiente secuencia: 1->2->3->2?
Gracias. Esa secuencia no es posible Fran, el papel numero 2 no puede estar en dos cajones.
(retomo el comentario anterior…)
Entonces hay que calcular cual es la posibilidad de que se formen esas cadenas de 50 eslabones o menos, porque hay tienen posibilidad de salvarse los presos. Y para calcular eso estan las formulas que se plantearon anteriormente.
se me perdio el primer comentario…. lo subo en un instante.
Lo único que me queda claro es que, salvo que haya algún matemático (o alguien que haya visto la solución al problema previamente) en el grupo, la probabilidad de que lleguen a dar con esta estrategia es mas pequeña que la misma probabilidad de salvarse si abren los cajones al azar (jaja esto ultimo es tal vez un poco exagerado)
reescribire el comentario anterior por haber apretado F5 por equivocacion snif…snif… @albert trataré de explicarlo sin utilizar mucha matematica y de la forma como lo entendí yo. Olvidemonos por un instante de los presos y centremonos en las 100 cajas y en los 100 papeles que hay en cada caja. Diremos que aunque estan colocadas al azar tienen un cierto orden fijo al que todos los presos van a acceder. Hagamos entonces el siguiente ejercicio. Digamos que yo abro la caja 1 y despues abro la caja que me indique el papel de la caja 1, si hago eso indefinidamente… Lee más »
[…] Gaussianos vuelve a contribuir, esta vez con la solución al problema de los cien presos. […]
El marsupial, la probabilidad que pides da un resultado muy curioso: la probabilidad de que haya algún ciclo de longitud 1 es 1-1/e. Por otro lado, la probabilidad de que al abrir una caja el número pertenezca a un ciclo de cualquier longitud es siempre la misma, 1/2N o en nuestro caso 1/100. Por ejemplo, la probabilidad de que haya un ciclo de longitud 3 es la de que en la primera caja no esté su número (99/100), en la segunda tampoco (98/99) pero en la tercera sí (1/98). El producto 99/100*98/99*1/98=1/100. Cualquier condenado al abrir tiene una probabilidad de… Lee más »
Muy interesante tanto el problema como la web.
Aquí de todos modos creo habría que corregir el enunciado, ya que dice:
«…en cajones distintos (también numerados del 1 al 100)…»
«..si todos los presos abren el cajón con su propio número entonces todos se salvan..»
Por lo tanto no está diciendo que cada preso debe abrir el cajón que contiene la papeleta con su número, sino el cajón con su propio número.
Solución alternativa: cuando se juntan todos, el preso número X se queda la papeleta del preso X+1, y así sucesivamente. El preso 1 abre 50 cajones, elige el cajón 2 y le da el cambiazo a la papeleta. El preso número X abre el cajón X y el X+1, y le da el cambiazo a la papeleta del X+1… y así sucesivamente.
Tu solución no la entendí bien. ¿Podrías dar un ejemplo completo? Además hay un detalle, los papeles están dentro de los cajones, no los tienen los presos.
Nadie quiere resolver las cuestiones en los **? Aparte de la 3, no se me ocurre ninguna.