Tenemos un número infinito de presos enumerados $\{1, 2, \dots\}$, y en cada uno de los prisioneros hay un sombrero de azul o de color rojo. El $n$th prisionero ve los sombreros de los presos $\{n+1, n+2, \dots\}$. Un guardia le pide a cada prisionero en la sucesión, comenzando con el prisionero $n=1$, "¿Cuál es el color de su sombrero?" Si a cualquier preso que se produce un error, el guardián se ejecuta el recluso. Los presos no pueden comunicarse. Qué estrategia debe a los prisioneros uso (discutido antes en el momento en que los sombreros están puestos en ellos), para finalizar con un número finito de ejecuciones?
Respuestas
¿Demasiados anuncios?
Este es un clásico acertijo, cuya solución sorprendentemente requiere el axioma de elección como se describe aquí.
La solución, sin embargo, es corto y listo. Codificar los colores en $0$$1$, y definir la relación de equivalencia en $2^\Bbb N$, $\langle x_i\rangle\sim\langle y_i\rangle$ si y sólo si hay algún $k$ tal que para todo $n\geq k$, $x_n=y_n$. Usando el axioma de elección de los presos elegir un representante de cada clase de equivalencia.
En su turno, $n$- th prisionero busca el representante de la clase de montaje de la cadena de sombreros se ve por delante, suponiendo que todos los sombreros a él son de color azul. Ya que todos los presos siguen el mismo representante de adivinar su propio color, se garantiza que después de un número finito de muertes, el representante y la moda de selección de sombreros por el guardián de acuerdo, y todos los demás va a sobrevivir.
-- "Las necesidades de muchos, son mayores que las necesidades de unos pocos".
Milo Brandt
Puntos
23147
Nos puede salvar a todos, pero un prisionero. La respuesta es un poco menos elegante que los de Asaf, pero yo valor de la vida humana sobre la matemática de la elegancia.
En particular, definir la simétrica de la operación de suma $$A\oplus B=(A\cup B)-(A\cap B)$$ que esencialmente dice $x\in (A\oplus B)$ si es en exactamente uno de $A$ o $B$. En virtud de ello, el powerset de $\mathbb{N}$ es un espacio vectorial sobre $\mathbb{F}_2$ de dimensión infinita. Desde el conjunto de singleton $S=\{\{n\}:n\in \mathbb{N}\}$ es linealmente independiente, debe haber alguna base $\mathscr B$ contiene $S$ (Oh, hola axioma de elección). Por lo tanto, podemos elegir alguna función lineal $f:\mathscr P(\mathbb N)\rightarrow \mathbb{F}_2$ donde $f(s)=1$ cualquier $s\in S$. A continuación, el primer prisionero que se dice $f(R)$ donde $R$ es el subconjunto de los prisioneros delante de él vistiendo sombreros rojos (numeradas $1$ hasta el infinito - no cuenta a sí mismo, porque él no puede ser salvado de todos modos). La siguiente persona tiene dos hipótesis - ya sea que él está usando un sombrero rojo o no. Si él está usando un sombrero rojo, a continuación, defina $R_2$ como el conjunto de los presos que él puede ver con sombreros rojos, excepto a sí mismo, y $R_2'$ como el mismo conjunto, incluyendo a él mismo. Desde $R_2 \oplus \{2\} = R_2'$, claramente $f(R_2)\neq f(R_2')$. Por lo tanto, el segundo prisionero figuras de su propio sombrero de color como lo de $f(R_2)$ o $f(R_2')$ coincide con el primer preso del cálculo de $f(R)$. Cada preso más allá de que conoce el sombrero de color de todos los otros prisioneros esperar a sí mismo y se puede proceder en consecuencia. Esto funciona para cualquier (no necesariamente finita) número de colores de sombrero.
Este es el mismo que el de la solución cuando hay sólo un número finito de prisioneros, pero el axioma de elección no sería necesaria, ya que, en la misma suma, $P(\{1,\ldots,n\})$ $\{\{1\},\{2\},\ldots,\{n\}\}$ como base, y por lo tanto no hay una única función lineal de tomar cada uno de los elementos de a $1$ (que pasa a ser el cómputo de la paridad).
Por supuesto, si incluso un preso tornillos hasta su cálculo...
