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.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉