The Prisoners and the Chessboard Solution

 Two weeks ago, I posted the following puzzle:

So, the evil guy who kidnaps people and sets them bizarre mathematical tasks which they have to complete or be executed has kidnapped you and your friend Bob. He sets you the following bizarre mathematical task:

I will take you into a room in which there is a chessboard. There is a coin on every one of the squares of this chessboard, showing either heads or tails. I will then tell you which one of the squares has the key to the door of the prison under it. After this, you will be allowed to turn over exactly one of the 64 coins and then be escorted from the room.

Immediately after this, Bob will be brought in, and will be asked to find the key. If he can locate it you're both free to use it to unlock the prison and leave. If not, you'll both be eaten by rabid wildebeest.

You and Bob are free to discuss a strategy before you are taken into the room with the chessboard - what should you do?

Adrianna emailed me a (sort of) solution less than a few hours later. I've posted my solution (and hers) below the fold).
Here's what adrianna sent me:

in order to specify exactly the position you need 6 bits of information.
You can get one bit of information by having a region and if there are an even number of heads, assign it to zero, if there are an odd number, assign it to 1.
You could always assign it the value you wanted if there is at least one square outside the region that you can flip if it starts off being the value you want.

if you had two regions you could get two bits provided you had a square outside both, a square inside both and a square in each that was outside of the other.

For six regions (6 bits) you could make them all have te value you wanted if you had every combination of regions overlapping on a square. One square for region 1 only, one for 2 only, one for 3 only, one for 1+2, one for 1+3, one for 1+2+3 etc.

So you would need:
6 choose 1 + 6 choose 2 + ... + 6 choose 6 = 63 squares which leaves one to be outside all regions.

 This idea works, and in fact, is not that hard to implement. I think for your 6 regions you can pick "black squares", "odd numbered rows", "odd numbered columns", "the top half of the board", "the left half of the board" and I'm not quite sure how you pick the other one, but I think it should be doable.

My solution is somewhat different, and requires thinking about the problem in a different way. You have 64 possible moves, and 64 possible messages that you want to send. This means you need to divide the possible arrangements of the board into 64 equivalence classes, such that every board is adjacent (ie, one coin-flip away from) a representative of each of the 64 equivalence classes.

When you think of the problem this way, if you're used to thinking about these sorts of problems, the idea of the 'Nim Sum' seems to jump out at you. For those who don't know, Nim Sum is a combinatorial game theorists way of writing 'bitwise XOR'. So, how does that idea help?


Well, we'll number the squares (in binary) and then we'll call the "state" of the board the Nim Sum of all the positions which contain a head. I claim that, whatever state you find the board in, you can leave it in any of the possible 64 states. Again, if you've ever played around with this sort of thing, this might appear obvious.

If you find the board in state x, and you want to leave it in state z, you simply flip the coin in square number x(+)z (where (+) means 'bitwise XOR', or Nim Sum). Why does this work? Well, we wanted to find a y so that x(+)y = z. Adding x to both sides, we get y = x(+)z. Essentially, the point here is that (+) is an involution on the set of binary integers, so x(+)x = 0.

If you want to think about this differently, just think that there are 64 things we can add to x, and each of them gives a different value (because if x(+)y = x(+)z then y = z by adding x to both sides), so each of the 64 different board states must be achievable.

No doubt there are other ways of looking at this problem. In fact, I'm pretty sure there are some interesting generalisations. For example, what if, instead of having a coin on each square, we have a six-sided dice? I think this is still do-able, although it's hard to explicitly generalise either of the ideas I've used above so that they work.