Una adivinanza sobre cómo adivinar los colores de los sombreros (que no está entre las comúnmente conocidas)

Question

Esta es una adivinanza que escuché hace poco, y mi pregunta es si alguien sabe por casualidad la solución. Lo pregunto por curiosidad más que por otra cosa.

Así que aquí está. El acertijo es una de las innumerables variaciones del rompecabezas "los prisioneros tienen que adivinar el color de su sombrero". $n$ A los presos se les pone un sombrero en la cabeza, que puede ser rojo o azul. Los colores son elegidos al azar por $n$ lanzamientos de monedas justos e independientes. Luego, cada prisionero puede adivinar el color de su sombrero (rojo o azul) o pasar. Los prisioneros pueden verse entre sí, pero no oír las llamadas de los demás y, por supuesto, no tienen ningún otro medio de comunicación. Esto significa que cada llamada sólo puede depender del color del sombrero de los demás prisioneros. Sin embargo, antes de que comience la distribución de los sombreros, los prisioneros son informados de las reglas y pueden acordar una estrategia. Los prisioneros ganan si ningún prisionero se equivoca y al menos uno acierta. ¿Qué estrategia deben utilizar los prisioneros para que la probabilidad de ganar sea máxima?

Algunas observaciones:

• Una estrategia sencilla es que un jugador sólo adivine y todos los demás jugadores pasen, de modo que la probabilidad máxima sea al menos 1/2. Para $n=2$ esta estrategia es óptima.
• Para $n=3$ Hay una estrategia que gana en 6 de cada 8 casos: Cuando un jugador ve (rojo,rojo) adivina el azul, para (azul,azul) adivina el rojo, y en caso contrario pasa. En términos más generales, esto demuestra que la probabilidad máxima es de al menos 3/4 para $n\ge 3$ .
• Es posible demostrar que cualquier estrategia falla para al menos 2 configuraciones de color de sombrero (a menos que $n=1$ ), lo que demuestra que la estrategia anterior es óptima para $n=3$ .
• Para $n=4$ hay más de $10^{15}$ estrategias, y para $n=5$ se trata de $10^{38}$ estrategias, lo que hace bastante inviable el uso de un programa informático de fuerza bruta (tal vez para $n=4$ es posible cuando se explotan las simetrías obvias).
• Si se cambian ligeramente las reglas prohibiendo a los jugadores pasar, entonces la probabilidad máxima de ganar es siempre 1/2. Este es un pequeño y agradable ejercicio.

En realidad escuché el acertijo sólo para $n=3$ y luego pensó en el general $n$ . Así que es muy posible que no haya una solución agradable.

Answer 1

Después de escribir esta respuesta encontré este documento que llega a las mismas conclusiones y además generaliza el problema a $q$ colores del sombrero. De todos modos, estoy publicando la respuesta para tenerla aquí en math.SE en forma autocontenida.

---

Como se describe en el artículo de Wikipedia que Gerry enlazó y este libro referencias, una estrategia óptima concentra las conjeturas erróneas en el menor número posible de configuraciones. Cada jugador individual adivina incorrectamente exactamente la mitad de las veces si no pasa, e idealmente estas adivinanzas incorrectas deberían concentrarse todas en configuraciones en las que todo el mundo adivina incorrectamente, mientras que las adivinanzas correctas deberían repartirse idealmente una por configuración.

Denotemos el conjunto $\def\red{\text{red}}\def\blue{\text{blue}}\def\pass{\text{pass}}\{\red,\blue\}$ de los colores del sombrero por $H$ y el conjunto $\{\red,\blue,\pass\}$ de las conjeturas de $G$ . A continuación, una estrategia para $n$ Los prisioneros son una función $H^n\to G^n$ de manera que el $k$ -ésima entrada del valor no depende de la $k$ -ésima entrada del argumento.

Dada una estrategia, nos interesa la proporción de vectores de $H^n$ para el que la estrategia prescribe un valor que no es la constante $\pass$ vector y en el que todas las entradas no pasadas coinciden con las entradas correspondientes del argumento. Llamemos a estos vectores buenos y a los demás malos.

Adyacente a todo vector bueno $g\in H^n$ es al menos un vector malo $b\in H^n$ que difiere de $g$ sólo en el color del sombrero de uno de los presos que adivinen correctamente para $g$ (de los cuales hay al menos uno). A la inversa, dado un subconjunto $S\subseteq H^n$ de vectores malos tal que cada vector es adyacente a al menos un vector malo en este sentido, podemos hacer que todos los demás vectores sean buenos asignando un vector malo adyacente a cada uno de ellos (arbitrariamente si hay más de uno) y dejando adivinar sólo al prisionero en cuya entrada difieren los dos vectores.

Así, una estrategia óptima está definida por un subconjunto mínimo $S\subseteq H^n$ tal que todos los vectores de $H^n$ son adyacentes a al menos un elemento de $S$ . Este subconjunto mínimo se denomina código de cobertura óptimo binario de longitud $n$ y el radio $1$ y el número de vectores en dicho subconjunto mínimo se denota por $K(n,1)$ . Esta tabla (enlazado desde esta página ) da los límites conocidos de $K(n,1)$ hasta $n=33$ .

Para $n=2^k-1$ los códigos Hamming descritos en el artículo y en el libro son códigos óptimos de cobertura binaria con $2^{n-k}$ vectores, con probabilidad de ganar $1-2^{n-k}/2^n=1-2^{-k}=n/(n+1)$ . Para otros valores de $n$ los valores de $K(n,1)$ sólo se conocen hasta $n=9$ y para $n$ un poder de $2$ el límite inferior de $K(27,1)$ se ha mejorado recientemente.

Answer 2

El rompecabezas se discute en http://en.wikipedia.org/wiki/Hat_Puzzle en la sección sobre la versión de Ebert y los códigos de Hamming.