Puzzle de sombreros arco iris

Question

Siete presos tienen la oportunidad de ser liberados mañana. Un verdugo de verdugo pondrá un sombrero en la cabeza de cada prisionero. Cada sombrero puede ser uno de los siete colores del arco iris y los colores del sombrero se asignan completamente a discreción del verdugo. Cada prisionero puede ver el colores de los sombreros de los otros seis prisioneros, pero no el suyo. No pueden comunicarse con los demás de ninguna manera, o de lo contrario son inmediatamente ejecutados. Entonces cada prisionero escribe su suposición del color de su propio sombrero color del sombrero. Si al menos un prisionero adivina correctamente el color de su sombrero, todos serán liberados inmediatamente; de lo contrario serán ejecutados. Se les da la noche para idear una estrategia. ¿Es ¿Existe una estrategia que les garantice la liberación?

Hoy me he encontrado con un acertijo que incluso después de leer la explicación de la solución no entiendo cómo funciona matemáticamente. Creo que es una pregunta bastante interesante, así que no voy a publicar la respuesta (probablemente no pueda expresarla bien de todos modos teniendo en cuenta que no la entiendo). De todas formas puede ser un acertijo matemático común.

Esperaba que alguien pudiera darme una explicación intuitiva y matemática de cómo resolver esto y por qué funciona. ¿Es posible también dar el proceso de pensamiento paso a paso de la construcción de esta solución?

Answer 1

Voy a suponer un mínimo de conocimientos matemáticos; pido disculpas si lo he planteado demasiado bajo. Una solución clásica funciona así.

Los prisioneros numeran los colores $0$ a través de $6$ ; dicen que el rojo $=0$ , naranja $=1$ , amarillo $=2$ y así sucesivamente hasta el violeta $=6$ . También se numeran $0$ a través de $6$ simplemente los llamaré $P_0,P_1,\dots,P_6$ . Cuando se ponen los sombreros en la cabeza, cada prisionero realiza el siguiente cálculo: suma los números de los colores de los seis sombreros que puede ver y lo resta de su propio número personal. Por ejemplo, si $P_3$ ve sombreros con colores $0,2,2,5,5$ y $6$ calcula $$3-(0+2+2+5+5+6)=-17\;.$$ Luego reduce este módulo $7$ a un número en el rango de $0$ a través de $6$ . Si no estás familiarizado con la aritmética modular, eso significa simplemente que suma o resta $7$ repetidamente hasta que obtenga un número en el rango deseado. En este caso $-17+3\cdot7=4$ es el resultado final. Este es el número correspondiente al color azul, por lo que escribe azul . La afirmación es que si cada preso sigue este procedimiento, uno escribirá el nombre del color de su propio sombrero.

He aquí por qué funciona. Observe primero lo que sucede si $P_3$ es realmente azul: entonces los colores del sombrero suman $$0+2+2+5+5+6+4=24\;,$$ y cuando reducimos este módulo $7$ obtenemos $24-3\cdot7=3$ , $P_3$ número personal. El procedimiento garantiza que esto ocurra con cada prisionero: adivina el color del sombrero que haría que la suma de los siete colores del sombrero fuera igual (módulo $7$ ) a su número personal.

Sean cuales sean los colores reales de los sombreros, sus números deben sumar (módulo $7$ ) a uno y sólo uno de los siete números $0,1,2,3,4,5$ o $6$ . Digamos que suman $k$ . Entonces $P_k$ y sólo $P_k$ escribe el color que hace que el total sea correcto. Cada uno de los demás prisioneros escribe un color correspondiente a uno de los otros seis totales posibles. Digamos que $P_k$ anotó el número de color $c_1$ que el color de su propio sombrero es el número $c_2$ y que los números de color de los seis sombreros que podía ver sumaban $t$ . Entonces, por un lado, el procedimiento asegura que eligió $c_1$ para hacer $t+c_1$ igual a su propio número, $k$ , modulo $7$ y por otro lado sabemos que $k$ es el total real de los siete números de color, por lo que $t+c_2$ es igual a $k$ modulo $7$ . En resumen, $t+c_1$ y $t+c_2$ se reducen al mismo número módulo $7$ Así que $c_1=c_2$ : escribió el color de su propio sombrero.

Answer 2

En lugar de colores, imagina que los sombreros están etiquetados con los elementos de $\mathbb{Z}/7$ . Al elaborar la estrategia, se acuerda la correspondencia entre el color y el elemento del grupo, y se asigna a cada prisionero un elemento distinto de $\mathbb{Z}/7$ . El preso al que se le asigna $k$ hace la conjetura que, de ser cierta, haría que la suma de todos los sombreros fuera $k$ .

Una vía útil para solucionar este tipo de problemas es utilizar la linealidad de la expectativa. En este problema, si el ejecutor coloca los sombreros utilizando distribuciones aleatorias uniformes independientes, cualquier estrategia llevará a que cada prisionero tenga una $1/7$ posibilidad de acertar, por lo que el esperado el número de aciertos es siempre $1$ . Esto significa que garantizar un acierto es equivalente a garantizar que no haya dos personas que acierten simultáneamente, lo que me parece más fácil. Muchos otros problemas de este tipo general (como el Problema de las 100 cajas ) puede entenderse mejor de esta manera.

Answer 3

Hay un rompecabezas similar aquí con una solución bastante bien explicada también: Adivinanza del sombrero del prisionero

Parece importante indicar también los supuestos que puedan faltar en el problema.

Answer 4

Si se numeran los posibles colores de los sombreros del 0 al 6, entonces la suma de los colores que tienen los sombreros es uno de 0-6 mod 7. Si cada uno de los prisioneros adivina cuál es, exactamente uno de ellos acertará. Ahora sólo hay que ver que esta persona también adivinará correctamente el color de su propio sombrero, porque su propio color de sombrero está completamente determinado dada la suma de los colores de los sombreros mod 7.

Answer 5

Primero hay que etiquetar los diferentes colores por elementos de $\mathbb{Z}/7\mathbb{Z}$ . Sea $c_i\in \mathbb{Z}/7\mathbb{Z}$ denotan el color del $i$ de la persona. Entonces el total $T = \sum c_i$ es un número que ningún prisionero conoce. Sin embargo, $$c_i = T - \sum_{j\neq i} c_j,$$ y la última cantidad del lado derecho la $i$ El prisionero hace saber. Supongamos que los prisioneros se encargan de que el $i$ El prisionero adivinará que su color es $i - \sum_{j\neq i}c_j$ . Entonces el $T$ El prisionero habrá adivinado correctamente su color.