Infinitos prisioneros con sombrero donde los prisioneros no conocen su posición.

Question

El rompecabezas de los prisioneros infinitos con sombreros es el siguiente. Tenemos un grupo contablemente infinito de prisioneros numerados $\{1, 2, \dots\}$ Cada uno de ellos lleva un sombrero blanco o un sombrero negro. El $n$ El preso sólo puede ver los sombreros de los presos $\{n+1, n+2, \dots \}$ . Un guardia pregunta sucesivamente a cada preso, empezando por el primero, de qué color es su sombrero. Si el prisionero se equivoca, es ejecutado en el acto. Supongamos que los prisioneros no pueden oír las respuestas de los que han sido preguntados antes que ellos. Encuentra una estrategia para los prisioneros que garantice que sólo un número finito de ellos sea ejecutado.

Hay una respuesta estándar utilizando el axioma de elección (que se sabe que es necesario). Codifica los sombreros como $0, 1$ y considerar la siguiente relación de equivalencia en el espacio de todas las secuencias contables $2^\mathbb{N}$ . Dejemos que $(x_i) \sim (y_i)$ si y sólo si existe algún $k \in \mathbb{N}$ tal que $x_n = y_n\ \forall n > k$ . En otras palabras, dos secuencias son equivalentes si coinciden después de algún punto finito. Elija un representante de cada clase de equivalencia: como cada prisionero puede ver todos los sombreros menos un número finito, sabe a qué clase de equivalencia pertenece la fila de prisioneros. Suponiendo que un prisionero determinado sepa que es $n$ en la fila, simplemente responden al $n$ del representante, y ya tenemos nuestra solución.

Parece que esta solución falla si los presos no saben en qué lugar de la fila se encuentran. Consideremos una secuencia de sombreros $(x_i)$ y construir una nueva secuencia $(y_i) = \{0, \dots, 0, x_1, x_2, \dots \}$ rellenando un número finito de ceros al frente. En general, $(x_i)$ y $(y_i)$ no estarán en la misma clase de equivalencia y, por lo tanto, si un prisionero no sabe en qué número se encuentra en la línea, hay ambigüedad en cuanto a qué representante debe elegir.

Se podría considerar "Parcheando" la solución dejando $(x_i) \sim (y_i)$ si existen subsecuencias arbitrariamente grandes en las que coinciden, pero esto permite secuencias de sombreros en las que muere un número infinito de prisioneros:

$(x_i) = \{0, *, 0, *, *, 0, *, *, *, 0, \dots \}$

$(y_i) = \{1, *, 1, *, *, 1, *, *, *, 1, \dots \}$

donde las secuencias se definen para coincidir en el $*$ elementos. Sospecho que me estoy perdiendo algo obvio y que hay una manera fácil de resolver el caso en el que los prisioneros no conocen su número en la fila. ¿Qué opinas?

Answer 1

Creo que se puede parchear el argumento de otra manera, declarando dos secuencias $(x_i)$ y $(y_i)$ equivalente si existen números enteros $k$ y $N$ tal que $x_{i+k} = y_i$ para todos $i \ge N$ es decir, si se introduce la equivalencia de desplazamiento. Ahora escoge un elemento $(x_i)$ fuera de la clase de equivalencia que se observa. Si la cola $(x_i)_{i \ge n}$ no determina de forma única su posición en la secuencia, esto significa que existe $N$ y $k \ne 0$ con $x_{i+k} = x_i$ para $i \ge N$ es decir, que la secuencia es finalmente periódica. Sin embargo, en ese caso para $n \ge N$ no importa la posición del $n$ -a la elección del prisionero, siempre que esté en la cola periódica de la secuencia, por lo que de nuevo sobreviven todos menos un número finito de ellos.