Hace dos días, he encontrado este problema en reddit (no tengo acceso a reddit cuando hice las matemáticas, así que lo hice con 24 en lugar de 23, y decidí que el alcaide escogido a alguien todos los días, no "cada vez que él se siente como que"):
Un funcionario de prisiones le dice a 24 presos que él tiene un "juego" para ellos. Una vez por día, el director elige a un preso al azar y se les lleva a Cambiar de Habitación. El acertadamente llamado Interruptor de la Habitación tiene dos interruptores, tanto en la posición de Apagado en primer lugar, que están conectados a nada. El llamado preso tiene que alternar exactamente un interruptor.
En cualquier momento, a cualquier preso que se puede ir al guardián y le digo que de los 24 presos fuimos todos a la Sala de switches al menos una vez. Si eso es cierto, todos están liberados. Si no, van a ser las salchichas para los otros presos o algo.
Los presos pueden venir con un plan de ahora , pero no siempre va a ser capaz de comunicarse de nuevo hasta que alguien le dice el guardián.
EDITAR Después de algunos debates con @alex.jordania, quería aclarar que mi intención. Mi perspectiva es que esto es una metáfora para "¿cómo le digo que N distintos eventos, de manera uniforme y aleatoria sucediendo, todo ha sucedido al menos una vez si usted sólo tiene 2 bits para repuesto", y no tiene nada que ver con un verdadero guardián (que podría ser parcial en sus elecciones al azar o utilizar otro modelo de distribución para el tornillo de seguridad de los prisioneros), o real de los presos.
Soy el único interesado en una respuesta que supone un prisionero está seleccionada de forma aleatoria y uniforme de una vez cada día (no "de vez en cuando", como se indica en el reddit de riddle), así que usted puede ignorar cualquier supuesto de que el guardián que hay para moler los presos a las salchichas o selecciona personas con un sesgo o simplemente no seleccionar a nadie.
El "clásico" de la solución es que los presos designar a un líder. Cuando un preso entra en el Interruptor de la Habitación (excepto el líder), si nunca has estado allí y encontrar el primer interruptor en la posición de Apagado, se enciende. De lo contrario, alternar el otro interruptor. Cuando el líder entra en el Interruptor de la Habitación, si ve que el primer interruptor en la posición On, él sabe que alguien que nunca ha estado allí antes ha sido, por lo que los cargos primero y apaga el interruptor. Cuando él ha contado a 23, él sabe que todo el mundo ha estado allí por lo menos uno.
La cosa es que esta solución es una mierda. Suponiendo 24 presos de nuevo, y saber que están elegidos al azar, se puede representar la totalidad de la cosa como una serie de distribuciones geométricas (esto también supone que estoy haciendo lo correcto, que no puede ser):
$$ X: \text{número de días antes de que el Líder va al Interruptor de la Sala de}\\ X \sim Geom\left(\frac{1}{24}\right)\\ E(X) = 24, Var(X) = 552\\ $$ $$ Y_n: \text{número de días antes de que uno de los n restantes prisionero}\\ \text{se encuentra el Interruptor de la Habitación por primera vez (n de 1 a 23)}\\ Y_n \sim Geom\left(\frac{n}{24}\right)\\ E(Y_n) = \frac{24}{n}, Var(Y_n) = \frac{24 (24-n)}{n^2} $$
Dado que los valores esperados y la varianza puede ser linealmente agregado, podemos esperar que el Líder dirá el guardián después de que, en promedio, 642 días, con una desviación estándar de 116, asumiendo el líder va a ir $E(X)$ días después de cualquier preso fue por primera vez como modelado por $E(Y_n)$:
$$ Z: \text{Número de días antes de que el Líder anuncia todos han sido para el Interruptor de la Sala de}\\ E(Z) = \sum_{n=1}^{23}E(X) + E(Y_n) = 552 + \sum_{n=1}^{23}E(Y_n) \aprox 552 + 89.6229 \aprox 641.6229\\ Var(Z) = \sum_{n=1}^{23}Var(X) + Var(Y_n) = 12696 + \sum_{n=1}^{23}Var(Y_n) \aprox 12696 + 833.3521 \aprox 13529.3521\\ \sigma = \sqrt{13529.3521} = 116.3157 $$
Muy simple, las matemáticas nos dicen que después de 642 días de cada prisionero, ha sido en promedio de 26 veces el Interruptor de la Habitación. Esto se ve como una horrible pérdida de tiempo.
Estoy bastante seguro de que es posible calcular cuántos días tendría que esperar antes de tener un 99% de posibilidades (o más) de que cada preso ha estado allí. El problema es, yo soy sólo la mitad del camino a través de mi colegio estadísticas de la clase, y sólo hemos visto fácil distribuciones donde los éxitos son independientes, así que no estoy demasiado seguro de cómo hacer frente a esa.
¿Cómo calcular las probabilidades de que cada preso ha sido para el Interruptor de la Habitación después de la $Z$ días?
EDIT acabo de hacer un rápido y sucio programa para que se ejecute "simulaciones", y se necesita un promedio de 90.6 días hasta que todos los prisioneros ha visitado el Interruptor de la Habitación, con una desviación estándar de 28.5. Hacer que en una distribución normal, debe ser alrededor de 157 días antes de que podamos afirmar con un 99% de certeza de que cada preso ha visitado el Interruptor de la Habitación al menos una vez, y 179 días para el 99,9% de certeza. Huelga decir que usted está bastante seguro después de 641 días...
Es un método empírico y no se siente matemáticamente satisfacciones, así que la pregunta sigue abierta para las mejores respuestas.
