During my stream today, one of my viewers asked me if I had heard of the Devil's Chessboard problem. I hadn't, but it led to some quite interesting questions. The basic question is as follows:

The devil has captured two people and is playing a game with them for their freedom. Person A will be presented with a chessboard with a penny in each square (64 total), with each penny either heads up or tails up randomly. The devil will choose a particular square and point it out to Person A. Person A then chooses a single square, and flips the penny in that square. Afterward, Person A is sent away and Person B is brought forward. Based on the new state of the board, Person B must point out the same square that the devil did in order to win. The two people can devise a strategy beforehand, but cannot communicate once the game starts. How can they win?

If you haven't heard the problem before, I'd recommend thinking about it for a while first. Despite looking like a typical "gotcha" brainteaser, the idea behind the solution is actually widely applicable to various situations. We'll also consider generalizations to the Devil's Chessboard where the number of coins changes from 64 to a different number \( n \).

The 64 coin solution

Number the coins from 0 to 63, and define the value of a board as the bitwise xor of the coins that are showing heads. So for example, if coins 3, 5, 12, 14, and 57 are heads and the rest are tails, the value of the board is 61:

 3 = 000011
 5 = 000101
12 = 001100
14 = 001110
57 = 111001
-----------
61 = 111101

Person A wants to find a coin to flip that will cause the value of the resulting board to be the index of the square that the devil pointed out. This will always be possible, and person A can determine which coin to flip by taking the devil's pointed out square and xoring it with the current value of the board. This works because \( x \oplus y \oplus y = x \) (where \( \oplus \) denotes xor), so flipping coin \( i \) changes the value of the board by xoring it with \( i \), regardless of whether the coin is flipped from heads to tails or from tails to heads.

Now let's consider the question of whether it is possible to win the \( n \) coin version of this game. Again, I recommend spending some time to think about the question for yourself before reading on.

When is the game winnable?

For this question, it helps to recast the problem in a different light. We can associate an arrangment of \( n \) coins as a string in \( \{0, 1\}^n \), which is just a compact way of denoting an n-bit string. So for example, \( \{0, 1\}^3 = \{000, 001, 010, 011, 100, 101, 110, 111\} \). Now, we'll construct a graph where the vertex set is \( \{0, 1\}^n \) and two vertices are connected by an edge if they differ in exactly one bit. In the context of the game, when person A is presented with the initial board, they will pick one of its \( n \) neighbors to present to person B.

This graph is exactly the hypercube graph \( Q_n \). Each vertex corresponds to an arrangement of coins, so we'll assign each vertex a value which is the square that person B will point to if presented with that arrangement. An assignment of values will correspond to a winning strategy whenever every vertex's neighbor set contains all \( n \) possible values.

Now we can use a counting argument. Look at any particular arrangement. In a winning strategy, It will have exactly one neighbor with value 0. So we count \( 2^n \) 0s, but each 0 got counted \( n \) times, because every arrangement has \( n \) neighbors. That means that there is a total of \( \frac{2^n}{n} \) 0s. But the number of 0s needs to be an integer, so \( n \) must divide \( 2^n \), which occurs exactly when \( n \) is a power of 2.

Furthermore, the solution from earlier generalizes straightforwardly to any number of coins that is a power of 2, so we have our answer: the game is winnable exactly when \( n \) is a power of 2.

Are there other solutions?

Now that we've established that \( n \) has to be a power of 2, it seems like there's something special about being able to index the coins with bit-strings in the way that we did earlier. We built our solution on the structure of xor, but maybe there is another type of structure that also leads to a solution.

So let's think about how many different solutions we can get out of the xor idea. It certainly doesn't matter what ordering we assign to the pennies, and furthermore once we've done the xoring, we can apply any bijective function to the result and not ruin the coloring property. So we have valid assignments of the form \( f(\bigoplus x_i) \) where \( f: \{0, \ldots, n-1\} \to \{0, \ldots, n-1\} \) is a bijection, the \( x_i \) are a permutation of \( \{0, \ldots, n-1\} \), and the xor ranges over all \( i \) where the \( i \)th coin shows heads.

But we can actually go further than that. Let's go back to the graph coloring idea. Instead of considering the graph \( Q_n \), let's consider the graph \( Q_n^2 \) -- the graph with length \( n \) bitstrings as vertices, and an edge between two vertices if the corresponding bitstrings differ in exactly two places. In a winning solution, no two adjacent vertices in this graph will have the same value, because they have a common neighbor in \( Q_n \). Conversely, any proper \( n \)-coloring of \( Q_n^2 \) leads to a winning strategy.

To see that, notice that for any arrangement, all of its neighbors in \( Q_n \) differ from each other in exactly two spots, so they are adjacent in \( Q_n^2 \). As a result, in such a coloring, any arrangement has \( n \) neighbors that all have different values, so every value in \( \{0, \ldots, n-1 \} \) must be present, meaning that this corresponds to a winning strategy.

The bijective function \( f \) that we applied earlier just corresponds to permuting the colors in a proper \( n \)-coloring to get another proper \( n \)-coloring. But notice that \( Q_n^2 \) has two connected components: one where the bitstrings have an even number of 1s, and one where the bitstrings have an odd number of 1s. So we were actually too strict before. The bijection can be different depending on the parity of the number of 1s.

So now our solutions are of the form \( f_b(\bigoplus x_i) \), where \( b \) is 0 when there are an even number of heads and 1 when there are an odd number, \( x_i \) are a permutation of \( \{ 0, \ldots, n-1 \} \), and \( f_0, f_1 : \{ 0, \ldots, n-1 \} \to \{ 0, \ldots, n-1 \} \) are bijections. At this point, it looks like we've covered all the "obvious" fudging that turns one solution into an equivalent one. But we don't know whether there's another solution still.

For 2 and 4 coins, there's nothing else.

For 2 coins, \( Q_2 \) is just a square, and it's easy to verify that the only assignments that are winning are two adjacent 0s and two adjacent 1s and that these are all captured by the form of solution that we already know about. The 4 coin problem is much more interesting. We're looking at the hypercube \( Q_4 \). But again, it'll be more useful to instead look at \( Q_4^2 \).

The odd component of \( Q_4^2 \) consists of the strings 0001, 0010, 0100, 1000, 0111, 1011, 1101, and 1110. In that set, all of the strings with a single 1 are adjacent to each other, and similarly for the strings with three 1s. Between those two sets, most of the pairs are adjacent as well, with the exception that a string is not adjacent to its complement. So 0001 is adjacent to every string except for 1110, and similarly for the others.

So between 0001, 0010, 0100, and 1000, all 4 values are represented, and 1110 is adjacent to all of them except for 0001. Therefore, 1110's value must be the same as 0001's value, and similarly for the other pairs of complements. Therefore, a 4-coloring of the odd component of \( Q_4^2 \) is just any bijection between \( \{0, 1, 2, 3\} \) and \( \{0001, 0010, 0100, 1000\} \), with the other values being determined from those. This freedom is captured in our general form by the choice of \( f_1 \).

Now let's look at our even component. For any bitstring, say 0000, it will not be adjacent to its complement, in this case 1111, but it will be adjacent to all of the other six bitstrings. Therefore, whatever value is assigned to 0000, the other values are all present in the middle layer, so the value of 1111 must be the same as the value of 0000. Similarly, the value of 1100 must be the same as that of 0011, and so on. So a 4-coloring of the even component corresponds to a bijection between \( \{0, 1, 2, 3\} \) and \( \{0000, 1001, 1010, 1100\} \), which is captured in our general form by the choice of \( f_0 \).

Unfortunately, 4 coins is too small to really see the pattern as we go to 8 coins, 16 coins, and beyond. Does more freedom show up at some point? I do not know the answer. My guess is that the general form that I've given here really does include all of the possibilities, but that's really just a guess and it would not be surprising at all to find out that my guess is wrong. Can you figure it out?