The Chessboard Puzzle

Problem

The situation is as follows. There are 3 contestants, Warden, Prisoner 1 and Prisoner 2, and a 8x8 chessboard with a coin placed on top of each cell. The warden sets up the intial configuration of heads and tails, and places a “key” under one of the cells. Prisoner 1, who is standing by him, sees this and accordingly flips one coin and walks away. Prisoner 2, who was away, comes and sees the current configuration only (he doesn’t know which coin has been flipped, just the resulting configuration). He has to tell where the key is! Note that the prisoners strategies before hand, and the warden listens to there strategy.

Solution

I first came across this puzzle early in my undergrad and just managed to solve this recently. In retrospect this is not too hard a puzzle, I might say elementary. But that doesn’t matter, it was more to me than a puzzle. It was fun - It was always a playground for exploration. The problem never felt like unapproachable, quite the opposite, I had so many different ideas on how to attack it; I felt overwhelmed by choices!

The reason I am telling this is, I have played around with this puzzle for such a long time and have grown since, I don’t really know what my thought process was at that time, most approaches seems to me now as clear dead end. I remember thinking geometrically, I had just passed high school this was the most natural, now its like “what was I thinking”, this is clearly a dead end, I spent quite some time on these thread just not sure on what exactly at this point. I also worked very sporadically, once or twice a year and not the best documented. With these excuses I will dive straight into the most recent attempt.

As you will see the square chessboard is irrelevant, and only the number of tiles matter. As such we generalize it by saying consider binary strings of length \(N\), along with a associated key (bit index). Prisoner 1, now flips one bit, and prisoner 2 based on the new string alone has to tell where the key is.

One thing should be obvious, we cannot tell which was the flipped coin. Because there are N possible strings that could have yielded it and all are possible for various keys! This is a bit subtle. If there is no notion of key, then all we are asking for is bijection, \(f: \{0,1\}^N \rightarrow \{0,1\}^N\) s.t \(d_H(f(x), x) = 1\), where \(d_H\) is the hamming distance (number of different bits) which obviously exist. A sample function is: always flip the first bit. Similarly any number of hamming distance apart strings are reversible. However when we further constraint the function s.t it should also tell the location of key, the same string has to map \(N\) different strings, one for each key (why?), and because the output space is the same as input space, the preimage of each string is not unique.

The functional formulation makes the problem a bit clear but also not apt at visualizing the possible symmetries to ensure the mapping exist. There is a cleaner way to visualize the problem, using graphs and colouring. Consider the graph \(G = (V,E)\), whose vertexes are the \(N\)-bit strings of 0 and 1s, and edges exist between two nodes if they are 1 hamming distance apart. This graph is nothing but the hypercube. Now the problem is equivalent to the following colouring scheme - colour each node using \(N\)-possible colours s.t no two nodes that are 2 bits (2 edges) apart have the same color. We will see how this colour scheme, if exist, ensure solution to our problem. Suppose warden gave you some initial string and key. We assign each key a colour, \(N\) possible location of keys and there are \(N\) colours. In the graph, find your initial string node and then find the neighbour (1 distance apart joined by an edge) with that key-colour. Prisoner 1 makes that transition (flips the bit that would lead to going to that node, with the key-colour). Prisoner 2 comes, sees the string, and looks at the graph. He notes the colour of the string node, and based on our key-colour mapping, tells the keys location! The reason we require the colour be different at 2 nodes that are 2 distance apart is simple - Let \(v\) be a common neighbour (i.e. both our nodes are its neighbour), suppose warden gave the initial string as \(v\) and the key location correponds to the colour of our 2 nodes. Where will the prisoner 1 moves the string to? There are 2 choices. You might say choose randomly, but you have to note that, because there are just \(N\) neighbours and \(N\) key location, each neighbouring strings should have distinct colour, else one key location is missed out!

From our above formulation, one thing is clear, every colour occurs the same number of times. There is a total symmetry in regard to each colour. Which implies \(2^N\) should be divisible by \(N\). Each colour occurs some \(k\) times, \(k\) being an positive integer, and so \(kN = 2^N\). If this is not case, some colour has to be overused to fill up the remainder nodes breaking the symmetry. This reduces the solution set, if exist, drastically. \(N\) can only be of form \(2^m\)¹. Now we will show that when \(N\) is a power of 2, such a colouring scheme exists! I.e. there exists a function \(g: \{0,1\}^N \rightarrow \{0,1\}^m\) s.t \(d_H(v_1, v_2) = 2 \implies g(v_1) \ne g(v_2)\), where \(N = 2^m\). Here we are using binary strings to encode colour, which as you will see holds the key (no pun intended) to the solution.

I am not quite certain how to motivate this next part, it came sort-of mechanically (or rather I should say worked mechanically, the idea was natural). Before I move forward, let me take a detour on little group theory (as this holds the key, really, why the solution works). A group is nothing but a collection of elements² with the associated property of composition. I.e. there exist a law of composition (a function or notationally we represent it by \(.\)), which takes 2 elements (in-order) and gives a new element. A group has some more properties like - closed under composition, composition is associative, existence of identity (an element \(e\), composition with which gives back same element), existence of inverse (i.e. if \(a \in G \implies\) \(\exists a^{-1} \in G\) s.t \(a.a^{-1} = a^{-1}.a = e\)). The set \(Z_2^N = \{0,1\}^N\) is a group with the composition operation being binary addition (mod 2! else will go out of bound). Here each elements is its own inverse, and 0 is the identity. A generating set of a group is the subset of group elements s.t taken together with the help of composition can generate every other element. For \(Z_2^N\) the direction elements \(\{1000 \cdots,\) \(0100 \cdots,\) \(\dots,\) \(\cdots 0001\}\) is one such generating set. Just to go a bit further, our hypercube is nothing but the “Cayley graph” for the \(Z_2^N\) group. A cayley graph, is a graph whose vertexes are the elements of the group (the binary strings in our case), there exist a edge between 2 nodes iff one is reached via other under composition with an element of generating set (i.e if \(u, v \in G\), \(\exists\) an edge iff \(v = s.u\), where \(s \in\) generating set, another way of saying is: there is an edge between \(u\) and \(s.u\)). Basically the generating set is equivalent to “direction” and the edges encode that. It is a visual way to see how each element is generated from symmetries.

Cayley graph of D_4: the symmetry group of the square. Red and blue arrow represent composition with r_90 and f_h. As horizontal flip is self-inverse, it is doubly directed

Now let me tell you the mapping \(g\). First map each colour to an element of \(Z_2^m\)³. Now assign each element of the generating set of our hypercube (the direction vectors) a number in \(Z_2^m\), note that both these sets have elements (\(N\)). Now for \(v \in Z_2^N = \sum a_i d_i\), where \(d_i\) is the \(i\)th direction vector (it can be decomposed thus because \(d_i\)’s are generating elements, start with an element in the generating set itself, or just plain otherwise!), \(g(v) = \sum_i a_i g(d_i)\), note this sum is mod 2, or put more mathematically “sum” refers to the composition law of \(Z_2^m\). I.e. a linear transformation. This is a simple colouring scheme, we now have to show it is a valid color scheme. Let \(v = u + e_1 + e_2\), where \(e_1\) and \(e_2\) are two direction vectors , we have to show \(g(v) \ne g(u)\).

\[\begin{align*} g(v) &= g(u + e_1 + e_2) \\ &= g(u) + g(e_1) + g(e_2) \\ \end{align*}\]

Showing \(g(v) \ne g(u)\) is equivalent to showing \(g(e_1) + g(e_2) \ne 0\). Now see that \(e_1\) and \(e_2\), cannot be the same, because \(d_i\) are its own inverse! You will be at \(u\) itself. Also, in general, a group has unique inverses⁴. Now as \(e_1\) and \(e_2\) are distinct, \(g(e_1)\) and \(g(e_2)\) (\(\in Z_2^m\)) are distinct. As this is the same group, and only way this sum is zero happens when they are inverses of each other. Which is only possible if both are equal. This is the reason why I added the primer on group theory, it is the structure of \(Z_2^N\) and consequently the \(Z_2^m\) that saved us!

Finally to wrap up, let us implement our strategy for \(N=64\) (the 8x8 chessboard). First we have to assign, we would label via binary strings itself instead of colour, a binary string in \(Z_2^6\) to each direction vector and then form the mapping \(g\). The key-label mapping is simply at which index the key is⁵. As \(g\) is a linear transformation, we directly write the matrix \(G_{6 \times 64}\). The \(i\)th column of \(G\) is the binary representation of “\(i\)”. If you are new to linear algebra, the \(i\)th column vector of a matrix represents where \(i\)th direction vector (with 1 in \(i\)th place and 0 elsewhere) maps to under the linear transformation. Now the warden gives an initial binary string and a key label. We have to find this string in our graph and find the neighbour with that label. This is easily done as follows, we know our new strings is nothing but \(u + e_1\), where \(u\) is the initial configuration. We know the label of \(u\) (which is \(Gu\)) and we know the desired label of \(u + e_1\) (label representation of the key). As \(g(u + e_1) = g(u) + g(e_1)\), we can find out the label for \(e_1\). Convert the label into base 10 number and call it \(j\), and we now know \(e_1\) \(= d_j\) (1 at \(j\) co-ordinate and 0 elsewhere). Make this move. Prisoner 2 comes and sees the new configuration, call it \(v\), he finds the label \(Gv\), find the key location via key-label mapping (which we assumed to be the index) and he is done!

Concretely, let \(u\) be “1000000000000000000000000000001000000000000000000000000000000001” and key be at index 10 (left to right, starting from 0 upto 63). Let us find \(e_1\): \(Gu\) is equal to \(1.(0)_2 + 1.(30)_2 + 1(63)_2\), where \((i)_2\) means representation of base 10 in base 2. This is equal to, 011110 + 111111, which is equal to 100001. The binary representation of 10 is 001001. Subtracting them (or adding inveres, which the same thing as they are same) to get \(g(e_1)\), 101000, which in base 10 is 40. Thus \(e_1\) correponds to 40th column (starting from 0), which is nothing but 1 at 40th place. So we flip the 40th bit, to get the new configuration “1000000000000000000000000000001000000000100000000000000000000001”. Now prisoner 2 comes and find label via \(Gv\) which is equal to \(1.(0)_2 + 1.(30)_2 + 1(40)_2 + 1(63)_2\), which is 011110 + 101000 + 111111 = 001001, which in base 10 is 10! The key is 10th index, as expected.

Slightly Direct Approach

A slightly different way to look at the very same thing, which might be more natural is: we want to assign colours (or labels) to the binary strings. Consider the assignment as follows \(\sum X_i b_i\). So like if our colors are represented by 0, 1, 2 for 3 bit strings, the scheme is as follows \(0.b_0 + 1.b_1 + 2.b_2\) (mod 3). You do like before, first see what is the label of your current string, and what you want in return, and see if you can alter the string to attain that. E.g here let the string be 000, the current label is 0. To get to label 0 - we can switch 0th bit, for label 1 we can switch 1st bit, for label 2 we can switch the 2nd bit. Good, what about 001? The current label is 2. To get to label 0, we need to subtract 2 or add 1 - switch the 2nd bit or switch the first bit (former subtracts 2 and later adds 1). However to get the label 1, we need to either add 2 or subtract 1. But 2nd bit is already on (can’t add 2), and can’t off 1st bit (already off, i.e. can’t subtract 1). So this scheme is not valid. In general for larger binary strings as well, we have 75% chance of failure. It is simple to see, and will lead to the solution directly. Our function would work if two bit flips are available - the bit correponding to addition is off, so that we turn it on (like 2 in above) and the bit correponding to subtract is on, so we can off it (like 1 in above). I.e. you have current label of string, and you want something different. You can either turn on a bit that would add the remaining value. Or you can turn off the bit that would subtract the value s.t it is equal to new label. Consider another example, this time 64 bit strings. Say your current label is 43 and you want 1. You either turn on the bit that would add 22 or turn off the bit that would take off 42. Now if both of these are on and off respectively already, there is nothing you can do. Hence the 75% or 3/4. Notice however if you use some other label s.t the addition and subtraction would imply the same bit flip you are always guaranteed. Our \(Z_2^m\) group is just that, here if you are at some label and want to go to some other label. You can either add or subtract, but you will be doing the same thing (as we have already seen in previous discussions)! So just flipping the bit corresponding to that label does the string.

Notes

1. The prime factors of \(N\) can only be 2, because any other won’t divide the numerator. ↩︎

2. Mathematically they are any objects with associated property, which are mentioned next. But intuitively, sometimes, it is better to proxy them with “symmeteries”. Each element in the set represent a symmetry. For example, a group would be: the symmetries of a square which consist of the eight elements: \(\{ e, r_{90}, r_{180},\) \(r_{270}, f_v, f_h,\) \(f_d, f_a \},\) where \(e\) is the identity (do nothing), \(r_{90}\), \(r_{180}\), and \(r_{270}\) are rotations by \(90^\circ\), \(180^\circ\), and \(270^\circ\) clockwise respectively, \(f_v\) is reflection over the vertical axis, \(f_h\) over the horizontal axis, \(f_d\) over the main diagonal (top-left to bottom-right), and \(f_a\) over the antidiagonal (top-right to bottom-left). The reason for this selection is, there is a natural composition law namely compose! Composition of any 2 symmeteries in above is quite natural operation, and it is visually obvious it preserves symmetry (i.e. result of composition is still in our set). The idea of inverse is also quite natural, if you apply some symmetry to the square, because doing the same operation backwards is also a symmetry it should exist in the set! Albeit might be represented in some convoluted manner (like \(r_{90}\)’s inverse is \(r_{270}\), though reflections are there own inverses). One can quickly see this is non-ableian (non-commutative), like \(f_h . r_{90} \ne r_{90} . f_h\). It also lends naturally into the theme of generating set. It is but wanting to be said that all (including \(e\), which is \(r_{90}\) composed 4 times) the rotations are essentially \(r_{90}\) composed onto itself several times. If you think about it, \(f_h\) and \(r_{90}\) when composed cleverly amongst themselves several times, leads to all the symmetries! This set of symmetries that together can create all other symmetries is called the generating set. All this said, when analysing or visualizing groups, imagining elements be symmetries might be useful.⁴ ↩︎

3. If you are fine with assigning numbers to the vertexes, you don’t need this mapping. This is just for terminology. ↩︎

4. Here it is not too hard to see. What is the inverse of any string \(b\), the \(b\) itself. Every bit requires itself to be added to go to 0. There is just no other choice. Though in a group, in general, inverses are unique! The proof is trivial - let \(a \in G\) and \(a_1, a_2\) be the 2 inverses. We know \(a.a_1 = e\), it implies \(a_2.(a.a_1) = a_2.e = a_2\), which is same as \((a_2.a).a_1 = e.a_1 = a_2\). ↩︎ ↩︎²

5. In a square representation, agree first hand how to assign a number to each cell. In a linear string, we can easily follow the convention of left to right (or vice versa). As there are \(N\) possible location of the key, we have \(N\) colour / labels, any mapping will do. ↩︎