Problema de los 100 prisioneros

Sorprendentemente, existe una estrategia que garantiza la supervivencia de todos los prisioneros con una probabilidad superior al 30%. La clave del éxito reside en que los prisioneros no tienen que decidir de antemano qué cajones abrir. Cada prisionero puede utilizar la información obtenida del contenido de los cajones ya abiertos para decidir cuál abrir a continuación. Otra observación importante es que, de esta forma, el éxito de un prisionero no es independiente del éxito de los demás, ya que todos dependen de la distribución numérica. ^{[ 2 ]}

Para describir la estrategia, no solo los prisioneros, sino también los cajones, están numerados del 1 al 100; por ejemplo, fila por fila comenzando con el cajón superior izquierdo. La estrategia es ahora la siguiente: ^{[ 3 ]}

1. Cada prisionero abre primero el cajón que lleva su propio número.
2. Si este cajón contiene su número, han terminado y han tenido éxito.
3. De lo contrario, el cajón contiene el número de otro prisionero, y a continuación abren el cajón etiquetado con ese número.
4. El prisionero repite los pasos 2 y 3 hasta que encuentra su propio número, o fracasa porque el número no se encuentra en los primeros cincuenta cajones abiertos.

Si el prisionero pudiera continuar indefinidamente de esta manera, inevitablemente volvería al cajón con el que empezó, formando un ciclo de permutación (véase más abajo ). Al comenzar con su propio número, el prisionero se asegura de estar en el ciclo específico de cajones que contiene su número. La única pregunta es si algún ciclo es más largo que cincuenta cajones; y solo un ciclo puede ser demasiado largo, ya que como máximo uno puede abarcar más de la mitad del total de cajones.

La razón por la que esta es una estrategia prometedora se ilustra con el siguiente ejemplo, que utiliza 8 prisioneros y cajones, donde cada prisionero puede abrir 4 cajones. El director de la prisión ha distribuido los números de los prisioneros en los cajones de la siguiente manera:

Los prisioneros actúan ahora de la siguiente manera:

• El prisionero 1 primero abre el cajón 1 y encuentra el número 7. Luego abre el cajón 7 y encuentra el número 5. Luego abre el cajón 5, donde encuentra su propio número y tiene éxito.
• El prisionero 2 abre los cajones 2, 4 y 8 en este orden. En el último cajón encuentra su propio número, el 2.
• El prisionero número 3 abre los cajones 3 y 6, donde encuentra su propio número.
• El prisionero 4 abre los cajones 4, 8 y 2, donde encuentra su propio número. Este es el mismo ciclo que experimentó el prisionero 2 y que experimentará el prisionero 8. Cada uno de estos prisioneros encontrará su propio número en el tercer cajón abierto.
• Los presos del 5 al 7 también encontrarán sus números de forma similar.

En este caso, todos los prisioneros encuentran sus números. Sin embargo, esto no siempre es así. Por ejemplo, el pequeño cambio en los números de los cajones 5 y 8 al intercambiarlos provocaría que el prisionero 1 fallara después de abrir los cajones 1, 7, 5 y 2 (y no encontrar su propio número):

Y en la siguiente disposición, el prisionero 1 abre los cajones 1, 3, 7 y 4, momento en el que debe detenerse sin éxito:

En efecto, todos los prisioneros, excepto 6 (que tiene éxito directamente), fracasan.

Representaciones gráficas de las permutaciones (1  7  5)(2  4  8)(3  6) y (1  3  7  4  5  8  2)(6)

La asignación de números de prisioneros a los cajones por parte del director de la prisión se puede describir matemáticamente como una permutación de los números enteros del 1 al 100. Una secuencia de números que, tras la aplicación repetida de la permutación, vuelve al primer número se denomina ciclo de la permutación. Toda permutación se puede descomponer en ciclos disjuntos , es decir, ciclos que no tienen elementos comunes. La permutación del primer ejemplo anterior se puede escribir en notación de ciclo como

${\displaystyle (1~7~5)(2~4~8)(3~6)}$

y, por lo tanto, consta de dos ciclos de longitud 3 y un ciclo de longitud 2. La permutación del tercer ejemplo es, en consecuencia,

${\displaystyle (1~3~7~4~5~8~2)(6)}$

y consta de un ciclo de longitud 7 y un ciclo de longitud 1. La notación de ciclo no es única ya que un ciclo de longitud${\displaystyle l}$se puede escribir en${\displaystyle l}$Existen diferentes maneras según el número inicial del ciclo. Al abrir los cajones con la estrategia anterior, cada prisionero sigue un único ciclo que siempre termina con su propio número. En el caso de ocho prisioneros, esta estrategia de seguimiento de ciclos tiene éxito si y solo si la longitud del ciclo más largo de la permutación es como máximo 4. Si una permutación contiene un ciclo de longitud 5 o más, ningún prisionero cuyos números se encuentren en dicho ciclo alcanzará su propio número en cuatro pasos.

En el problema inicial, los 100 prisioneros tienen éxito si el ciclo más largo de la permutación tiene una longitud máxima de 50. Por lo tanto, su probabilidad de supervivencia es igual a la probabilidad de que una permutación aleatoria de los números del 1 al 100 no contenga ningún ciclo de longitud mayor que 50. Esta probabilidad se determina a continuación.

Una permutación de los números del 1 al 100 puede contener como máximo un ciclo de longitud${\displaystyle l>50}$. Hay exactamente${\displaystyle {\tbinom {100}{l}}}$formas de seleccionar los números de dicho ciclo (ver combinación ). Dentro de este ciclo, estos números se pueden organizar en${\displaystyle (l-1)!}$formas ya que hay${\displaystyle l}$permutaciones para representar ciclos distintos de longitud${\displaystyle l}$debido a la simetría cíclica. Los números restantes se pueden ordenar en${\displaystyle (100-l)!}$formas. Por lo tanto, el número de permutaciones de los números del 1 al 100 con un ciclo de longitud${\displaystyle l>50}$es igual a

${\displaystyle {\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}.}$

La probabilidad de que una permutación aleatoria ( distribuida uniformemente ) no contenga ningún ciclo de longitud mayor que 50 se calcula con la fórmula para eventos simples y la fórmula para eventos complementarios dada por

${\displaystyle 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0.31183,}$

dónde${\displaystyle H_{n}}$es el${\displaystyle n}$-ésimo número armónico . Por lo tanto, utilizando la estrategia de seguimiento de ciclos, los prisioneros sobreviven en un sorprendente 31% de los casos. ^{[ 3 ]}

Si${\displaystyle 2n}$en lugar de considerar 100 prisioneros, donde${\displaystyle n}$es un número natural arbitrario, la probabilidad de supervivencia de los prisioneros con la estrategia de seguimiento de ciclos viene dada por

${\displaystyle 1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2.}$

Con la constante de Euler-Mascheroni${\displaystyle \gamma }$, para${\displaystyle n\to \infty }$

${\displaystyle \lim _{n\to \infty }(H_{n}-\ln n)=\gamma }$

se cumple, lo que resulta en una probabilidad de supervivencia asintótica de

${\displaystyle \lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0.30685.}$

Dado que la secuencia de probabilidades es monótonamente decreciente , los prisioneros sobreviven con la estrategia de seguimiento de ciclos en más del 30% de los casos, independientemente del número de prisioneros. ^{[ 3 ]}

En 2006, Eugene Curtin y Max Warshauer demostraron la optimalidad de la estrategia de seguimiento de ciclos. La demostración se basa en una equivalencia con un problema relacionado en el que todos los prisioneros pueden estar presentes en la habitación y observar la apertura de los cajones. Matemáticamente, esta equivalencia se basa en el lema de transición de Foata , una correspondencia biunívoca entre la notación de ciclos (canónica) y la notación de permutaciones de una línea. En el segundo problema, la probabilidad de supervivencia es independiente de la estrategia elegida e igual a la probabilidad de supervivencia en el problema original con la estrategia de seguimiento de ciclos. Dado que una estrategia arbitraria para el problema original también puede aplicarse al segundo problema, pero no puede alcanzar una mayor probabilidad de supervivencia en este último, la estrategia de seguimiento de ciclos debe ser óptima. ^{[ 2 ]}

En un principio, Gál y Miltersen consideraron en su artículo el caso en que el número de cajas es el doble del número de miembros del equipo, mientras que la mitad de las cajas están vacías. Este es un problema más difícil, ya que las cajas vacías no conducen a ninguna parte y, por lo tanto, no se puede aplicar la estrategia de seguimiento de ciclos. Queda por determinar si, en este caso, la probabilidad de ganar tiende a cero a medida que aumenta el número de miembros del equipo. ^{[ 4 ]}

En 2005, Navin Goyal y Michael Saks desarrollaron una estrategia para el equipo B basada en la estrategia de seguimiento de ciclos para un problema más general en el que la fracción de cajas vacías, así como la fracción de cajas que cada miembro del equipo puede abrir, son variables. La probabilidad de ganar sigue tendiendo a cero en este caso, pero más lentamente que lo sugerido por Gál y Miltersen. Si el número de miembros del equipo y la fracción de cajas que se abren son fijos, la probabilidad de ganar permanece estrictamente mayor que cero cuando se añaden más cajas vacías. ^{[ 10 ]}

En caso de que el director de la prisión no tenga que distribuir los números en los cajones al azar y se dé cuenta de que los presos pueden aplicar la estrategia mencionada anteriormente y adivine la numeración de las cajas que usarán (como los números indicados en las cajas), puede frustrar la estrategia. Para ello, solo tiene que asegurarse de que la asignación de números de presos a los cajones constituya una permutación con un ciclo de longitud mayor a 50. Los presos, a su vez, pueden contrarrestar esto acordando entre ellos una numeración aleatoria específica de los cajones, siempre que el director no lo oiga o no se moleste en responder reemplazando los números en las cajas antes de que los presos entren. ^{[ 11 ]}

En caso de que un prisionero entre primero en la habitación, inspeccione todas las cajas y luego intercambie el contenido de dos de ellas, todos los prisioneros sobrevivirán. Esto se debe a que cualquier ciclo de longitud superior a 50 puede romperse, por lo que se garantiza que todos los ciclos tengan una longitud máxima de 50.

Para un número suficientemente grande de prisioneros${\displaystyle N}$, pueden asegurar su escape abriendo significativamente menos de la mitad de los cajones. Específicamente, cada prisionero necesita abrir solo${\displaystyle O\left(N{\frac {\log \log N}{\log N}}\right)}$cajones para asegurar la fuga de todos los prisioneros. ^{[ 12 ]}

En la variante en la que cualquier prisionero que encuentre su número queda libre, la probabilidad esperada de supervivencia de un individuo dada una permutación aleatoria es la siguiente:

Sin estrategia:${\displaystyle {\frac {1}{2}}}$

Con la estrategia para el problema original:${\displaystyle (1-\ln(2))\cdot 1+\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}\left(1-{\frac {k}{n}}\right)=1-\ln(2)+\sum _{\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}-\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{n}}=1-\ln(2)+\ln(2)-{\frac {1}{2}}={\frac {1}{2}}}$

Cabe destacar que, si bien obtenemos los mismos valores esperados, provienen de distribuciones muy diferentes. Con la segunda estrategia, algunos prisioneros están simplemente destinados a morir o vivir según una permutación particular, mientras que con la primera estrategia (es decir, sin estrategia), existe realmente una probabilidad de 1/2 para cada permutación.

En 2009, Adam S. Landsberg propuso la siguiente variante más simple del problema de los 100 prisioneros que se basa en el conocido problema de Monty Hall : ^{[ 13 ]}

Detrás de tres puertas cerradas se encuentran, al azar, un coche, las llaves y una cabra. Hay dos jugadores: el primero debe encontrar el coche y el segundo, las llaves. Solo si ambos lo consiguen, podrán conducir el coche hasta casa. El primer jugador entra en la habitación y puede abrir consecutivamente dos de las tres puertas. Si lo logra, las puertas se cierran y entra el segundo jugador. Este también puede abrir dos de las tres puertas, pero no puede comunicarse con el primero de ninguna manera. ¿Cuál es la probabilidad de ganar si ambos jugadores actúan de forma óptima?

Si los jugadores eligen sus puertas al azar, la probabilidad de ganar es solo de 4/9 ( aproximadamente un 44%). Una estrategia óptima asocia al primer jugador y el coche con el número 1, al segundo jugador y las llaves con el número 2, y a la cabra con el número 3. El algoritmo básico es, por lo tanto:

• El jugador 1 abre primero la puerta 1. Si el coche está detrás de la puerta, el jugador ha tenido éxito. Si las llaves estaban detrás de la puerta, el jugador abre la puerta 2; si, en cambio, la cabra estaba detrás de la puerta, el jugador abre la puerta 3.
• El jugador 2 abre primero la puerta 2. Si las llaves están detrás de la puerta, el jugador tiene éxito. Si el coche estaba detrás de la puerta, el jugador abre a continuación la puerta 1; mientras que si la cabra estaba detrás de la puerta, el jugador abre a continuación la puerta 3.

En las seis posibles distribuciones de coche, llaves y cabra detrás de las tres puertas, los jugadores abren las siguientes puertas (en los casos verdes, el jugador tuvo éxito):

El éxito de la estrategia se basa en establecer una correlación entre los éxitos y fracasos de los dos jugadores. Aquí, la probabilidad de ganar es 2/3 , lo cual es óptimo ya que el primer jugador no puede tener una probabilidad de ganar mayor que esa. ^{[ 13 ] En} otra variante, se esconden tres premios detrás de tres puertas y tres jugadores deben encontrar de forma independiente sus premios asignados con dos intentos. En este caso , la probabilidad de ganar también es 2/3 cuando se emplea la estrategia óptima. [ ^{14 ]}

En lugar de tener que encontrar su número en los primeros 50 intentos, la prueba podría consistir en encontrar el número en los 50 intentos impares, 1, 3, ..., 97, 99. Cada prisionero tiene un 50% de probabilidad de encontrar su propio número en un intento impar. La estrategia principal funcionará para todos los prisioneros si la permutación de los prisioneros contiene solo ciclos de longitud impar. Para 100 prisioneros, la probabilidad de que todos tengan éxito utilizando la estrategia principal es aproximadamente del 7,9589%, lo cual es sustancialmente mejor que la probabilidad (1/2) ¹⁰⁰ que se obtendría si cada prisionero abriera los cajones de forma independiente y al azar.

Los prisioneros pueden abrir de 1 a 99 cajones y todos deben encontrar su propio número o todos deben fallar. Deben hacerlo 100 veces en 100 días consecutivos. Si solo es un día y los prisioneros optan por no encontrar sus números, es decir, cada prisionero abre solo el cajón etiquetado con su propio número, todos tienen éxito con una probabilidad del 36,79 %. Sin embargo, intentar esto 100 veces seguidas resulta en una tasa de éxito cercana al 0 %. Pero cuando cada prisionero abre 99 cajones siguiendo la estrategia principal, todos tienen una tasa de éxito del 100 %, ya que el único caso en el que un prisionero no encuentra su número es una permutación con un solo ciclo de longitud 100 y entonces todos los prisioneros obtienen el mismo resultado. ^{[ 9 ]}