Coloración de $n^2$ -hipercubo de dimensiones

Question

Un amigo me planteó un enigma*, que pude reducir a la siguiente pregunta:

Dejemos que $n \geq 2$ sea un número entero y consideremos el gráfico $(V,E)$ en el plató $V=\{0,1\}^{n^2}$ de secuencias binarias de longitud $n^2$ obtenida añadiendo una arista entre dos secuencias $x$ y $y$ si y sólo si $x$ y $y$ difieren sólo en un bit, es decir $x E y$ si y sólo si $|\{i \in n^2: x(i) \neq y(i)\}|=1$ .

Podemos colorear los vértices $V$ en $n^2$ colores para que, dado cualquier vértice $v \in V$ entre los vértices cuya distancia a $v$ es como máximo $1$ , todos $n^2$ ¿se observan los colores?

Más concretamente, ¿existe una función $f: V \rightarrow \{1,2,\dots,n^2\}$ tal que para cada $v \in V$ y cada $1 \leq i \leq n^2$ existe $w \in V$ con $f(w)=i$ tal que $v = w$ o que $v E w$ ?

Pude comprobarlo por $n=2$ . El rompecabezas real es sobre el caso $n=8$ . Creo que se supone que hay una solución recursiva para $n=4,8,16,\dots$ pero no puedo encontrarlo. También podría ser interesante encontrar soluciones para dimensiones arbitrarias en lugar de dimensiones de la forma $n^2$ .

Puedes encontrar una solución al rompecabezas obviando esta pregunta.

---

*: Este es el acertijo: Tú y tu amigo serán ejecutados si pierden el siguiente juego. Hay 64 monedas, una de las cuales es una moneda mágica que debe ser encontrada por tu amigo para ganar el juego. Usted y su amigo no pueden comunicarse de ninguna manera después de que el juego comience.

Una vez que el juego comienza, tu amigo tiene los ojos vendados. A continuación, esas 64 monedas se colocan en las casillas de un tablero de ajedrez, mirando a cara o cruz. El ejecutor señala entonces la moneda mágica. Se le permite (pero no se le obliga) a lanzar una moneda de su elección. A continuación, se desata la venda de los ojos de tu amigo y se supone que debe encontrar la moneda mágica.

Antes de que comience el juego, se os explican a ti y a tu amigo estas reglas. ¿Podéis construir una estrategia que os garantice ganar la partida?

---

Por eso, la solución de este juego se reduce a la pregunta anterior: Identificar las cabezas con $0$ y colas con $1$ podemos representar el tablero por un elemento de $V$ . Si podemos encontrar una coloración que satisfaga la propiedad anterior, entonces, lanzando una sola moneda, siempre podemos hacer que (el elemento correspondiente a) el tablero tenga color $1 \leq i \leq 8^2$ codificando la ubicación de la moneda mágica. Así, el amigo puede encontrar la moneda mágica simplemente evaluando la función $f$ en (el elemento correspondiente a) la tabla que ve.

Answer 1

Lo siguiente funcionará para un $2^n$ -hipercubo no un $n^2$ -hipercubo.

A cada vértice, $v$ especificado por una secuencia binaria de longitud $2^n$ , $v: v_{_{0\dots 0}},v_{_{0\dots 1}}, \dots, v_{_{1\dots 1}}$ (cada elemento de la secuencia está indexado por un número binario de n dígitos), asignamos un color $c_v$ que es una secuencia binaria de longitud $n$ cuyo $i$ -la cifra es la paridad del número de unos en el conjunto $\Omega_i$ definido por $$\Omega_i=\{v_{j_1,\dots,j_n}|j_i=1\}.$$

Veamos cómo funciona: supongamos que quiero encontrar el color $c$ en los alrededores de $v$ . Mira la representación binaria de $c$ XOR $c_v$ , $(j_1, \dots, j_n)$ (esta secuencia especifica qué bits de la función de color deben invertirse), y luego invertir $v_{j_1,\dots,j_n}$ . Cambiará la paridad de $\Omega_i$ s para todos $i$ tal que $j_i=1$ y, por lo tanto, cambia $c_v$ a $c$ .

Esto generaliza la respuesta de Bob Jones.

Answer 2

Etiquetar las columnas $0$ a través de $7$ y lo mismo para las filas. Cree 3 dígitos binarios, pares o Impares, de la siguiente manera: cuente la paridad de las monedas de cabeza en las columnas con un 4, un 2 o un 1 en su expansión binaria. Es decir, el primer número es el número de monedas cara a cara en las columnas $4,5,6,7$ el segundo son las columnas $2,3,6,7$ y la tercera son las columnas $1,3,5,7$ . Esto le da la expansión binaria de otro número entre $0$ y $7$ . Haz lo mismo con las filas.

A continuación, averigua qué dígitos tienes que cambiar en el número de la fila y la columna para que coincida con la fila y la columna en la que está la moneda mágica. Siempre hay una sola moneda que puedes voltear y que hará que esto funcione, su fila y columna están determinadas de manera única. Así que se le da la vuelta.

Entonces el trabajo de tu amigo es simplemente hacer el mismo cálculo que tú hiciste y señalar esa moneda y ganar.