El problema de los 100 prisioneros es un problema matemático de teoría de probabilidad y combinatoria . En este problema, 100 prisioneros numerados deben encontrar sus propios números en uno de 100 cajones para poder sobrevivir. Las reglas establecen que cada prisionero puede abrir solo 50 cajones y no puede comunicarse con otros prisioneros. A primera vista, la situación parece desesperada, pero una estrategia inteligente ofrece a los prisioneros una posibilidad realista de sobrevivir.
Anna Gál y Peter Bro Miltersen propusieron el problema por primera vez en 2003.
El problema de los 100 prisioneros tiene distintas versiones en la literatura. La siguiente versión es de Philippe Flajolet y Robert Sedgewick : [1]
Si cada prisionero selecciona 50 cajones de forma independiente y aleatoria , la probabilidad de que un solo prisionero encuentre su número es del 50%. La probabilidad de que todos los prisioneros encuentren sus números es el producto de las probabilidades individuales, que es (1/2 ) 100 ≈0,000 000 000 000 000 000 000 000 000 0008 , un número minúsculo. La situación parece desesperada.
Sorprendentemente, existe una estrategia que ofrece una probabilidad de supervivencia de más del 30%. La clave del éxito es que los prisioneros no tienen que decidir de antemano qué cajones abrir. Cada prisionero puede utilizar la información obtenida del contenido de cada cajón que ya ha abierto para decidir cuál abrir a continuación. Otra observación importante es que de esta manera el éxito de un prisionero no es independiente del éxito de los demás prisioneros, porque todos dependen de la forma en que se distribuyen los números. [2]
Para describir la estrategia, no sólo los prisioneros, sino también los cajones, se numeran del 1 al 100; por ejemplo, fila por fila comenzando por el cajón superior izquierdo. La estrategia ahora es la siguiente: [3]
Si el prisionero pudiera continuar indefinidamente de esta manera, inevitablemente volvería al cajón con el que comenzó, formando un ciclo de permutación (ver más abajo). Al comenzar con su propio número, el prisionero garantiza que está en el ciclo específico de cajones que contienen su número. La única pregunta es si algún ciclo tiene más de cincuenta cajones, y solo un ciclo puede ser demasiado largo, ya que como máximo uno puede comprender más de la mitad del total de cajones.
El motivo por el que esta estrategia es prometedora se ilustra con el siguiente ejemplo, en el que se utilizan ocho presos y cajones, en el que cada preso puede abrir cuatro cajones. El director de la prisión ha distribuido los números de los presos en los cajones de la siguiente manera:
Los prisioneros ahora actúan de la siguiente manera:
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 al intercambiar los cajones 5 y 8 haría que el prisionero 1 fallara después de abrir 1, 7, 5 y 2 (y no encontrara 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 deben detenerse sin éxito:
De hecho, todos los prisioneros excepto 6 (que tiene éxito directamente) fracasan.
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 del 1 al 100. Tal permutación es una aplicación uno a uno del conjunto de números naturales del 1 al 100 a sí mismo. Una secuencia de números que después de la aplicación repetida de la permutación vuelve al primer número se llama ciclo de la 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 ciclo como
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,
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 se puede escribir de diferentes maneras dependiendo del número inicial del ciclo. Durante la apertura de los cajones utilizando la estrategia anterior, cada prisionero sigue un solo ciclo que siempre termina con su propio número. En el caso de ocho prisioneros, esta estrategia de seguimiento de ciclo es exitosa 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, todos los prisioneros cuyos números se encuentran en dicho ciclo no alcanzan su propio número después de cuatro pasos.
En el problema inicial, los 100 prisioneros tienen éxito si el ciclo más largo de la permutación tiene una longitud de 50 como máximo. 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 . Existen exactamente formas de seleccionar los números de dicho ciclo (ver combinación ). Dentro de este ciclo, estos números se pueden ordenar de formas ya que existen permutaciones para representar distintos ciclos de longitud debido a la simetría cíclica. Los números restantes se pueden ordenar de formas. Por lo tanto, el número de permutaciones de los números del 1 al 100 con un ciclo de longitud es igual a
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 individuales y la fórmula para eventos complementarios , dadas así por
donde es el -é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 en lugar de 100 prisioneros se consideran, donde un número natural arbitrario, la probabilidad de supervivencia de los prisioneros con la estrategia de seguimiento del ciclo viene dada por
Con la constante de Euler-Mascheroni , para
se cumple, lo que da como resultado una probabilidad de supervivencia asintótica de
Dado que la secuencia de probabilidades es monótonamente decreciente , los prisioneros sobreviven con la estrategia de seguimiento del ciclo en más del 30% de los casos, independientemente del número de prisioneros. [3]
En 2006, Eugene Curtin y Max Warshauer dieron una prueba de la optimalidad de la estrategia de seguimiento de ciclos. La prueba se basa en una equivalencia con un problema relacionado en el que a todos los prisioneros se les permite 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 uno a uno de la notación de ciclos (canónica) y la notación unifilar de permutaciones. 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 se puede aplicar al segundo problema, pero no se puede alcanzar una probabilidad de supervivencia más alta allí, la estrategia de seguimiento de ciclos tiene que ser óptima. [2]
El problema de los 100 prisioneros fue considerado por primera vez en 2003 por Anna Gál y Peter Bro Miltersen en las actas del 30. Coloquio Internacional sobre Autómatas, Lenguajes y Programación ( ICALP ). [4] En su versión, el jugador A (el director de la prisión) colorea al azar tiras de papel con los nombres de los jugadores del equipo B (los prisioneros) en rojo o azul y coloca cada tira en una caja diferente. Algunas de las cajas pueden estar vacías (ver más abajo). Cada jugador del equipo B debe adivinar su color correctamente después de abrir la mitad de las cajas para que su equipo gane. [4] Inicialmente, Gál y Miltersen asumieron que la probabilidad de ganar tiende rápidamente a cero con un número creciente de jugadores. Sin embargo, Sven Skyum, un colega de la Universidad de Aarhus , llamó su atención sobre la estrategia de seguimiento de ciclos para el caso de este problema donde no hay cajas vacías. Encontrar esta estrategia se dejó abierto como un ejercicio en la publicación. El artículo fue honrado con el premio al mejor artículo. [2]
En la primavera de 2004, el problema apareció en la columna de acertijos de Joe Buhler y Elwyn Berlekamp de la revista trimestral The Emissary of the Mathematical Sciences Research Institute . De este modo, los autores reemplazaron las cajas por ROM y las tiras de papel de colores por números con signo . Los autores observaron que la probabilidad de ganar puede aumentar también en el caso de que los miembros del equipo no encuentren sus propios números. Si la respuesta dada es el producto de todos los signos encontrados y si la longitud del ciclo más largo es la mitad del número (par) de jugadores más uno, entonces todos los miembros del equipo en este ciclo adivinan mal o todos adivinan bien. Incluso si esta extensión de la estrategia ofrece una mejora visible para un pequeño número de jugadores, se vuelve insignificante cuando el número de jugadores se vuelve grande. [5]
En los años siguientes, el problema entró en la literatura matemática, donde se le dio forma de otras formas diferentes, por ejemplo, con cartas sobre una mesa [6] o carteras en taquillas ( locker puzzle ). [2] En forma de problema del prisionero fue planteado en 2006 por Christoph Pöppe en la revista Spektrum der Wissenschaft y por Peter Winkler en el College Mathematics Journal . [7] [8] Con ligeras modificaciones, esta forma fue adoptada por Philippe Flajolet, Robert Sedgewick y Richard P. Stanley en sus libros de texto sobre combinatoria. [1] [3] El problema, o acertijo, junto con una explicación detallada de la solución, fue presentado por el canal Veritasium en un vídeo de 2023 en YouTube .
En un primer momento, Gál y Miltersen consideraron en su artículo el caso en el 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 llevan a ninguna parte y, por lo tanto, no se puede aplicar la estrategia de seguimiento del ciclo. Es un problema abierto si en este caso la probabilidad de ganar tiende a cero con un número creciente 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 todavía tiende 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 se mantiene estrictamente mayor que cero cuando se agregan más cajas vacías. [9]
David Avis y Anne Broadbent consideraron en 2009 una variante teórica cuántica en la que el equipo B gana con certeza. [10]
En caso de que el director de la prisión no tenga que distribuir los números en los cajones de forma aleatoria y se dé cuenta de que los presos pueden aplicar la estrategia antes mencionada y adivine la numeración de las casillas que aplicarán los presos (por ejemplo, los números indicados en las casillas), puede frustrar la estrategia. Para ello, sólo tiene que asegurarse de que su asignación de los números de los presos a los cajones constituya una permutación con un ciclo de longitud superior 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 y no se moleste en responder reemplazando los números en las casillas antes de que los presos entren. [11]
En el caso de que un prisionero entre primero a la habitación, inspeccione todas las cajas y luego intercambie el contenido de dos cajas, todos los prisioneros sobrevivirán. Esto es así porque cualquier ciclo de una longitud mayor a 50 puede romperse, de modo que se puede garantizar que todos los ciclos tengan una longitud máxima de 50.
En el caso de un número suficientemente grande de prisioneros , pueden asegurar su escape abriendo significativamente menos de la mitad de los cajones. En concreto, cada prisionero necesita abrir solo cajones para asegurar la fuga de todos los prisioneros. [12]
En la variante donde 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:
Con la estrategia para el problema original:
Cabe destacar que, aunque recibimos los mismos valores esperados, estos provienen de distribuciones muy diferentes. Con la segunda estrategia, algunos prisioneros están simplemente destinados a morir o vivir dada una permutación particular, y con la primera estrategia (es decir, sin estrategia), hay "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]
Si los jugadores seleccionan sus puertas al azar, la probabilidad de ganar es solo 4/9 (alrededor del 44%). Sin embargo, la estrategia óptima es la siguiente:
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 la construcción de una correlación entre los éxitos y los 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 las tres puertas y tres jugadores tienen que encontrar independientemente 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 dentro de los primeros 50 intentos, la prueba podría ser encontrar el número dentro de los 50 intentos impares, 1, 3, ..., 97, 99. Cualquier prisionero individual tiene un 50% de posibilidades 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 usando la estrategia principal es aproximadamente 7.9589%, que es sustancialmente mejor que la probabilidad (1/2) 100 que se obtendría si cada prisionero abriera cajones independientemente al azar.
