$N$ perfecto lógicos usando sombreros

Question

Una vez me encontré con el siguiente acertijo: (suponga $N$ a ser muy grande)

Hay $N$ perfecto lógicos, dispuestos en una fila vertical. Son permite elaborar estrategias antes de que el juego, durante el juego son prohibidos a partir de la comunicación. En el juego, las luces están apagadas, y un sombrero, ya sea rojo o azul, se coloca sobre la cabeza de cada uno de los los lógicos. Las luces están encendidas; cada lógico puede ver el sombrero los colores de todas las personas en frente de él, él no puede ver el color de su propio sombrero, o la gente detrás de él. Comience con la persona en el de nuevo, cada lógico tiene que llamar a un color (escuchado por todos). Si su propio sombrero es de ese color, él está a salvo, de lo contrario, en silencio muerto. La misma se realiza por la siguiente persona, y así sucesivamente, a la derecha hasta la primera persona. Cómo muchos de los lógicos pueden garantizar a guardar, independientemente de la inicial de colores, o cualquier probabilidad?

La respuesta fue simple. La primera lógico sería sacrificar su vida. Él iba a rojo si hay un número par de sombreros rojos en frente de él, y negro, si hay un número impar de sombreros rojos. Después de él, cada lógico correctamente puede decir el color de su propio sombrero.

Me decidí a dar a la pregunta de un giro. Supongamos que hay un hombre ciego entre los lógicos. Su vida vale tanto como cualquier otra persona, y se le coloca al azar en la cola. Cómo muchos de los lógicos pueden garantizar a guardar?

El mismo enfoque no funcionaría porque, si el hombre ciego se dio el color equivocado, no sólo a él, sino a toda la gente en frente de él le dará el color equivocado, ya que dependen de su información también.

Después de mucho pensar, finalmente me di con esta solución.

Encontrar el más pequeño de $n$ tal que $3(n+1)+2^n \geq N$. El primer $3(n+1)$ de la gente (de la) serán las sacrificar sus vidas (Grupo a), y el resto ($2^n$) van a tratar de averiguar su propio sombrero de colores (Grupo B). Comenzando con la parte de atrás del Grupo B, asignar a cada una lgica ($n+1$) dígitos del número binario, a partir de una cadena de ceros, y la adición de $1$ para obtener el siguiente lgica de la ID. Tenga en cuenta que el primer dígito siempre será un $0$.El primer Grupo se divide en $n+1$ subgrupos de $3$ lógicos, cada uno de ellos. A cada subgrupo se le asigna un normal número decimal $1,2,3,\cdots$, y así sucesivamente (de nuevo comenzando desde la parte posterior). Deje que el subgrupo número de una lgica ser $k$

Cuando se inicia el juego, cada Grupo Un lógico se mira toda la gente que en el Grupo B, cuyas $k^{th}$ dígito binario es $1$. De estas personas, si hay un número par de sombreros rojos, él dirá rojo, de lo contrario dirá azul. El otro $2$ lógicos en su subgrupo se dan exactamente la misma información que la primera. Esto es necesario para confirmar que él está diciendo la verdad, si hay una discrepancia entre el $3$ de las respuestas, la información dada por $2$ es correcta, y la tercera es la ciega. La misma es realizada por todas las personas en el Grupo A.

Las personas del Grupo B sólo tratar de averiguar su propio sombrero de colores. Cada lógico ha $n+1$ maneras de averiguar su propio sombrero de color. Si todos los datos dados no llevan a la misma respuesta, él sabe que el ciego está detrás de él y ya ha llamado fuera una mentira. A continuación, se puede utilizar la primera lógico de la información (primero en el Grupo a y la fila) a la figura de su propio color, ya que el ciego ha de asegurarse sido contados por esa persona.

Es mi enfoque correcto y hay uno más rápido? Espero que mi pregunta es bastante clara.

Nota: El ciego sabe donde está colocado, pero nadie conoce su posición.

Answer 1

Creo que el código de Hamming con extra de paridad proporciona una solución. Si hay $2^n$ logcians, esto requiere sacrificar $n$ de ellos (cada uno con probabilidad de $1/2$). Vamos a la parte trasera $n$ ser la paridad de los bits de código, llamados por los lógicos. El resto puede ejecutar la detección de error en el esquema. Si no hay bits son un mal camino, ya sea porque el ciego lógico no ha hablado, o porque él estaba en lo correcto, cada persona puede encontrar el sombrero de color que no tiene errores. Si un bit está mal ya, uno de los sombrero de opciones hará dos errores, que son detectables por el código.

Si los que están detrás de el ciego lo puede ver donde está, puede salvar a todos, pero tal vez 2. La parte trasera lógico anuncia el color de los ciegos el hombre del sombrero. El próximo anuncia la paridad de todos los sombreros que él puede ver. Todo el mundo es salvado por la solución original. Si el ciego está en la parte de atrás, no es un problema. Si el ciego es el segundo, el primero anuncia el color debe decir para la paridad.

Su enfoque es correcto, pero no óptima. Para un gran $n$, se requiere el sacrificio de la $3 \log_2 n$ lógicos, mientras que mi primer párrafo requiere el sacrificio de la $\log_2 n$. Como usted dice, que se van repitiendo a cada bit de tres veces, lo que garantiza la respuesta correcta será una mayoría si sólo uno de los bits es volteado. Esta explota el hecho de que la distancia de Hamming entre el $000$ $111$ es de tres. Voltear un poco dejará a distancia $1$ a partir de la cadena correcta y la distancia $2$ a partir de la cadena incorrecta. El código que he citado en el comienzo, hace lo mismo con $n$ bits de palabras de código. Todos los aceptables son, al menos, una distancia de $4$ desde cualquier otro, así que usted puede corregir errores de bit únicos y detectar dos errores de bit.

Agregó: podemos hacerlo con un máximo de tres siendo sacrificados. Hacer la clásica solución que no implique el ciego lógico. La parte trasera de una adivina el color que haría que el número de sombreros rojos incluso, y se sacrifica con probabilidad $1/2$. Cada uno agrega a su vez el número de sombreros rojos ve a la cantidad de glóbulos rojos conjeturas que ha escuchado. Si incluso, adivinaba azul. Si es impar, lo adivina rojo. Todos (excepto tal vez la primera) será el correcto. Ahora añadimos en el ciego lógico, que conjeturas al azar. Si el ciego es el hombre equivocado, el siguiente después de que él sea malo, sino que restaura la paridad y el resto son salvos. Ahora nos perdemos en la mayoría de los tres (el primero, el hombre ciego, y la siguiente).

Answer 2

Esta es la tercera versión de esta respuesta, dando incluso una solución más general que los dos anteriores.

Parece que Saphrosit la solución es correcta. Además, tras Mercio comentarios a continuación, puede ser simplificado considerablemente, sacrificando no más de $2B+1$ lógicos si $B$ de ellos son ciegos. Sorprendentemente, este es el caso, sin embargo muchos de los colores de los sombreros pueden tener.

Supongamos que los sombreros de tomar los colores de $\mathbb{Z}_c$ y deja que el sombrero de colores se $h_1,\ldots,h_N$, cada una de las $h_i\in\mathbb{Z}_c$, y deje $s_k=\sum_{i=k+1}^N h_i\pmod c$ ser la suma modular de los sombreros en frente de la lgica $k$.

Definimos $g_k$, el color "adivinado" por la $k$th lógico, de la siguiente manera:

• Un ciego lógico suponer arbitrariamente.

• Si la primera lógico no es ciega, $g_1=s_1$.

• Para la otra no-lógicos ciegos, $g_k = g_1 - s_k - \sum_{i=2}^{k-1} g_i \pmod c$, para todos los $k\geqslant2$. Si $g_1=s_1$ y, para cada una de las $i$ en el rango $2\leqslant i<k$,$g_i=h_i$,$g_k=h_k$.

Si la primera lógico es ciego y adivina un color diferente de$s_1$,$g_2=h_2+(g_1-s_1)\neq h_2$, pero los lógicos adivinar correctamente porque es todavía el caso de que $g_1-g_2=s_1-h_1$.

Si lgica $b>1$ es ciego y no acierta, a continuación,$g_{b+1}=h_{b+1}+(h_b-g_b)\neq h_{b+1}$, pero de nuevo los lógicos posteriores adivinar correctamente.

Por lo tanto, si $\mathcal{B}$ es el conjunto de índices de los lógicos ciegos, $$ \{k:g_k\neq h_k\} \;\subseteq\; \{1\} \:\la copa\: \{b:b\in\mathcal{B}\} \:\cup\: \{b+1:b\in\mathcal{B}\}. $$

Una pregunta: ¿se Puede hacer mejor que $2B+1$ si $B$ es grande en comparación a $N$ (es decir, si $B>\log N$ o $B>\sqrt{N}$ o algo)?

Answer 3

Yo no soy un experto en la teoría de la codificación, así que por favor tengan paciencia conmigo si mi solución no está formalmente indicada, pero creo que he encontrado una solución que requiere de un constante número de sacrificios: $6$ (en el peor de los casos). La idea es la siguiente:

El ciego lógico es enseñado a decir $0$ en cada caso.
Las primicias $4$ lógicos son los responsables de proporcionar la paridad de información: las primicias $2$ dar un bit de paridad para el conjunto de la cola de $N-4$ lógicos, mientras que los segundos $2$ dar un bit de paridad para los lógicos en una posición. Es necesario que cada bit se repite dos veces en el caso de que el ciego está entre los primeros a $4$ (redundancia permitirá a todos a entender que es la correcta bits). Claramente, el bit de paridad de los lógicos en posición impar se pueden deducir.

Todos los demás lógicos, será motivo de la siguiente manera: se supone que todos los que ya hablamos era el correcto. Si lo que ves es coherente con la inicial de la paridad de señalización (es decir, si la deducción de su bits usando el total del bit de paridad se obtiene el mismo resultado como deducir su bits utilizando sólo el par/impar bit de paridad) a continuación, sólo decir que la broca se deduce. De lo contrario se deduce que el ciego fue justo antes de usted, así que por voltear su poco se puede entender su, y como consecuencia de su bits. Acaba de decir la correcta.

Para demostrar que el máximo número de sacrificios en realidad es $6$ hay un par de afirmaciones que deben ser probados:

• ¿por qué un conflicto entre los bits de paridad y bits siguientes permite concluir que el ciego lógico es exactamente la anterior a la actual?

• por qué, después de detectar el error y la identificación de el ciego, podemos estar seguros de que no hay otros enfrentamientos se producen?

Para responder, vamos a utilizar una parte del lenguaje formal: vamos a $A$ el conjunto de las primicias $4$ lógicos y $B$ el conjunto de la subsiguiente $N-4$ lógicos. Podemos dar $B$ el discurso de orden (el primero es el que habla primero). Deje $hat: B \to \{0,1\}$ ser el "color" de el sombrero de lgica $x \in B$.
Deje $b$ ser ciegos lógico. Supongamos $b \in B$ (de lo contrario todos los lógicos, en $B$ va a dar la respuesta correcta) y $hat(b) = 1$ (de lo contrario va a adivinar su color y no se genera ningún error). W. l.o.g. podemos suponer $b = x_0 \in B$ si $b=x_i$, para todos los $j < i$, lgica $x_j$ va a dar la respuesta correcta.
Por último, vamos a $p_t$ el total de bits de paridad y $p_e$ el bit de paridad considerando sólo las posiciones.

Lgica $x_1$ detectará un conflicto mediante $p_e$ ($x_0$ y $x_1$ ver el mismo número de "incluso" los lógicos) de modo que se puede deducir que $x_0 = b$$hat(b)=1$. Utilizando, a continuación, $p_t$ puede deducir de su color.

El reclamo es que no hay otros lógico detectará un choque.
De hecho la respuesta de $x_0$ está en conflicto con tanto $p_t$ $p_e$ $x_1$ es capaz de proporcionar la respuesta correcta; como resultado, $p_t$ $p_e$ puede ser visto como "disparidad" bits (es decir, los bits para que el número total de $1$s es impar). El uso de estos bits de $x_2$ siempre deducir el color equivocado, en realidad corregir el error, como un segundo error hará $p_t$ $p_e$ a ser de nuevo bits de paridad. Todos los lógicos posteriores no notará ningún choque y será capaz de proporcionar la respuesta correcta.

Por supuesto, esta solución tiene sentido sólo si $N>>6$ pero tiene la ventaja de requerir un número constante de los sacrificios.

Lo siento por la forma en que la solución está formulado, estoy seguro de que la codificación teórico será capaz de decirlo en una más compacta y elegante manera (suponiendo que yo no tenía ningún error).

Answer 4

como los lógicos están autorizados a discutir antes de que el juego comienza, se decide que cada alternativo hombre se nota el color de la lgica justo antes de él, ahora bien, si el color de la lgica del sombrero que está en tela de juicio es la misma que la de el sombrero de la lgica en su frente, él será salvado demasiado de lo contrario, la lgica justo antes de que él se guarda. pero si se puede varry sus gritos que si alguien grita para largo esto significa que el color del sombrero de la lgica antes de la lgica antes que él, es el mismo y uno grita por un tiempo más corto que los colores son diferentes en este caso al menos n-1 se guardarán