Una pregunta acertijo sobre sombreros: ¿cómo demostrar que la solución estándar es óptima?

Question

Actualmente estoy escribiendo un ensayo sobre acertijos de sombreros, y para la sección de calentamiento introduzco algunos de los acertijos de sombreros finitos estándar. Uno de ellos procede de la siguiente manera:

Tú y dos amigos reciben cada uno un sombrero color beige o gris, determinado en cada caso por un lanzamiento de moneda. Nadie sabe de qué color es su sombrero, pero todos pueden ver los otros dos. Al sonar la campana, cada uno anunciará una suposición sobre su propio color o permanecerá en silencio. Los tres ganarán, como equipo, si al menos una persona adivina correctamente y nadie adivina incorrectamente. Perderán si todos permanecen en silencio o si alguien hace una suposición incorrecta. ¿Cuál es tu mejor oportunidad de ganar? Puedes idear una estrategia antes de lanzar las monedas y repartir los sombreros, pero por supuesto, no está permitida ninguna comunicación después de eso.

Por supuesto, puedes ganar con al menos cincuenta por ciento de probabilidad simplemente acordando que una persona designada diga "beige" sin importar qué, y nadie más diga nada. Pero en realidad, puedes hacerlo mejor al seguir la estrategia: si alguien ve dos sombreros del mismo color en los otros, entonces adivina el color opuesto para ti mismo. Esto será correcto en 6 de las 8 posibilidades, si lo piensas, por lo que tienes un 75% de probabilidades de ganar.

¿Cómo podemos demostrar que esta solución es óptima?

Me gustaría afirmar que ninguna estrategia que dirija a los jugadores a hacer un anuncio o a permanecer en silencio puede lograr un porcentaje de victoria mayor al 75%, pero me he dado cuenta de que en realidad no sé cómo probar esto.

Answer 1

Supongamos que tenemos alguna estrategia mixta para este rompecabezas del sombrero. Para cada una de las $8$ asignaciones posibles de sombrero y cada una de las $3$ personas involucradas, podemos preguntar sobre la probabilidad de que la persona adivine correctamente condicional a esa asignación de sombrero, y la probabilidad de que adivine incorrectamente. Después de especificar esto, habremos asignado una probabilidad a cada posible tupla (estado del mundo, precisión de la persona 1, precisión de la persona 2, precisión de la persona 3), donde el estado del mundo puede estar en una de las 8 disposiciones, y la precisión de cada persona se puede calificar como "correcta", "silenciosa" o "incorrecta".

Para una sola persona, su probabilidad esperada de ser correcta (condicional a dar un voto) es siempre de 0.5; es decir, la probabilidad total de todos los resultados en los que adivinan correctamente debe ser igual a la probabilidad total de todos los resultados en los que adivinan incorrectamente.

Para que un resultado lleve a un éxito, necesitamos al menos una suposición correcta y ninguna incorrecta. Entonces la probabilidad de éxito en el rompecabezas es a lo sumo la suma de P(correcto) en las tres personas.

Mientras tanto, un resultado sin éxito puede tener como máximo tres conjeturas incorrectas, porque solo hay tres personas. Entonces la probabilidad de fracaso es al menos un tercio de la suma de P(incorrecto) en las tres personas.

¡Pero para cada persona, P(correcto) = P(incorrecto)! ¡Así que sabemos que la probabilidad de éxito es como máximo tres veces la probabilidad de fracaso, lo que limita nuestra tasa de éxito en 0.75.

Answer 2

Supongamos que tú y tus dos amigos se llaman A, B, C.

Para cada caso, asigna una cadena de 3 letras para los colores que las personas reciben. Por ejemplo, TGG significa que A recibe beige mientras que B y C reciben gris.

Supongamos que cuando A ve dos sombreros beige, hay una probabilidad $A_T$ de que A adivine beige.
Cuando B ve dos sombreros beige, hay una probabilidad $B_T$ de que B adivine beige.
Cuando C ve dos sombreros beige, hay una probabilidad $C_T$ de que C adivine beige.

$Pr(\text{ganar|TTT})\le\text{número esperado de adivinanzas correctas}=A_T+B_T+C_T$
$Pr(\text{ganar|GTT})\le1-A_T$ ya que hay una probabilidad $A_T$ de que A adivine incorrectamente
$Pr(\text{ganar|TGT})\le1-B_T$ ya que hay una probabilidad $B_T$ de que B adivine incorrectamente
$Pr(\text{ganar|TTG})\le1-C_T$ ya que hay una probabilidad $C_T$ de que C adivine incorrectamente

Por lo tanto, $Pr(\text{ganar|TTT})+Pr(\text{ganar|GTT})+Pr(\text{ganar|TGT})+Pr(\text{ganar|TTG})\le3$ entonces $Pr(\text{ganar|al menos dos beige})\le3/4$. De manera similar, $Pr(\text{ganar|al menos dos gris})\le3/4$ entonces $Pr(\text{ganar})\le3/4$.

Answer 3

Hay 8 estados del mundo. Supongamos que (con estrategias deterministas) ganan en 7 de esos 8 estados.

Entonces ganan en cada estado donde el sombrero de A es dorado o en cada estado donde el sombrero de A es beige. Supongamos lo primero.

Se deduce que A nunca adivina beige. De la misma manera, hay un color que B nunca adivina y un color que C nunca adivina. Dejemos que los colores que nunca adivinan sean X, Y, Z. Se deduce que pierden en el estado XYZ, así que (porque ganan en 7 estados) deben ganar en todos los demás.

Ahora consideremos qué sucede en el estado X'Y'Z' (con todos los colores cambiados a sus opuestos). Esto no es lo mismo que XYZ, así que deben ganar en este estado, lo que significa que alguien adivina correctamente en este estado. Que sea A. Entonces cada vez que A vea Y'Z', debe adivinar X'. Pero entonces se equivoca la mitad del tiempo.

Editado para añadir: Un razonamiento similar (y/o una generalización del argumento de RavenclawPrefect) muestra que la probabilidad de ganar está limitada por encima por $n/(n+c-1)$ cuando hay $n$ jugadores y $c$ colores de sombrero igualmente probables.

Answer 4

Estoy haciendo esto una respuesta aparte aunque realmente es solo una versión concisa de mi respuesta anterior:

Supongamos que hay 7 estados ganadores. Sea XYZ un estado ganador en el que tanto A como B nombran colores. Entonces X'YZ y XY'Z son ambos estados perdedores, contradicción. Por lo tanto, en cualquier estado ganador, como máximo un jugador nombra un color. Por lo tanto, hay como máximo 4 estados ganadores (indexados por el conjunto posiblemente vacío de jugadores que nombran colores en ese estado), contradicción.

Answer 5

Considera el juego con $n$ jugadores e identifica las posibles asignaciones de colores de sombrero con los vértices del grafo del hipercubo de $n$ dimensiones. Dada una estrategia (determinística), sea $S$ el conjunto de vértices donde la estrategia tiene éxito.

Afirmo que para cualquier vértice $v$, los $n+1$ vértices en $N^+(v)=\{v\}\cup N(v)$ no pueden todos estar incluidos en $S$: si $N^+(v)\subseteq S$, entonces en la situación $v$, la estrategia debe hacer que todos permanezcan en silencio, ya que cualquier posible anuncio del jugador $i$ es inconsistente ya sea con $v$ o con el $u\in N(v)$ que difiere de $v$ en la coordenada $i$. Pero entonces la estrategia falla en $v$ después de todo, lo cual es una contradicción.

Esto implica $$|S|\le\frac n{n+1}2^n:$$ si la probabilidad de que un vértice elegido al azar $v$ pertenezca a $S$ es $p>n/(n+1)$, entonces por linealidad de la esperanza, el número esperado de elementos de $N^+(v)\cap S$ es $(n+1)p>n$, por lo tanto existe un vértice $v$ tal que $|N^+(v)\cap S|\ge n+1$, lo cual es una contradicción.

Para $n=3$, obtenemos $|S|\le6$.

Recíprocamente, si $S$ es un conjunto de vértices tal que $N^+(v)\nsubseteq S$ para todos los $v$, entonces existe una estrategia que tiene éxito en $S$, definida de la siguiente manera. Para un jugador dado, sea $u$ y $v$ los dos vértices vecinos consistentes con lo que el jugador observa. Si exactamente uno de $u$ y $v$ pertenece a $S$, digamos $w$, entonces el jugador anuncia el color correspondiente a $w$; de lo contrario, el jugador permanece en silencio. Si $v\in S$, entonces en la situación $v$, ningún jugador puede anunciar un color incorrecto, y la condición $N^+(v)\nsubseteq S$ garantiza que todos los jugadores no pueden permanecer en silencio.