7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It can only work when $n$ is a power of $2$. You have $2^{n^2}$ sequences that you need to divide into groups of $n^2$ colors. By considering the neighborhood relation it is clear you need the same number of vertices to have each color, so $n^2$ must divide into $2^{n^2}$, which can only happen if $n$ is a power of $2$ $\endgroup$ – Ross Millikan Oct 14 '17 at 20:29
  • $\begingroup$ @RossMillikan: I don't think that is true. Consider the coloring $f: \{0,1\}^3 \rightarrow \{a,b,c\} $ given by $f^{-1}(a)=\{000,010,101\}$, $f^{-1}(b)=\{011,100,111\}$ and $f^{-1}(c)=\{110,001\}$. (I am writing this assuming that you meant the dimension should be a power of $2$. Or, did you mean that $n$ should be a power of $2$ where the dimension is $n^2$?) $\endgroup$ – Burak Oct 14 '17 at 20:37
  • $\begingroup$ But $101$ has no neighbor in $f^{-1}(a)$ in your example, nor does $100$ in $f^{-1}(b)$. If you add up all the neighbors of all the vertices you count each vertex $n^2$ times so you need the same number of each color. $\endgroup$ – Ross Millikan Oct 14 '17 at 20:52
  • $\begingroup$ @RossMillikan: 101 itself has color $a$ and 100 has color $b$. In the fourth paragraph of the OP, I allow $w$ to be $v$. $\endgroup$ – Burak Oct 14 '17 at 20:54
  • $\begingroup$ You don't need to flip a coin if you don't want. In the case of $101$, you could just leave it alone if you wanted to denote $a$. $\endgroup$ – Bob Jones Oct 14 '17 at 20:55
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your color assignment operation $c_v$ is the digit-wise summation of $v_jj$ over $j\in \{0,1\}^n$ and the to-be-flipped bit index $f$ is indexed by the digit-wise subtraction. We can also use the modulo summation and subtraction to achieve the same goal. $$c_v:=\sum_{j\in\{0,1\}^n}v_jj\mod 2^n$$ and $$f=c-c_v \mod 2^n.$$ $\endgroup$ – Hans Oct 22 '17 at 23:35
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.