Problema de los 100 prisioneros
Consiste en que cada uno de 100 prisioneros debe encontrar su número en uno de los 100 cajones para sobrevivir y si alguno no lo encuentra, todos morirán; y, cada prisionero puede abrir sólo 50 cajones y no puede comunicarse con los demás prisioneros, excepto en el debate previo de la estrategia.
A primera vista, la situación es desesperada, pero existe una estrategia que ofrece a los cautivos una oportunidad de supervivencia aproximadamente del 30%.
El científico en computación danés Peter Bro Miltersen fue el primero en proponer este problema en el 2003.
En la literatura se encuentran diferentes enunciados de este problema.
A continuación se muestra la versión de Philippe Flajolet y Robert Sedgewick:El director de una prisión ofrece a un centenar de condenados a muerte (numerados del 1 al 100) una última oportunidad.
Cada uno de los prisioneros puede: abrir y comprobar sólo 50 cajones en cualquier orden, y después cierra todos los cajones.
Antes de que el primer prisionero busque su número, los prisioneros pueden discutir la estrategia, pero no pueden comunicarse a partir de este momento.
La clave del éxito radica en el hecho de que los prisioneros no necesitan decidir de antemano cuáles cajones abrir: cada prisionero puede utilizar la información recibida del contenido de los cajones ya abiertos, para decidir cuál abrir después.
Otra importante observación es que el éxito de un prisionero no es independiente del éxito de otros prisioneros, ya que todo depende de cómo se distribuyeron los números en los cajones.
La estrategia descrita cubre no sólo los prisioneros, sino también los cajones numerados del 1 al 100 (por ejemplo, hilera por hilera, a partir del primer cajón de la esquina superior izquierda del armario).
La única cuestión reside en si la secuencia es mayor de 50.
La razón del éxito de esta estrategia puede ilustrarse en el siguiente ejemplo, usando 8 prisioneros y 8 cajones, cada prisionero puede abrir 4 cajones.
La permutación del primer ejemplo anterior se puede escribir en notación cíclica como
La notación del ciclo no es única ya que un ciclo de longitud l se puede escribir en l diferentes formas dependiendo del número de inicio del ciclo.
Durante la apertura de los cajones en la estrategia anterior, cada prisionero sigue un ciclo único que siempre termina con su propio número.
Si una permutación contiene un ciclo de longitud 5 o más, todos los prisioneros cuyos números se encuentren en dicho ciclo no alcanzan su propio número después de cuatro pasos.
Dentro de este ciclo, estos números se pueden ordenar en (l-1)!
ya que hay l permutaciones para representar distintos ciclos de longitud l debido a la simetría cíclica.
La probabilidad de que una permutación aleatoria (uniformemente distribuida) no contenga ningún ciclo de duración superior a 50 se calcula con la fórmula para eventos individuales y la fórmula para eventos complementarios así dada por
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.Detrás de tres puertas cerradas, un coche, las llaves del coche y una cabra se distribuyen al azar.
Sólo si ambos jugadores tienen éxito pueden conducir el coche a casa.
El primer jugador entra en la sala y puede abrir dos de las tres puertas consecutivamente.
Si tiene éxito, las puertas se cierran de nuevo y el segundo jugador entra en la sala.
El segundo jugador también puede abrir dos de las tres puertas, pero no puede comunicarse con el primer jugador de ninguna forma.
