Adivinanza de sombreros con estuche para 100 sombreros

Question

Mi pregunta se refiere a la pregunta que se ha formulado aquí: Una adivinanza sobre cómo adivinar los colores de los sombreros (que no está entre las comúnmente conocidas)

$100$ A los presos se les pone un sombrero en la cabeza, que puede ser rojo o azul. Los colores son elegidos al azar por $100$ lanzamientos de moneda justos e independientes. A continuación, cada prisionero puede adivinar el color de su sombrero (rojo o azul) o pasar. Los prisioneros pueden verse, 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 el reparto de sombreros, los prisioneros son informados de las reglas y pueden acordar una estrategia. Los prisioneros ganan si ninguno se equivoca y al menos uno acierta. ¿Qué estrategia deben utilizar los prisioneros para que la probabilidad de ganar sea máxima?

sobre esta cuestión encontraron respuesta para $n=2^k-1$ y $2^k$ pero mi pregunta es ¿cómo puedo resolver para otros casos? específicamente para $n=100$

Answer 1

En general es un problema abierto encontrar la probabilidad óptima de éxito para $n$ presos cuando $n\notin\{2^k-1,2^k\mid k\in \mathbb N_+\}$ excepto para todos los valores de $n$ hasta $9$ . Los límites más conocidos para $n$ hasta $33$ figuran en la tabla de la respuesta enlazada.

Aunque no se conoce una estrategia óptima, la siguiente es una estrategia bastante buena. Encontrar el mayor número entero $m$ tal que $m\le n$ y $m=2^k-1$ para algunos $k$ . La primera $m$ presos utilizan la estrategia del código Hamming, mientras que los restantes $n-m$ Los prisioneros pasan. Esto da una probabilidad de fracaso de $1/(m+1)$ que es como máximo $2/(n+1)$ . Dado que se puede demostrar que cada estrategia tiene una tasa de fracaso de al menos $1/(n+1)$ , esta estrategia está dentro de un factor de $2$ de óptimo.

Para $n=100$ el porcentaje de éxito es $63/64\approx 98\%$ .

Ahora voy a demostrar que cada estrategia debe fallar con una probabilidad de al menos $1/(n+1)$ . Fija una estrategia y tabula el número de personas que se equivocan en cada una de las $2^n$ escenarios posibles. Siempre que los prisioneros ganan, hay al menos un acierto, y siempre que los prisioneros pierden, hay como máximo $n$ suposiciones incorrectas. Además, cada prisionero acierta de media la mitad de las veces que adivina, por lo que, en todos los casos, el número de aciertos y errores debe ser igual. Supongamos que $W$ el número de situaciones ganadoras y $L$ el número de situaciones perdedoras, la discusión anterior implica $$ W\le nL, $$ que puede manipularse para demostrar que $$ P(\text{losing})=\frac{L}{W+L}\ge \frac{1}{n+1}. $$