10 enanitos

Question

Un gigante matador de enanos pone en fila a 10 enanos del más bajo al más alto.

Cada enano puede ver a todos los enanos más bajos que tiene delante, pero no puede ver a los enanos que tiene detrás.

El gigante pone al azar un sombrero blanco o negro a cada enano. Ningún enano puede ver su propio sombrero. El gigante dice a todos los enanos que preguntará a cada uno de ellos, empezando por el más alto, el color de su sombrero.

Si el enano responde incorrectamente, el gigante lo matará.

Cada enano puede oír las respuestas anteriores, pero no puede oír cuando un enano es asesinado.

Los enanos tienen la oportunidad de confabularse antes de repartir los sombreros.

¿Qué estrategia debe utilizarse para matar el menor número de enanos, y cuál es el número mínimo de enanos que puede salvarse con esta estrategia?

Mi enfoque: El primer tipo cuenta qué color es el máximo, lo dice, todos los demás copian su respuesta. De esta manera, nos ahorramos al menos 5, pero creo que podemos optimizar esto, sólo que no puedo averiguar cómo....

Answer 1

Paridad: Los enanos están de acuerdo en que el negro = 1 y el blanco = 0. El primer enano suma todos los sombreros que ve mod 2 y lo señala. El resto de los enanos deben recordarlo. Cada enano suma los sombreros que ve mod 2 y si es igual, considera su sombrero blanco, si no es la misma paridad, entonces considera su sombrero negro.

Después de eso, cada enano por turno dice su presunción del color del sombrero, excepto que los enanos que escuchan deben cambiar su suposición cada vez que alguien antes de ellos dice "negro" (después del primer enano). De esta manera, sólo tienen que sumar los sombreros una vez, y no necesitan recordar cada llamada, sólo cambiar su color cuando se dice "negro".

Todos los enanos, excepto el primero, tienen garantizada la supervivencia.

Answer 2

Este vídeo de Khan academy puede ser útil:

https://www.youtube.com/watch?v=K4pocYXOmTQ

Answer 3

Solución 1: Si el último grita el primer color y el penúltimo el segundo, al menos seguro que sobreviven los cinco primeros de la fila. Solución 2: Como no hay obligación en la forma de responder, pueden ponerse de acuerdo; Si digo sólo el color, "negro" o "blanco", significa que el que tengo delante es blanco Si digo el color en una frase, "es negro" o "debería ser blanco", significa que el que tengo delante es negro.

Siguiendo estas reglas 9 sobrevivirán y hay un 50% de posibilidades para 1.

Ejemplo: El último dice "negro" significa que el siguiente es blanco. así que el siguiente dirá "blanco" si delante es blanco y dice "es blanco" si el siguiente es negro.

Answer 4

Mi respuesta es : Mínimo 9 enanos pueden ser salvados .

Supuesto: La pregunta se formula en orden decreciente de altura, empezando por el más alto.

El gigante empieza a preguntar al enano más largo el color de su sombrero . La probabilidad de que la respuesta sea correcta es del 50%. Así que puede decir blanco o negro ; pero como todos han formulado una estrategia : el enano más largo verá el color del enano de al lado y dirá su color.

Por lo tanto, el siguiente enano conoce su color con un 100% de seguridad y lo dirá a continuación; los 9 enanos restantes dan la respuesta correcta.

Answer 5

Los enanos buscan lo que pasó en la Biblia y se arman con hondas. Diez piedras contra la cabeza y el gigante cae, momento en el que le cortan el cuello. Todos los enanos sobreviven.