El problema de los 100 presos y las 100 cajas

El problema de 100 prisioneros y 100 cajas es un problema de teoría de probabilidad y combinatoria . La esencia de la tarea es que cada uno de los 100 prisioneros debe encontrar su número en una de las 100 casillas para que todos sobrevivan; si uno falla, todos mueren. Cada prisionero solo puede abrir 50 cajas y no puede comunicarse con otros prisioneros, excepto para una discusión preliminar de estrategia.

A primera vista, la situación parece desesperada, pero existe una estrategia que les da a los prisioneros una probabilidad de supervivencia de alrededor del 30%. El problema fue propuesto por el informático danés Peter Miltersen en 2003 .

Condición

En la literatura, existen diferentes condiciones del problema. A continuación se muestra la versión de Philippe Flajolet y Robert Sedgwick [1] .

El director de la prisión ofrece una última oportunidad a un centenar de presos condenados a muerte. Los presos están numerados del 1 al 100 y la habitación contiene un armario con 100 cajones. El jefe coloca aleatoriamente uno de los números del 1 al 100 en cada casilla y diferentes números en todas las casillas. Los prisioneros se turnan para entrar en la habitación. Cada preso puede abrir y marcar 50 casillas en cualquier orden. Después de cada prisionero, las cajas se cierran nuevamente y todos los números permanecen en las cajas. Si cada uno de los presos encuentra su número en una de las casillas, entonces todos los presos serán indultados; si al menos un preso no encuentra su número, todos los presos serán ejecutados. Antes de que el primer preso entre en la habitación, los presos pueden discutir la estrategia, pero no pueden comunicarse después de ese punto. ¿Cuál es la mejor estrategia para los presos?

Se supone que los números de prisioneros se distribuyen entre las cajas al azar y, por lo tanto, todas las permutaciones de los números de prisioneros en las cajas son igualmente probables. También se entiende que las casillas también están numeradas del 1 al 100, o es posible acordar de antemano la falta de ambigüedad de dicha numeración.

Si un preso elige al azar 50 cajas de 100 , tiene un 50% de posibilidades de encontrar su número. La probabilidad de que todos los prisioneros, al abrir casillas al azar, encuentren sus números es el producto de las probabilidades de éxito de los prisioneros individuales, es decir

\left({\frac {1}{2}}\right)^{100}

≈ 0.00000000000000000000000000000008

es un número evanescentemente pequeño. La situación parece desesperada.

Solución

Estrategia

Existe una estrategia que proporciona más de un 30% de posibilidades de que los prisioneros sobrevivan. La clave del éxito es que los presos no tienen que decidir de antemano qué cajas abrir: todos pueden usar la información obtenida del contenido de las cajas que ya han abierto para decidir cuál abrir a continuación. Otra observación importante es que el éxito de un prisionero no es independiente del éxito de los demás, ya que todos dependen de la disposición de los números en las casillas [2] .

Para describir la estrategia, suponga que no solo los prisioneros, sino también las casillas están numeradas del 1 al 100, por ejemplo, línea por línea, comenzando desde la casilla superior izquierda. La estrategia es [3] :

Cada preso primero abre la caja con su número.
Si esta casilla contiene su número, el preso ha tenido éxito.
De lo contrario, la caja contiene el número de otro preso y abre la caja con ese número.
El preso repite los pasos 2 y 3 hasta que encuentra su número o abre 50 cajones.

Partiendo de su propio número y recorriendo el bucle, el preso garantiza que se encuentra en una secuencia de casillas que terminan con su número. El éxito de sus acciones depende solo de si esta secuencia es más larga que 50 casillas.

En una versión modificada del problema, donde se agrega un personaje más: un abogado al que se le permite abrir todas las cajas y, si es necesario, intercambiar el contenido de dos de ellas, la supervivencia de los prisioneros se vuelve independiente de la permutación inicial: para esto, el abogado, habiendo descubierto un ciclo de más de 50 cajas, lo rompe por dos ciclos de no más de 50.

Ejemplos

La razón del éxito de esta estrategia se puede ilustrar con el siguiente ejemplo: hay 8 prisioneros y cajas, cada prisionero puede abrir 4 cajas. Suponga que el director de la prisión asignó los números de los presos a las casillas de la siguiente manera:

números de caja	una	2	3	cuatro	5	6	7	ocho
números de prisioneros	7	cuatro	6	ocho	una	3	5	2

De acuerdo con la estrategia anterior, los presos actúan de la siguiente manera:

El preso 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 número y así lo logra.
El preso 2 abre en orden las casillas 2, 4 y 8. En la última casilla encuentra su número.
El preso 3 abre los cajones 3 y 6; en este último encuentra su número.
El preso 4 abre los cajones 4, 8 y 2 antes de encontrar su número. Tenga en cuenta que este es el mismo ciclo que encontró el Prisionero 2, aunque ninguno de estos prisioneros lo sabe.
Los presos 5 a 8 también encontrarán sus números de manera similar.

En este ejemplo, todos los presos encuentran sus números, pero no siempre es así. Por ejemplo, si cambia el contenido de las casillas 5 y 8, el preso 1 usa todos sus intentos abriendo las casillas 1, 7, 5 y 2 y no encuentra su número:

números de caja	una	2	3	cuatro	5	6	7	ocho
números de prisioneros	7	cuatro	6	ocho	2	3	5	una

Y en el siguiente arreglo, el preso 1 abrirá las casillas 1, 3, 7 y 4 y tampoco lo conseguirá:

números de caja	una	2	3	cuatro	5	6	7	ocho
números de prisioneros	3	una	7	5	ocho	6	cuatro	2

De hecho, en este ejemplo, todos menos 6 reclusos no podrán encontrar la casilla con su número.

Explicación en términos de permutaciones

La disposición de los números de prisioneros en las casillas se puede describir matemáticamente como una permutación de números del 1 al 100. Tal permutación es un mapeo uno a uno del conjunto de números naturales del 1 al 100 sobre sí mismo. Una secuencia de números tal que el primero va al segundo, el segundo al tercero, y así sucesivamente, y el último al primero, se llama ciclo de permutación . Cada 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 bucle como

{\ estilo de visualización (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 segundo ejemplo es, respectivamente,

{\ estilo de visualización (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 cíclica no es única, ya que un ciclo de longitud se puede escribir de muchas formas diferentes dependiendo de la elección del primer número. Al abrir las cajas según la estrategia sugerida anteriormente, cada preso sigue un ciclo que termina con su propio número. En el caso de ocho prisioneros, esta estrategia tiene éxito si y solo si la duración del ciclo de permutación más largo es como máximo 4. Si la permutación contiene un ciclo de longitud 5 o más, todos los prisioneros cuyos números se encuentran en dicho ciclo no alcanzan su número después de cuatro pasos. $yo$ $yo$

Probabilidad de éxito

En el problema original, 100 prisioneros tendrán éxito si el ciclo de permutación más largo es como máximo 50. Por lo tanto, la probabilidad de que sobrevivan es igual a la probabilidad de que una permutación aleatoria de números del 1 al 100 no contenga un ciclo de longitud mayor de 50. Esta probabilidad se define como sigue.

Una permutación de números del 1 al 100 puede contener como máximo un ciclo de longitud . Hay formas de seleccionar números para dicho ciclo, donde los corchetes indican combinaciones . Estos números se pueden organizar alrededor del ciclo de formas, ya que debido a la simetría cíclica hay formas de escribir ciclos de la misma duración . Los números restantes se pueden organizar de maneras. En total, el número de permutaciones de números del 1 al 100 con un ciclo de longitud es ${\ estilo de visualización l> 50}$ ${\tbinom {100}{l))$ ${\ estilo de visualización (l-1)!}$ $yo$ $yo$ ${\ estilo de visualización (100-l)!}$ ${\ estilo de visualización l> 50}$

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

La probabilidad de que una permutación aleatoria ( distribuida uniformemente ) no contenga un ciclo mayor de 50 se calcula como

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})\aprox. 0,31183

donde es el -ésimo número armónico . Por tanto, utilizando la estrategia de seguir el ciclo, los presos sobreviven en alrededor del 31% de los casos [3] . Sorprendentemente, esto es más del 25%: la probabilidad de éxito de solo dos prisioneros, eligiendo cajas al azar e independientemente. $H_n$ $norte$

Asintóticos

Si en lugar de 100 presos consideramos presos, donde es un número natural arbitrario, la probabilidad de supervivencia de los presos al utilizar la estrategia de seguir el ciclo se define como $2n$ $norte$

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

Sea la constante de Euler- Mascheroni . Entonces para nosotros obtenemos $\gama$ $n\to\infty$

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

y por lo tanto la probabilidad de supervivencia tiende a

\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 decrece monótonamente , al utilizar la estrategia de seguir el ciclo, los presos sobreviven en más del 30% de los casos, independientemente del número de presos [3] .

Optimalidad

En 2006, Eugene Curtin y Max Varsovia demostraron la optimización de la estrategia de seguimiento del ciclo. La prueba se basa en una equivalencia con un problema similar en el que a todos los presos se les permite estar presentes en una habitación y ver cómo se abren las cajas. Matemáticamente, esta equivalencia se basa en el lema de transición de Foata , una correspondencia uno a uno entre la notación cíclica (canónica) y la notación de permutación estándar[ especificar ] . En el nuevo problema, la probabilidad de supervivencia no depende de la estrategia elegida y es igual a la probabilidad de supervivencia en el problema original cuando se usa la estrategia de seguir el ciclo. Dado que una estrategia arbitraria para la tarea original también se puede aplicar a la nueva tarea, pero no puede lograr una mayor probabilidad de supervivencia, la estrategia cíclica debe ser óptima [2] .

Historia

El problema de los 100 prisioneros y las 100 cajas fue planteado por primera vez en 2003 por el informático danés Peter Miltersen, quien lo publicó junto con Anna Gal en un informe sobre los resultados del 30º Coloquio Internacional sobre Autómatas, Lenguajes y Programación ( ICALP ). En su versión, el jugador A (el jefe de la prisión) pinta al azar tiras de papel con los nombres de los jugadores del equipo B (prisioneros) de rojo o azul y coloca cada tira en una casilla separada, aunque algunas de las casillas pueden estar vacías. . Para que el equipo B gane, cada uno de sus miembros debe nombrar correctamente su color después de abrir la mitad de las cajas [4] .

Inicialmente, Milterson asumió que la probabilidad de ganar se reduce rápidamente a cero con un aumento en el número de jugadores. Sin embargo, Sven Skyum, un colega de Miltersen en la Universidad de Aarhus , ideó una estrategia de ciclismo para un tipo de problema que no tiene casillas vacías. Como resultado, en el artículo se dejó como ejercicio encontrar esta estrategia. El artículo fue premiado[ aclarar ] premios a la mejor publicación [2] .

En la primavera de 2004, este problema apareció en la columna de acertijos de Joe Buhler y Alvin Berlekamp en The Mathematical Research Institute trimestral [5] . En los años siguientes, este problema comenzó a utilizarse en la literatura matemática en varias formulaciones, por ejemplo, con tarjetas sobre la mesa [6] o billeteras en casilleros [2] .

En la forma del problema de los 100 prisioneros y las 100 cajas, fue planteado en 2006 por Christoph Peppe en el Spektrum der Wissenschaft (versión alemana de Scientific American ) [7] y por Peter Winkler en el College Mathematics Journal [8] . Con modificaciones menores, esta variante fue utilizada en libros de texto de combinatoria por Philippe Flajolet y Robert Sedgwick [1] , así como por Richard Stanley [3] .

Véase también

La tarea de los tres prisioneros

Notas

↑ 1 2 Philippe Flajolet, Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press, p. 124
↑ 1 2 3 4 Eugene Curtin, Max Warshauer (2006), El rompecabezas del casillero , Mathematical Intelligencer Vol . 28: 28–31 , DOI 10.1007/BF02986999
↑ 1 2 3 4 Richard P. Stanley (2013), Combinatoria algebraica: caminatas, árboles, cuadros y más , Springer, p. 187–189
↑ Anna Gál, Peter Bro Miltersen (2003), La complejidad de la sonda celular de las estructuras de datos sucintas, Actas del 30º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) , p. 332–344
↑ Joe Buhler, Elwyn Berlekamp (2004), Columna de rompecabezas , p. 3
↑ Richard E. Blahut (2014), Criptografía y comunicación segura , Cambridge University Press, p. 29–30
↑
↑ Peter Winkler (2006), Rompecabezas de nombres en cajas , p. 260.285.289

Literatura

Philippe Flajolet , Robert Sedgewick (2009), Combinatoria analítica , Cambridge University Press
Richard P. Stanley (2013), Combinatoria algebraica: caminatas, árboles, cuadros y más , Springer
Peter Winkler (2007), Mathematical Mind-Benders , Taylor y Francis