Solución al problema de los 100 presos

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 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?

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), 100, y la cantidad de cajones que cada preso puede abrir, 50. Por comodidad, llamaremos N=50, con lo que el número de presos será simplemente 2N.

Por otra parte, sabemos que hay escondidos en los 2N cajones los números del 1 al 2N, 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 1 al 100 y una aplicación biyectiva que a cada número (cajón) del 1 al 100 le hace corresponder un y sólo un número (papel) del 1 al 100. Sea pues N=50, y consideraremos la permutación que a cada índice (cajón), i \in \{ 1,\ldots ,2N \}, le hace corresponder el número escondido en el cajón i-é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 i-ésimo empiece abriendo el cajón i-ésimo, para todo i=1,\ldots ,2N) 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 N cajones abiertos, lo que cada preso estará haciendo es recorrer N pasos de un ciclo de la permutación inicial.

Entonces, si el preso encuentra su número durante los N pasos, habrá completado el ciclo (que tendrá, por lo tanto, a lo sumo longitud N); y si no lo encuentra, el ciclo quedará incompleto después de N pasos (y por lo tanto tendrá una longitud estrictamente mayor que N).

Así, cada preso cumplirá con su parte si y sólo si el ciclo al que pertenece su índice consta de, como máximo, N 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 N. 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 N. Llamaremos C_N a este suceso::

C_N := {la permutación inicial no tiene ciclos de longitud > N}

Veamos cuál es la probabilidad de C_N. Observemos en primer lugar que el número de permutaciones de 2N elementos (como nuestra permutación inicial) con un ciclo de longitud k, es

\binom{2N}{k}(k-1)!(2N-k)!=\cfrac{(2N)!}{k}

(**¿Sabríais decir por qué? ^\text{1})

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 k es exactamente 1 / k

(**De nuevo: ¿sabríais decir por qué? ^\text{2})

Y por último, como nos interesa considerar los ciclos de longitud k estrictamente superior a N, es evidente que no se pueden dar dos en la misma permutación (**¿por qué? ^\text{3}). Es decir, los sucesos “tener un ciclo de longitud igual a k” son disjuntos dos a dos para k > N. De aquí ya es inmediato (**¿por qué? ^\text{4}) que la probabilidad de que la permutación inicial tenga algún ciclo de longitud estrictamente mayor que N (es decir, de longitudes entre N+1 y 2N) es

\displaystyle{\sum_{k=N+1}^{2N} 1/k}

Así pues, la probabilidad buscada, es

p(C_N) = 1 - \displaystyle{\sum_{k=N+1}^{2N}1/k}

que para N=50 nos da

p(C_{50})=1-\displaystyle{\sum_{k=51}^{100} \cfrac{1}{k}= 1- \cfrac{1}{51} - \cfrac{1}{52} - \cdots - \cfrac{1}{100}=0.31183}

Es decir, sorprendentemente, con la estrategia indicada los presos pueden incrementar su esperanza de supervivencia de

2^{-100} \approx 7.8886 \ 10^{-31} = 0,00000000000000000000000000000078886

a un

0,31183

considerablemente más esperanzador.

Observemos que en el caso general es

P_{N}=1-\left( H_{2N}-H_{N}\right)

donde H_{n} es el n-ésimo número armónico, H_{n}=\displaystyle{\sum\nolimits_{k=1}^{n}1/k}.

Teniendo en cuenta que para n suficientemente grande tenemos H_{n}=\ln (n)+\gamma +O(1/n) , resulta que

P_{N}\approx 1-\left( \ln (2N)-\ln (N) \right) =1-\ln (2)=0.30685

para N \gg 1, 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.

Autor: gaussianos

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.

24 Comentarios

  1. 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?

    Publica una respuesta
  2. 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:

    \sum_{k=n+1}^{2n}\frac{1}{k}<ln(2n+1)-ln(n+1)=ln(\frac{2n+1}{n+1})1-ln(2)

    Y la otra cosa que quería comentar es que de primeras parece que el primer preso va a tener un 50% de posibilidades de encontrar su número independientemente de la estrategia que siga. Sin embargo, ¿pasa esto siguiendo esta estrategia? Pues si no me he equivocado en mis cuentas, resulta que la probabilidad de encontrar su papeleta es algo así como uno 84.4%, lo que sorprende bastante. Pongo los cálculos que he hecho.

    Por un lado la encontraría seguro si no hay ciclos de longitud mayor a 50. Si hay un ciclo de longitud 51 (cosa que pasa con una probabilidad 1/51) tiene 99/100 posibilidades de encontrar la papeleta, si es de longitud 52 (que pasa en 1/52) tiene 98/100,…, de longitud 50+k tiene (100-k)/100 de encontrarla y así. Por tanto la probabilidad de encontrar la papeleta sería:

    1-\sum_{k=51}^{100}\frac{1}{k}+\sum_{k=51}^{100}\frac{1}{k}\frac{150-k}{100}=1-\sum_{k=51}^{100}\frac{50-k}{100k}\simeq 0,844.

    Espero no haberme equivocado.

    Publica una respuesta
  3. Vaya, mi comentario no sale bien por culpa de que por usar símbolos parecidos a \prec\;\succ 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:

    \sum_{k=n+1}^{2n}\frac{1}{k}\prec ln(2n+1)-ln(n+1)=ln(\frac{2n+1}{n+1})\prec ln(2n/n)=ln2

    Por tanto

    1-\sum_{k=n+1}^{2n}\frac{1}{k}\succ 1-ln(2)

    Espero que ahora salga mejor aunque las desigualdades las haya puesto un poco raras 😀

    Publica una respuesta
  4. 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%

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. 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!!

    Publica una respuesta
  7. “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)!

    Publica una respuesta
  8. Por supuesto mmonchi, en el cálculo solo interesan los ciclos de longitudes entre N+1 y 2N.

    Publica una respuesta
  9. Aqui el paper, gato-docs.its.txstate.edu/mathworks/Locker_Puzzle.pdf

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. 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 primero, fracasarían. Por tanto yo pensé que lo que había que hacer era buscar que cada preso realizara una elección “lo más diferente posible” de todas las de sus compañeros.
    Por ejemplo que el primero coja las cajas 1 a 50, el segundo de 2 a 51, etc.
    No veo por qué ésta forma de proceder tiene que ser peor que la solución propuesta.
    Parece que los cálculos lo demuestran, ¿pero alguien me lo puede explicar de una forma argumental? No acabo de captar la idea. Los cálculos no me dejan ver el bosque.

    Publica una respuesta
  13. Muy bueno el problema. ¿Qué pasa si el preso 1 encuentra la siguiente secuencia: 1->2->3->2?

    Publica una respuesta
  14. Gracias. Esa secuencia no es posible Fran, el papel numero 2 no puede estar en dos cajones.

    Publica una respuesta
  15. (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.

    Publica una respuesta
  16. 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)

    Publica una respuesta
  17. 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 se comenzará a crear una cadena que concluira cuando abra la caja que contenga un papel que haga referencia a la caja 1 y como esa ya esta abierta se cerrara la cadena. (¿me sigues?)

    Al distribuir los papeles en esas cajas se han creado cadenas, algunas con varios eslabones y otras con pocos. Por ejemplo podrian haberse creado las siguientes cadenas:

    1>4>6>87>65>45>90>100>2>1

    3>7>3

    34>94>23>32>56>55>8>34

    ¿Notas que un eslabon no puede estar en dos cadenas a la vez? Eso es imposible porque dos papeletas no pueden indicar a una misma caja.

    Ahora pensemos en los presos, si el preso 1 abre la caja 1 comenzará a recorrer una cadena que invariablemente terminará en su numero ¿Entonces todos se salvan? pues no, porque el solo tiene 50 cajas para abrir ¿Y si la cadena tiene 51 eslabones o mas? Ahí esta con un serio problema.

    Entonces la probabilidad que buscamos no es en definitiva la posibilidad de que los presos saquen su numero, sino que la probabilidad de que la forma en que se colocaron los papeles en las cajas generen cadenas de 50 eslabones o menos que es ciertamente la forma en que los presos se salvarian. Y para calcular eso estan las formulas que se plantearon anteriormente.

    Creo que lo he explicado bien, ahora si he orinado fuera del recipiente corrijanme por favor

    Publica una respuesta
  18. 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 salvarse de 50/100 abriendo cajas al azar y de 50*1/100 con el método descrito; lógicamente es la misma. Lo que consigue el método es mejorar la probabilidad conjunta, no las individuales.

    Respondiendo la primera pregunta, hay (2N)! permutaciones de 2N elementos, de modo que se puede abrir una caja en 2N*(2N)! casos diferentes (cada caja de cada permutación); como la probabilidad de encontrar una caja perteneciente a un ciclo de longitud k es 1/2N, la encontraremos en 2N*(2N)!/2N casos, es decir (2N)!; pero como esos (2N)! casos corresponden a ciclos de longitud k, el número de ciclos será (2N)!/k.

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. 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.

    Publica una respuesta
  21. 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.

    Publica una respuesta
  22. Nadie quiere resolver las cuestiones en los **? Aparte de la 3, no se me ocurre ninguna.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: El martes pasado publicábamos en Gaussianos “el problema de los 100 presos, un interesante…
  2. Resumen del Carnaval de Matemáticas Edición 3.1 (actualizándose) | Scientia potentia est - [...] Gaussianos vuelve a contribuir, esta vez con la solución al problema de los cien presos. [...]
  3. ¡A votar! (Carnaval de Matemáticas 3.1) | Scientia potentia est - [...] Gaussianos vuelve a contribuir, esta vez con la solución al problema de los cien presos. [...]

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 *