A room contains a normal $8\times8$ chess board together with $64$ identical coins, each with one "heads" side and one "tails" side. Two prisoners are at the mercy of a jailer who has decided to play a game with them for their freedom. The rules of the game are as follows.
The jailer will take prisoner 1 with him into the aforementioned room, leaving prisoner 2 outside. Inside the room the jailer will place exactly one coin on each square of the chess board, choosing to show heads or tails as he sees fit. Having done this he will then choose one square of the chess board and declare to prisoner 1 that this is the magic square. Prisoner 1 must then turn over exactly one of the coins and exit the room. Then, prisoner 2 is admitted. The jailer will ask him to identify the magic square. If he is able to do this, both prisoners will
be free.
These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. What strategy should the prisoners adopt?
===============================================
We generalize to any chessboard with $k$ squares. The problem is equivalent to finding the magic coloring of the hypercube graph $Q_k$ with $k$ colors such that the colors of all $k$ neighbors of every vertex are distinct. By counting it is obvious that we need every color class to have the same number of vertices, so a necessary condition for the magic coloring to exist is that $k$ is a power of $2$.
We show by induction that it is also the sufficient condition.
For $k=1$, every vertex is colored $0$. Let $f_{k}:\{0,1,\dots,2^k-1\}\mapsto\{0,1,\dots,k-1\}$ be a magic coloring for some $k$ which is a power of $2$. For $x\in\{0,1,\dots,2^{2k}-1\}$, define $x_L,x_R\in\{0,1,\dots,2^k-1\}$ as $x$'s first $k$ and last $k$ bits, respectively, i.e., $x=x_L2^k+x_R$.
Let
$$f_{2k}(x)=\left(2f_k(x_L)+2f_k(x_R)+\mathbf{1}(x_R\text{ has an odd number of ones})\right)\mod 2k.$$
It could be seen that $f_{2k}$ is a magic coloring.
No comments:
Post a Comment