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

Mi solución a esto fue una versión más generalizada de lo anterior. En cualquier momento dado, cada prisionero tiene un valor. Esto comienza en 1 para todos los prisioneros, excepto uno de ellos que tiene un valor de 29.

Cada noche, la bombilla tiene un valor de potencia de dos que es acordado por los prisioneros al principio. Cuando un prisionero entra en la habitación (en cualquier día excepto el día uno), si la luz está encendida aumentan su valor por el valor de la bombilla de la noche anterior.

Luego expanden su valor en binario. Si tienen un 1 en la posición de la potencia de dos para el valor de la noche subsiguiente, aseguran que la luz se quede encendida y restan esto de su propio valor. Si tienen un cero en esa posición aseguran que la luz se quede apagada.

La secuencia de los valores de la bombilla se elige mediante un sorteo de una distribución aleatoria que refleja la densidad esperada de los valores de potencia de dos presentes en la población de prisioneros en su totalidad dadas las elecciones anteriores. (Los prisioneros tienen que tener una memoria prodigiosa para este algoritmo).

Si algún prisionero se encuentra con un valor de 128, anuncian el éxito.

Answer 2

Una persona elegida al azar podría significar que los $100$ prisioneros nunca serán elegidos todos en su vida, así que me parece que no hay una cantidad mínima de tiempo para satisfacer la situación "$100$% segura" (en el caso general), así que ¿cuál es el punto de esta pregunta? Podría tomar desde $100$ días hasta toda una vida. ¿Por qué no simplemente asignarles a cada uno un número del $1$ al $100$ y hacer una marca en la sala de estar cuando estén en ella? Los prisioneros son buenos en ese tipo de cosas. ¿Quizás rayar un código binario (hombres de palo)?

Además, ¿qué sucede si uno de los no elegidos muere antes de que todos los $100$ sean elegidos? ¿Cómo se verifica si todos los prisioneros han visitado la sala de estar o no? Si está escrito en algún lugar, entonces tal vez los prisioneros deberían descubrir dónde y usar esa información.

Demasiadas incógnitas en esta pregunta mal redactada para llegar a una respuesta razonable.