Enigma : de magos, enanos y sombreros

Question

Tengo un enigma bastante difícil que requiere amplios conocimientos en matemáticas, y pensé que algunos podrían apreciarlo.

Un malvado hechicero tiene en prisión a un número infinito de enanos (contablemente infinito). Los reúne y les dice : Mañana, Te alinearé para que el primero de vosotros vea a todos los demás enanos. El segundo verá a todos menos al primero, etc... Entonces, pondré un sombrero en cada una de sus cabezas , negro o blanco. Nadie puede ver su propio sombrero, ni el de los que le preceden. Pero cada enano puede ver los sombreros de los que le siguen (tienen buena vista). Y entonces, empezando por el primer enano, preguntaré que cada uno de ustedes me diga exactamente una palabra, "Negro" o "Blanco" . Pero tendrás que susurrármelo al oído, para que nadie más pueda escucharlo . Luego, cuando esté hecho (el brujo es bastante rápido) liberaré a los enanos que acierten el color de su sombrero y mantendré al resto encarcelados.

Los enanos se reúnen después de la reunión, y encuentran una estrategia para que sólo un número finito permanece encarcelado . ¿Qué han decidido?

P.D: No hay ningún truco. No se da ninguna información de un enano a otro cuando dicen "Negro" o "Blanco" al hechicero. No gruñen ni esperan un tiempo determinado. Los enanos no pueden escapar ni hacer nada sospechoso.

Sin embargo, las matemáticas implican algunas... matemáticas ambiguas =)

Answer 1

Aviso de spoiler: Este es un rompecabezas divertido - la solución sigue; no sigas leyendo si quieres intentarlo tú mismo :-)

Los enanos, más bien pensativos, reflexionan profundamente sobre su situación. Después de haber estado encarcelados durante mucho tiempo (¿infinito?), se dan cuenta de que sólo pueden liberarse externamente si primero se liberan internamente. No deben dejar que su largo cautiverio les robe su libertad interior. A pesar de haber estado encarcelados desde que tienen uso de razón, se dan cuenta de que sólo pueden escapar si realmente creen que pueden elegir. Y por eso abrazan el axioma de la elección.

Utilizando el axioma de elección, eligen (de antemano) un representante de cada clase de secuencias binarias (contablemente) infinitas bajo la relación de equivalencia que relaciona todas las secuencias que difieren sólo en un número finito de lugares. A continuación, cada enano determina la clase de equivalencia de la asignación real del sombrero y adivina que lleva el sombrero especificado por el representante elegido para esa clase.

Answer 2

Nota: Esto es para la versión en la que los enanos pueden escuchar lo que los otros han dicho.

1)

Para infinitas tuplas $(d_1, d_2, \dots )$ con cada coordenada $d_i$ siendo Negro/Blanco, los enanos se ponen de acuerdo sobre los representantes para cada clase de la relación de equivalencia: $x$ relacionado con $y$ si y sólo si $x$ y $y$ difieren en un número finito de posiciones.

También están de acuerdo en que Negro = par y Blanco = impar.

El primer enano llama a la paridad del número de posiciones la tupla formada por el resto de los enanos, difiere del representante de la clase a la que pertenece esa tupla.

---

2)

Una prueba posiblemente diferente es que el grafo infinito formado por las tuplas (dos tuplas son adyacentes si difieren exactamente en una posición) es $2$ -colorables. Los enanos se ponen de acuerdo para colorear el gráfico y el primer enano dice el color del vértice correspondiente a la tupla formada por el resto de los sombreros.

Que el gráfico es $2$ -colorables se desprenden de la maravillosa teorema (demostrado con argumentos de compacidad) que un gráfico infinito es $k$ -colorables si cada subgrafo finito lo es.