Colorings of $n^2$-dimensional hypercube

Question

A friend of mine asked me a puzzle*, which I was able to reduce to the following question:

Let $n \geq 2$ be an integer and consider the graph $(V,E)$ on the set $V=\{0,1\}^{n^2}$ of binary sequences of length $n^2$ obtained by adding an edge between two sequences $x$ and $y$ if and only if $x$ and $y$ differ only by a single bit, that is $x E y$ if and only if $|\{i \in n^2: x(i) \neq y(i)\}|=1$.

Can we color the vertices $V$ into $n^2$ colors so that, given any vertex $v \in V$, among vertices whose distance to $v$ is at most $1$, all $n^2$ colors are observed?

More precisely, does there exists a function $f: V \rightarrow \{1,2,\dots,n^2\}$ such that for every $v \in V$ and every $1 \leq i \leq n^2$, there exists $w \in V$ with $f(w)=i$ such that $v = w$ or that $v E w$?

I was able to prove this for $n=2$. The actual puzzle is about the case $n=8$. I think there is supposed to be a recursive solution for $n=4,8,16,\dots$ but I cannot seem to find it. It might also be interesting to find solutions for arbitrary dimensions instead of dimensions of the form $n^2$.

You are welcome to find a solution to the puzzle bypassing this question.

---

*: Here is the puzzle: You and your friend are to be executed if you lose the following game. There are 64 coins, one of which is a magic coin that is supposed to be found by your friend in order to win the game. You and your friend are not allowed to communicate in any way after the game starts.

Once the game starts, your friend is blindfolded. Then those 64 coins are placed on squares of a chess board, facing heads or tails. The executer then points to the magic coin. You are allowed to (but not forced to) flip one coin of your choice. Then your friend's blindfold is untied and he is supposed to find the magic coin.

Before the game starts, you and your friend are both explained these rules. Can you build a strategy which guarantees that you win the game?

---

Here is why a solution to this game reduces to the question above: Identifying heads with $0$ and tails with $1$, we can represent the board by an element of $V$. If we can find a coloring satisfying the property above, then, by flipping a single coin, we can always make (the element corresponding to) the board having color $1 \leq i \leq 8^2$ coding the location of the magic coin. Thus, you friend can find the magic coin simply by evaluating the function $f$ at (the element corresponding to) the board he sees.

Answer 1

Label the columns $0$ through $7$, and similarly for the rows. Create 3 binary digits, even or odd, as follows: count the parity of heads-up coins in the columns with a 4, a 2, or a 1 in their binary expansion. That is, the first number is the number of heads-up coins in columns $4,5,6,7$, the second is columns $2,3,6,7$ and the third is columns $1,3,5,7$. This gives you the binary expansion of another number between $0$ and $7$. Do the same thing for the rows.

Then you figure out which digits you have to change in the row and column number to match with the row and column that the magic coin is in. There is always a single coin you can flip over that will make this work, its row and column is uniquely determined. So you flip that over.

Then your friend's job is to just do the same calculation you did and point to that coin and win.

Answer 2

The following will work for a $2^n$-hypercube not an $n^2$-hypercube.

To each vertex, $v$, specified by a binary sequence of length $2^n$, $v: v_{_{0\dots 0}},v_{_{0\dots 1}}, \dots, v_{_{1\dots 1}}$ (each element of the sequence is indexed by an n-digit binary number), we assign a color $c_v$, which is a binary sequence of length $n$ whose $i$-th digit is the parity of the number of ones in the set $\Omega_i$ defined by $$\Omega_i=\{v_{j_1,\dots,j_n}|j_i=1\}.$$

Let us see how this works: suppose I want to find the color $c$ in the neighborhood of $v$. Look at the binary representation of $c$ XOR $c_v$, $(j_1, \dots, j_n)$ (this sequence specifies which bits in the color function need to be flipped), then flip $v_{j_1,\dots,j_n}$. It will change the parity of $\Omega_i$s for all $i$ such that $j_i=1$, and therefore changes $c_v$ to $c$.

This generalizes Bob Jones answer.