Yet another prisoner puzzle

Shortly after I started working at SIG, somebody at work asked me the following puzzle.

A room contains a normal 8x8 chess board together with 64 identical coins, each with one "heads" side and one "tails" side. Two prisoners are at the mercy of a typically eccentric jailer who has decided to play a game with them for their freedom. The rules are the game are as follows.

The jailer will take one of the prisoners (let us call him the "first" prisoner) with him into the aforementioned room, leaving the second prisoner 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 (e.g. randomly). Having done this he will then choose one square of the chess board and declare to the first prisoner that this is the "magic" square. The first prisoner must then turn over exactly one of the coins and exit the room. After the first prisoner has left the room, the second prisoner is admitted. The jailer will ask him to identify the magic square. If he is able to do this, both prisoners will be granted their freedom (if not, the poor prisoners will be forced to take up employment at Lee Overlay Partners - a fate that few would relish).

These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. Of course the question is: what strategy should the prisoners adopt?

When I was first asked this puzzle I thought it was probably impossible for the prisoners to guarantee their freedom and rather rashly declared this to be the case (the person who asked me the puzzle did not know whether or not there was a solution). However after thinking about it for long enough, I eventually found a winning strategy. I'd like to talk a bit about:

  1. An elementary winning strategy (without any discussion of its correctness)
  2. How to figure out this winning strategy
  3. Different points of view on the winning strategy
  4. Generalisations of this puzzle
  5. Explicit realisations of particular generalisations
Obviously I recommend thinking a bit about the puzzle before diving down to the solution but it's up to you, reader.

(a) The prisoners can guarantee their freedom. A strategy consists of a pair of algorithms: one algorithm for the first player and one algorithm for the second player. The output of each player's algorithm is the row and column index of a square on the chess board. In the case of the first prisoner these indices identify the coin he must turn over, in the case of the second prisoner these indices identify the magic square which he will announce to the jailer. It is convenient to begin by describing the second player's algorithm.

The input for the second player's algorithm is the configuration of coins he sees on the chess board. He calculates the row and column index independently. Not surprisingly the rules for calculating the row index are the same as those for calculating the column index except that everything is just turned sideways so we will content ourselves with a description of how to calculate the column index. For this, consider the following three chessboards patterns with the squares marked 'o' or 'X':

o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
o o o o X X X X        o o X X o o X X        o X o X o X o X
  
Now suppose the second prisoner knew whether the magic square was one of the 'X' squares or one of the 'o' squares in the first of these patterns, then he would have narrowed down the column of the magic square to either the left or the right hand side of the board. Moreover if he knew the answer to this question not only for the first of these patterns but for all three patterns then he would know the exact column of the magic square. Bearing this in mind, it is enough for us to describe how the second prisoner can answer this question for each of the three patterns independently. To decide whether or not the magic square is one of the 'X' squares for one of the above three patterns, our prisoner counts how many of the 'X' squares contains coins with their heads side showing. If this number turns out to be odd then the magic square is one of the 'X' squares for this pattern, if it is even then the magic square is one of the 'o' squares for this pattern.

So that's the second prisoner's algorithm. As for the first prisoner, his algorithm is very similar except that his input includes the location of the magic square as well as the configuration of the coins that the jailer assembles on the chess board. His algorithm is exactly the same as the second prisoner's algorithm except that whenever he's counting how many coins are showing heads up, he counts the coin on the magic square as if it was the other way up. Now we know both player's algorithms and so the complete strategy. That's it!

The above the most elementary way I can think of to describe a winning strategy but, as is often the case, the most elementary method is far from the most illuminating.

(b) I suppose one of the first things to do when considering a puzzle like this is to try to solve the smallest/easiest version of it. In this case this would be case where we have a 1x2 board and 2 coins. A moment's thought reveals that the problem is completely trivial in this case: the prisoners could agree the following obvious strategy. Let's call the two squares A, B. If the magic square is A then the first prisoner makes sure the square A has a coin showing heads on it. (He can always guarantee this by turning over the coin on square A if the jailer leaves it showing tails. Otherwise if the jailer leaves it showing heads, since he must turn over a coin he just turns over the coin on square B.) Similarly he makes sure square A is showing tails if the magic square is B. All the second prisoner has to do is to check whether square A is showing heads or tails. He knows that the magic square is A or B depending on whether heads or tails is showing respectively.

OK so what's the next biggest version of the puzzle? Well it was very convenient that there were 2 states (heads, tails) and 2 squares in the trivial case so we should probably not break this 2-ness completely. Bearing this in mind we should not blindly increase the number of squares and get a 1x3 board; instead we should recognise that we have just solved a 1-dimensional puzzle and increase the dimension of the puzzle by 1. That would give us 4 coins and a 2x2 board. How do we solve this? An obvious thing to try is to adapt the idea from the 1-dimensional (1x2) case so that we encode both a row and a column index (i.e. an index for each dimension of our now 2-dimensional problem). If we are as optimistic as possible (which we should always be!) then we would hope that the row and column indices are encoded independently and we really just have two versions of the 1-dimensional problem to solve. So let's think about encoding the column index first.

In the 1-dimensional problem, the unique square in the first column (A) encoded the column index. Let's hope this same idea will work in the 2-dimensional problem except it would not make sense to favour one row over another since we're only suppoed to be bother about columns so we'll allow both squares in the first column to encode the column index. When we were using 1 square to encode, we needed a mapping: $$ \{\mbox{head, tail}\} \to \{\mbox{column 0, column 1}\} $$ and we used a bijection (obviously either would work). We now need a mapping: $$ \{\mbox{(head, head), (head, tail), (tail, head), (tail, tail)}\} \to \{\mbox{column 0, column 1}\} $$ This map should be:

The second symmetry property means we should send the two points (head, tail), (tail, head) to the same column and in view of this and the first symmetry, we should send the two points (head, head), (tail, tail) to other column. This leaves two possible maps and we can obviously use either so let's use the map which sends the points (head, head), (tail, tail) to column 0 and (head, tail), (tail, head) to column 1. Another way of saying this is we choose column 0 iff it contains an even number of heads. We must now consider how the first prisoner may encode the column index in view of this. All he does is to look at which column the two coins in the first column are encoding according to the above map. If they are encoding the column of the magic square he does not want to change this and so must leave them alone and turn over a coin in the second column, otherwise he turns over either of them (it doesn't matter when we're just considering how to get the column correct) and hence toggles the column they encode to encode the column of the magic square. All of the above is the same for encoding the row of the magic square except we work row-wise instead of column-wise. So in summary: the encoded column index is toggled iff a coin in column 0 is turned over and similarly for rows. Thus depending on whether the row or column or both or neither indices need to be toggled the first prisoner chooses to turn over the coin in row 0 or 1 and column 0 or 1.

OK so that 2-dimensional version is solved and it was obvious once we thought about what symmetries should be preserved. In fact it should be clear by now that different dimensions do not interfere with each other so we can inductively solve the problem in any number of dimensions, e.g. 6-dimensions where we'll have 64 squares, i.e. the chess board. In other words we're finished! It's also worth noting that because the different dimensions are independent we can think of an N-dimensional version of the problem as the Cartesian product of an m-dimensional version with an n-dimensional version for any \( m, n\) such that \( N = m+n\). In the chess board case, because the board was naturally presented to us as \( 8\times 8 = 2^3 \times 2^3\) we thought of it as the Cartesian product of two 3-dimensional versions of the problem. The 3-dimensional version is most naturally thought about as a little cube of 8 squares but I wrote it above in linear form since this is how things crop up for the chess board. In case it's not completely clear already, we could also do this for the 2-dimensional version (i.e. we could represent the 2-dimensional version linearly instead of as a square). The patterns for counting whether we had an even number of heads in the square 2-dimensional problem were:

X o
X o
	
for columns and:
X X
o o
	
for rows. If we write things linearly, these become:
X o X o
and:
X X o o
If we linearised 3-dimensional version we'd get the patterns given in (a) above.

(c) What I described in (b) is I think a plausible, analytical attack on the problem which turns out to work (I think such analytical attacks are better for puzzles than real mathematics.) However it's possible to set things up rather more concisely and it might be worthwhile. One point of view is that we're looking for hash functions. There are many ways to describe the hash function corresponding to the solution we have outlined above. One way is using d-bit binary numbers, for the d-dimensional version of the problem. Specifically, if we let \( n = 2^d\), our hash function maps: $$ h : \{0, 1, ..., 2^n - 1\} \to \{0, 1, ..., 2^d - 1\} $$ and is defined by: $$ h(x) = x_1 \mbox{ xor } \cdots \mbox{ xor } x_k \mbox{ mod } 2 $$ where \( x_1, \ldots, x_k\) are the indices of the 1s in the binary representation of \( x\) (i.e. \( x = 2^{x_1} + \cdots + 2^{x_k}\)). xor is the exclusive-or operation on d-bit binary numbers which is of course the same as addition in the d-dimensional vector space over the field with 2 elements.

This has function has the property that: $$ h(2^m \mbox{ xor } x) = m \mbox{ xor } h(x) $$ Thus since \( a \mbox{ xor } a \mbox{ xor } b = b\) for any \( a, b\) this means that: $$ h(2^{h(x) \mbox{ xor } y} \mbox{ xor } x) = h(x) \mbox{ xor } y \mbox{ xor } h(x) = y $$ which is the statement that if the second prisoner computes h on the state of the board after the first prisoner has turned over the coin on square \( h(x)\) xor \( y\) then he find the square \( y\). In other words the above identity is the statement that the prisoners' strategy works.

A final note here is that all we're really doing in this problem is showing that the set of \( 2^{2^d}\) strings of \( 2^d\)-bit binary numbers can be partitioned into \( 2^d\) subsets such that any two subsets in the partition contain two points that are Hamming distance 1 from each other.

(d) One of the reasons I thought this puzzle was worth writing a bit about was that I thought was a good example of something that changes from looking a bit tricky to looking completely trivial when sufficiently generalised. Here's what I mean.

We can generalise this problem as follows. Take a commutative ring (with unit) A and an A-module M. Consider the A-module: $$ \hat A^M = \{ g : M \to A \mbox{ such that g is finitely non-zero} \} $$ There is a natural A-linear map: $$ h : \hat A^M \to M $$ defined as: $$ g \mapsto \sum_{m\in M} g(m)\cdot m $$ Note also that given any \( m \in M\) we have \( e_m \in \hat A^M\) defined by: $$ e_m(m') = \begin{cases} 1 & \mbox{if $m = m'$}\\ 0 & \mbox{otherwise} \end{cases} $$ and that we have: $$ h(e_m) = m $$ and so we have the key identity: $$ h(e_{m-h(g)} + g) = m $$ for all \( g \in \hat A^M\). In this setting, the above identity is the statement that the prisoners' strategy works. In the case of the prisoners we have:

A configuration of coins on the chessboard represents an element \( g \in \hat A^M\) in this case by identifying tails with \( 0 \in GF(2)\) and heads with \( 1 \in GF(2)\). Thus the jailer's chosen function g sends a point in M to the value of the coin (using the tails/heads = 0/1 identification) on that square.

Other than the fact that the hash function h in this setting is essentially the only non-trivial natural map (and so the solution is essentially obvious) I also like this generalisation because it gives us a recipe for generating new puzzles. We need only plug in a given ring and module to the above construction and then look at the resulting problem. Also note that this is certainly not the most general setting for the problem. For example, the "finitely non-zero" condition is a bit of a cop-out, we could really replace this with an appropriate measure (which would then have to be supplied). Also, we should notice that in the key identity, the dummy variables g, m are redundant. It should be possible to find a maximally general category in which the key identity can be stated in a point-free form (maybe).

(e) I'd like to finish by seeing what sort of puzzles we get by plugging different A-modules M into the above generalisation of the problem. The puzzles will all have the same flavour of course. Here are a few examples of the resulting puzzles and their corresponding modules (you should find it trivial to solve them if I've explained the above properly!):

I guess the last thing on my mind regarding this puzzle are the possibilities for interesting versions for non-free modules and perhaps an interesting infinite dimensional example but this is probably enough for now!