Estrategia simétrica para 100 prisioneros y un problema de bombillas

Question

Observación: El problema es el presos y problema de la bombilla pero sin el marco probabilístico habitual (el ogro elige a su antojo). Además, la estrategia es simétrica y los enanos no tienen noción del tiempo. El enlace anterior no da una solución para estas hipótesis.

Más en detalle, el problema es el siguiente: $100$ enanos inmortales son capturados por un ogro inmortal para que juegue a un juego. Los enanos están en celdas separadas y nunca se comunican, y cada día el ogro elige arbitrariamente a un enano y lo lleva a una habitación con una bombilla que está encendida o apagada. El enano puede dejarla como está o cambiarla. El primer día, los enanos deciden una estrategia, y la bombilla está apagada.

Los enanos son capaces de salir si un día uno de ellos puede decir que todos $100$ enanos se han llevado a la bombilla (y tener razón en ello).

Dos hipótesis importantes:

• la elección del ogro es arbitraria ( no aleatorio , arbitrario), pero el juego no es injusto, así que promete que planea llevar a cada enano un número infinito de veces a la sala de las bombillas,
• los enanos tienen sin sentido del tiempo (así que, en particular, no pueden saber cuántos enanos fueron a la habitación antes que ellos, o si el ogro les llevó a la habitación varias veces seguidas). Equivalentemente, podríamos decir que el ogro lleva a un enano a la habitación siempre que quiere.

$ $

Pregunta: antes del partido, todos $100$ los enanos se reúnen una (¿última?) vez para decidir una estrategia.

• A. ¿Pueden encontrar una estrategia ganadora?

• B. [Contiene pista para 1...] ¿Pueden encontrar un ganador simétrico estrategia (es decir, cada enano tiene la misma política de acción)?

---

No tengo respuesta para B. Pongo esta pregunta aquí porque creo que puede ser necesario algo de combinatoria (muy simple) para encontrar una prueba para una estrategia simétrica.

Aquí está mi respuesta para A: uno de los enanos es elegido como "líder": sólo él puede encender la luz, y sólo él puede hablar con el ogro. Así que cada vez que la encienda (o no si ya lo está) y contar el número de veces que lo encendió. Todos los $99$ Los demás enanos sólo pueden apagar la luz una vez si la encuentran encendida (y luego no hacen nada más). Una vez que el líder haya encendido la luz $100$ veces (está apagada al principio), le dice al ogro que todos los enanos han visto la bombilla. Usando el hecho de que después de cualquier número de días, el ogro todavía traerá a cada enano de nuevo en la habitación, es fácil demostrar que los enanos ganarán.

Answer 1

Si los enanos son conscientes de la separación entre rondas, entonces los problemas son triviales, como puedes ver en la respuesta de @Arthur. Suponiendo que los enanos pierdan el sentido del tiempo, los problemas son mucho más interesantes. Una sugerencia para 2): Todos juegan asumiendo que la luz estaba apagada desde el principio. La única modificación en la estrategia: cada uno de los 99 enanos no líderes apaga la luz dos veces si la encuentra encendida. Si el líder encuentra la luz encendida durante su primera visita, entonces la deja encendida, y sabe que aquí es donde empezó el juego, porque él debe haber sido el primer visitante. Si la encuentra apagada, entonces la enciende (según la estrategia original), y asume que ya había cero o un visitante. En cualquier caso, después de tener que encender la luz por 198ª vez, el líder puede hacer la declaración.

La 198ª vez llega definitivamente: aunque la luz fuera apagada por un enano el primer día, se enciende después de cada vez que fue apagada, es decir, 198 veces. Cuando la luz se enciende por 198ª vez, no puede haber habido como máximo 98 enanos en la habitación antes de eso: de lo contrario, habrían apagado la luz 196 veces, además de que quizás hubo una ronda extra de encendido por parte del líder (lo que puede ocurrir si el líder fue llevado a la habitación el primer día y la luz estaba apagada).

Answer 2

Creo que no existe una estrategia simétrica para los prisioneros. Este problema apareció en Puzzles matemáticos, una colección para entendidos por Peter Winkler. En la solución aportada, fue más allá y ofreció una caracterización completa de todas las estrategias de éxito. He aquí el extracto exacto del libro, que Winkler advierte que es sólo "esquemático".

Centrémonos en una prisionera, digamos Alice. Su estrategia puede ser ser determinista y basarse únicamente en la secuencia de estados de luz que ha observado hasta ahora.

Supongamos que la estrategia de Alicia le exige (en alguna circunstancia) cambiar el estado (de la luz) después de encontrarla en el estado en el que la dejó por última vez. Entonces el adversario podría haberla llevado inmediatamente a la habitación, "desperdiciando" su visita anterior; en efecto, esta pieza de la estrategia de Alice sólo puede dar al adversario un extra adicional. Podemos suponer, por lo tanto, que Alice nunca cambia el estado cuando lo encuentra donde lo dejó por última vez.

A continuación, supongamos que Alicia tiene que abandonar en algún momento el estado tal y como lo encontró. Entonces afirmamos que podemos suponer que nunca actuará de nuevo. ¿Por qué? Porque si el adversario no quiere que ella actúe nunca más de nuevo, puede asegurarse de que ella nunca vea un estado diferente del estado en el que se encuentra ahora. Él puede hacer esto porque si Alice se convirtió en permanentemente inactiva, al menos uno de los estados (encendido o apagado) se repetirá infinitamente a menudo; supongamos que es el estado "apagado". Entonces él puede programar Alice para que vea "apagado" ahora y en cada visita posterior, por lo tanto, por el argumento anterior, ella nunca actuará de nuevo. Así, una vez más una vez más, el adversario siempre tiene la opción de silenciar a Alice por lo que podemos suponer que es su única opción.

Obviamente, Alice no puede entonces comenzar con la instrucción de dejar el estado tal y como lo encuentra, ya que en ese caso estará inactiva para siempre y nadie sabrá nunca que ha visitado la habitación.3 Digamos que debe debe encender la luz si está apagada y dejarla encendida si no lo está. Entonces no hará nada hasta que vuelva a encontrar la luz apagada. En ese momento, sólo podrá volver a encenderla o permanecer inactiva para siempre. Por lo tanto, se limita a encender la luz un número determinado de veces. $j$ (que también puede ser constante, e opciones). Llamamos a esta estrategia $+j$ donde $j$ i infinito. Argumentos similares se aplican si se le ordena que apague la luz en la primera visita, lo que lleva a la estrategia $-j$ .

La única posibilidad que queda es que se le ordena cambiar el estado de la luz en la primera visita, en cuyo caso debe proceder dependiendo de si encendió o apagó la primera luz. De nuevo, esto sólo da al adversario una opción adicional.

Estamos reducidos a que cada prisionero tenga una estrategia $+ j$ o $- j$ para varios $j$ . Si todos apagan (o encienden) las luces, nadie aprenderá nada. aprenderá nada; por lo tanto, podemos suponer que la estrategia de Alice es $+j$ y Bob es $- k$ .

Llegados a este punto, la pregunta está respondida. Toda estrategia es de la forma $\pm j$ para $j\in \mathbb N\cup \{\infty\}$ y está claro que ninguna de ellas funciona cuando la utilizan todos los presos. Aquí está el resto de la solución por si alguien tiene curiosidad.

Si Charlie enciende las luces, Alice nunca será capaz de distinguir si Bob y Charlie han terminado, y Bob y Charlie teniendo cada uno una tarea pendiente. Si Charlie apaga las luces, es Bob quien se quedará "a oscuras".

Juntando todo esto, tenemos que para que un preso pueda [ ] mientras todos los demás la apagan (o viceversa). De hecho, si su estrategia es $+j_1$ y los otros son $- j_2, \dots, -j_{n}$ t teniendo cada $j_i$ finito, pero al menos $2$ y $j_1$ g las otras $j_i$ 's menos el menor de ellos, es necesario y suficiente.

Answer 3

Para (2), pueden simplemente decidir que quien entre el primer día saldrá con la luz apagada, y entonces empezar cualquier estrategia real que estén planeando el segundo día.

Para (3), esto puede parecer hacer trampa, pero deja que el enano que sea elegido el segundo día se convierta en el líder.