100 prisioneros y una bombilla

Question

100 presos están encarcelados en celdas individuales. Cada celda no tiene ventanas y es a prueba de sonido. Hay una sala de estar central con una bombilla; la bombilla está apagada inicialmente. Ningún preso puede ver la bombilla desde su propia celda. Cada día, el carcelero elige a un prisionero de forma completamente aleatoria, y ese preso visita la sala de estar central; al final del día, el preso es devuelto a su celda. Mientras está en la sala de estar, el preso puede encender o apagar la bombilla si lo desea. Además, el preso tiene la opción de afirmar que los 100 presos han estado en la sala de estar. Si esta afirmación es falsa (es decir, algunos presos aún no han estado en la sala de estar), los 100 presos serán fusilados por su estupidez. Sin embargo, si es realmente cierto, todos los presos serán liberados e ingresados en MENSA, ya que el mundo siempre puede usar a más personas inteligentes. Por lo tanto, la afirmación solo debe hacerse si el preso está 100% seguro de su validez.

Antes de que comience todo este procedimiento, se permite a los presos reunirse en el patio para discutir un plan. ¿Cuál es el plan óptimo en el que pueden ponerse de acuerdo, de modo que eventualmente alguien haga una afirmación correcta?

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

Me preguntaba si alguien sabía la solución para la solución de los 4,000 días. Además, ¿alguien tiene alguna idea sobre cómo resolver esto?

Solo quería saber si alguien tiene alguna idea de cómo resolver esto. http://www.siam.org/ ofrece dinero en premio por una prueba de una solución óptima para esto. Supongo que para dejarlo claro, la gente quiere un plan que signifique que en promedio se tomará la menor cantidad de tiempo para liberar al preso. El punto es que el tiempo de ejecución promedio sea lo más bajo posible.

Answer 1

La solución "estándar" para el rompecabezas es la siguiente. Los prisioneros eligen a uno de ellos, vamos a llamarlo "El Contador". El trabajo de El Contador es contar a los prisioneros que han estado en la sala de estar. El trabajo de los otros prisioneros es dar una señal a El Contador de que han estado en la sala de estar. Esto se hace de la siguiente manera. El Contador es la única persona que puede apagar la luz. Los demás solo pueden encender la luz y solo hacerlo una vez. Es decir, si un prisionero entra en la sala de estar y la bombilla está apagada y nunca la ha encendido, entonces la enciende. La bombilla permanecerá encendida hasta que El Contador venga y la apague. Cuando El Contador ha apagado la bombilla 99 veces, sabe que todos los prisioneros han estado en la sala de estar.

No sé cuál es la eficiencia de esta solución, pero en tu enlace se afirma que la solución estándar lleva en promedio 27-28 años. Así que sospecho que esa es la eficiencia de esta solución.

Answer 2

Aquí hay una forma de mejorar la solución de Levon. Ahora mismo no tengo tiempo para hacer un análisis completo de probabilidad, pero mis estimaciones muy aproximadas sugieren que con ajustes cuidadosos, técnicas como esta deberían poder reducir el tiempo promedio de ejecución a alrededor de 4000 días:

No es seguro pero es "bastante probable" que cada prisionero pueda visitar la sala de estar al menos una vez durante los primeros, digamos, 800 días. Así que divide la estrategia en varias fases:

• Día 1 a 800: Todos encienden la lámpara la primera vez que ven la sala de estar. Si tenemos suerte, después del día 800 habrá 50 prisioneros que hayan apagado al menos una vez la lámpara. Ellos son los prisioneros "activos". (Si tenemos mala suerte y hay alguien que no ha estado en la sala de estar todavía, habrá menos de 50 prisioneros activos).

• Día 801 a 1600: Todos los prisioneros que son activos después de la primera fase encienden la lámpara la primera vez que ven la sala de estar durante este periodo. (El prisionero que entra el día 801 se asegura de que la lámpara ya esté apagada antes de que haga su parte, si no, algo habrá salido mal, pero continúa según lo planeado de todos modos). Los prisioneros que apagaron la lámpara durante esta fase siguen activos. Si tenemos suerte, hay 25 de ellos.

• Día 1601 a 2400: Divide nuevamente por la mitad el número de prisioneros activos. Esta vez los que encendieron la lámpara siguen activos; ahora hay 13 prisioneros activos a menos que algo haya salido mal.

• Día 2401 a 6000: Cuenta los 13 prisioneros aún activos utilizando el algoritmo estándar, con un Contador seleccionado de antemano.

Si alguien todavía se encuentra en prisión el día 6001, todos se encogen de hombros y comienzan de nuevo el algoritmo desde el día 1. Dado que 3600 días deberían ser suficientes para contar a 13 prisioneros activos, el principal riesgo es que alguien que necesitaba participar en una de las primeras tres fases no lo haya hecho, y dado que el riesgo de eso es pequeño, no afectará mucho el tiempo de ejecución esperado del algoritmo.

Con los parámetros dados aquí (y varios atajos de aproximación en el cálculo) esta estrategia tiene un tiempo promedio de ejecución de 4353 días. Pero hay lugar para algunas optimizaciones ajustando los números. Parece que 800 días es cercano al óptimo para la primera división, pero las divisiones posteriores pueden acortarse un poco sin incurrir en un riesgo total tan grande de perder a un prisionero activo y tener que reiniciar.

EDITAR: Después de una búsqueda semi-sistemática de mejores parámetros, parece que lo mejor que este método puede lograr es un tiempo promedio de ejecución de 4227 días (aproximadamente 11½ años), que se logra con tres fases de división de 840, 770 y 700 días, seguidas por una fase de conteo de 2200 días. Ni más fases de división ni menos mejoraron la eficiencia general. De vuelta a la mesa de dibujo ...

Answer 3

Las soluciones de tiempo más corto que conozco se basan en este esquema, sugerido por primera vez por Paul Hammond aquí.

El tiempo se divide en rondas, y cada ronda se divide aún más en dos etapas. En el esquema original de Paul Hammond, la primera etapa en cada ronda es de 2600 días, mientras que la segunda es de 2700 días.

Cada prisionero se considera que comienza con un "token" virtual. Si la luz está apagada, pueden dejar su token en la habitación encendiendo la luz (por lo que ya no tienen un token ellos mismos). Pueden recoger un token dejado en la habitación apagando la luz. En la reunión inicial, se elige un contador principal y 9 contadores asistentes. Todos los demás son "drones". Los drones nunca recogen un token (excepto en el último día de una etapa). Solo pueden dejar uno.

Durante la primera etapa, los drones dejan su token en la habitación cuando la luz está apagada. Si la luz está encendida, o si ya han entregado su token, no hacen nada. Todos los contadores recogen cualquier token dejado en la habitación hasta que tengan 10 tokens (incluyendo el suyo propio). Después de eso, no hacen nada en esta etapa. En el último día de la etapa, la persona que visite la habitación recoge cualquier token que esté allí (si se trata de un drone y aún no ha entregado su propio token, entonces tendrá dos tokens para pasar en la siguiente ronda, los cuales debe entregar uno a la vez).

Durante la segunda etapa, los tokens se pasan de 10 en 10 de los contadores asistentes al contador principal. Los drones nunca encienden o apagan la luz. Los contadores asistentes solo pueden encender la luz si tienen 10 tokens para pasar. Después de pasarlos, se convierten en drones. El contador principal apaga la luz en su próxima visita, y agrega 10 tokens a su inventario. Si tiene los 100 tokens, declara que todos han visitado. Al igual que en la primera etapa, si la luz está encendida en el último día de la etapa, la persona que visite recoge los 10 tokens allí, y los guarda para la etapa 2 de la próxima ronda, cuando actuará como contador asistente.

Si la ronda no tiene éxito, se lleva a cabo una ronda adicional con nuevas etapas 1 y 2, y así sucesivamente, hasta que el contador principal finalmente alcance los 100.

Paul Hammond originalmente hacía que comenzaran de nuevo con cada nueva ronda (todos recuperaban sus tokens y todos los contadores restablecían sus recuentos a su propio token). Las simulaciones por computadora estiman que el tiempo de ejecución esperado es de 3964 días. AlexH sugirió guardar los tokens como lo describí anteriormente. Este cambio y ajuste de las duraciones de las etapas (que no necesariamente deben ser iguales entre rondas) produjeron un tiempo de ejecución estimado esperado de 3600 días. Sin embargo, la persona que publicó ese resultado no especificó qué duraciones de etapa utilizó. Sin embargo, una variante posterior del esquema que elige a los contadores durante un período especial de 40 días al principio y usa duraciones de etapa iniciales de 2000 y 1500, mientras que todas las etapas posteriores son de 300 días cada una, produce un tiempo de ejecución esperado estimado de 3489 días.

Un esquema posterior parece haber reducido eso a menos de 3400 días, pero aún no he examinado ese esquema.

Answer 4

Una encuesta de varias estrategias se puede encontrar en https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf. Describe una estrategia ("two-stage counting") que se cree, basado en simulaciones, produce tiempos de ejecución esperados entre 3500 y 4000 días, y hace referencia a una estrategia híbrida por un Bertram Felgenhauer que supuestamente se demuestra que se ejecuta en un promedio de 3949 días.

Answer 5

La estrategia de la reducción a la mitad parece funcionar bien: en una primera fase de x1 días todos encienden la lámpara en la primera entrada (la lámpara siempre se apaga en el último día de una fase). En la siguiente fase i+1 todos los que encendieron la lámpara a un cierto estado en la fase i, continúan. Este estado en particular depende del número de jugadores en la fase i: si era par (como inicialmente - 100), entonces todos los que apagaron la lámpara continúan para i+1, si era impar - entonces todos los que la encendieron - esto es para asegurar que nadie "se escape". Esto debería continuar hasta que haya una fase con 2 jugadores. Entonces, si uno de los dos entra y ve la lámpara encendida, sabe que es el segundo, y en retrospectiva, cada jugador activo logró entrar en la habitación, incluida la primera fase, por lo que todos han estado al menos una vez allí.

Las fases son con 100, 50, 25, 13, 7, 4 y 2 jugadores, por lo que si intentamos resolver el siguiente problema de minimización: minimizar la suma de las longitudes de las fases, con la restricción de que la probabilidad total de que todos los jugadores de la fase entren en las habitaciones al menos una vez en cada fase sea exactamente (o al menos - dependiendo del algoritmo de minimización utilizado) 0.5. Por supuesto, se puede establecer una probabilidad objetivo diferente.

Hay dos enfoques: 1. resolver un problema restringido donde el objetivo es el total de días y la restricción es la probabilidad total = 0.5 (o algo más). 2. resolver un problema no restringido donde la función objetivo de alguna manera incluye la longitud total y la probabilidad objetivo (esto permite una mayor variedad de métodos).

En todos los casos hay un problema general de que el dominio real es de números enteros y minimizar funciones sobre números enteros es difícil, así que al menos opté por aproximaciones. Además, parece que la tarea restringida es difícil y la tarea no restringida es no convexa.

Para Nelder-Mead y una función objetivo algo forzada obtengo soluciones diferentes (todas muy cercanas a p=0.5) dependiendo del punto de inicio. El mínimo, logrado desde un punto de inicio sensato, es alrededor de 3439 días. (Ver más abajo para el punto de inicio sensato).

SLSQP y COBYLA parecen comportarse de manera más consistente una vez que se resuelven algunos problemas numéricos (tanto en la función objetivo como en la restricción) y dan 3455.

Respecto a la suposición inicial sensata - parece razonable suponer que si la probabilidad objetivo es 0.5. entonces podemos elegir longitudes iniciales de fase para que todas las probabilidades de fase sean iguales, es decir, 0.5^(1/7). La experimentación confirmó que esta podría ser una buena suposición inicial.