Another Flipping Puzzle ...

Colin Wright
Recreational Maths Colloquium
Lisbon, 2015

The setup ...

Where is the prize?
Standing up on stage, the performer announces that he has two assistants who will be sent out of the room and called back later. As they leave the room, the performer calls for a volunteer from the audience. One is selected, and they start making their way to the stage.

As they are on their way the performer then reveals a four by four grid, currently empty, and explains that the volunteer will choose one of these 16 places to hold an item of great value. All the places will then be covered by identical black covers. The performer will, he explains, then be permitted to swap one, and only one, black cover for a white cover, and will then leave the stage. The assistants will then return and somehow, magically, divine where the item of great value is hidden.

By now the volunteer has reached the stage, but the audience seems unimpressed. Surely this is trivial nonsense. Surely the performer will simply change the cover over the item of great value to white, and it's then completely obvious where the item is hidden.

Sensing that the audience expected more, the performer acknowledges that the trick is not that difficult.

Where is the prize?
"So!" he says, "to make it more difficult I will allow my volunteer not only to choose a place to hide the item, but also to change one of the covers to be white. Only then will I change the colour of just one of the covers (which may be the same one!) and again, my assistants will be able to find the item of great value.

"Hmm" says the audience. "That's a bit trickier. How would the two assistants know which cover the performer changed? There are now two white covers - or none - so ... hmmm. I could probably work that out ..."

The trick ...

"Enough!" says the performer. "Let's make it really interesting." He turns to the volunteer. "Choose your hiding place, then cover everything, each with black or white, each of your own free will. Do what you like - any pattern you choose. I will then swap one, and only one, changing white for black or black for white, and still my assistants will find your item."

Where is the prize?
The audience is now intrigued. There seems to be no way that can be done. The volunteer chooses a hiding place, then covers all the places haphazardly. There seems to be no pattern at all. The performer then takes a moment, strokes his chin theatrically, and decides on which one to change. He reaches forward, then mutters "Yes? No?" retracts his hand, and then reaches forward decisively - "Yes."

To avoid the audience suspecting that there is a secret vocal code, he gets the volunteer to call the assistants, and leaves the stage. The two assistants enter, and start discussing sotto voce con animato -- "Here? "No, here." "You sure?" "Yes, counting from there." "Ah! Yes." Finally they agree, point at a cover, and lift it up to reveal the item of great value.

Success!

But how?

The reveal ...

At this point you may choose to put this article down and try to work out how it's possible. Yes, the volunteer may have been part of a secret, but she wasn't. Yes, there may have been a secret vocal code, but there wasn't. Why two assistants? Because they had only been trained the night before, and were not entirely confident, so it was important that they be able to discuss and agree.

But how can it be done so quickly, and with so little training on the part of the assistants? There must be some sort of code in the pattern of white and black, but how can the performer achieve the feat of specifying any square, given that he can change only one?

And how can he work out which one to change so quickly?

(Pause)

Are you still reading? Have you tried this for yourself? What ideas did you come up with? Have you solved it? Have you tried it out on your friends? Have you tried different sizes of board? Can you prove that the method you have is the only one possible?

Have you generalised to more than two colours? Is this a simple example of a more complex, abstract, comprehensive system/structure?

What's really going on?

(Pause)

Are you still reading? Soon the performer's method will be revealed, and if you haven't worked on this first then you will nod sagely, say "I suspected as much" and move on. If you have then you will punch the air and shout "Yes!" if you got it right, and understand more fully and completely if you hadn't.

(Pause)

A solution ...

So here is the simple description: The black/white configuration on the board encodes a location given by the NIM sum of all the white covers.

Well, that description is only simple if you know what a NIM sum is, and all the implications that follow. Here is a more elementary description.

You now have a number from 0 to 15. Count from the top left, starting with 0, count that many places, and that is the encoded location.

You can check that this works in the simplest case: set only one cover to be white. You will find that it encodes its own location. That's because if you number the locations in binary, the last two rows have the top bit set, corresponding to 8. The second and fourth rows have the second bit set, corresponding to 4, and so on.

For those unfamiliar with the NIM sum, it is the bit-wise addition in binary with no carries. Thus the NIM sum of 0101 and 0011 is 0110, and the NIM sum of 1110 and 0111 is 1001. The NIM sum is commutative and associative, has identity 0000, and every number is its own inverse. It can also be thought of as the bit-wise Exclusive-OR, or XOR, of the numbers in binary.
Now flip two covers to be white, and you'll find that the encoding gives the NIM sum of the two locations. This works recursively to give the result that the NIM sum of all the white locations encodes the location as described in the procedure above.

So that's what the assistants have to do - to read the board and decode the position. But how does the performer decide which cover to change?

That's just as simple. Read the existing board, NIM sum that with the desired location number, and the answer is the cover to change. This can be done in a singe reading as follows:

With practise, this can be done on an 8x8 board. Label the squares in binary starting from 0, and look at which squares have the top bit set to 1. They contribute 32 to the running total. Look at which squares have the second bit set - they contribute 16. And so on. It is made simpler to decode the rows to give a number from 0 to 7, then the columns to give a number 0 to 7, multiply the first by 8, add the second, and you get the final result.

There are many short-cuts, and different short-cuts suit different people. Without doubt, the best ones are the ones you come up with yourself.


Uniqueness, and generalisations ...

So is this the only solution?

There are many, many equivalent encodings. We can choose any labelling of the squares from 0 to 15. For each square we can choose whether 0 is represented by black or white. That gives us an encoding. We can then choose a different labelling of the squares for mapping the encoded value to a square. Each of these is clearly a valid encoding, although the one given is the simplest.

Further, consider two possible encodings. We can derive a mapping from one board to the other by taking a blank board, flipping one in each, and mapping the encoded square of one to the encoded square in the other. So there is a natural mapping from one board to another, and it turns out that this is consistent, and implies an isomorphism between the encodings. So up to obvious and natural transformations there is only one solution.

There are also other ways to think about the problem. One version is to ask:

Most people find this formulation less easy to visualise than a board with black and white markers, although surprisingly, not all.

We can also seek interesting variations on a theme and ask about different sizes of board, different possible colours beyond just two, and so on. Perhaps there are many problems of this type waiting to be discovered, and this is just the beginning.

References, and further reading ...

In researching the origins of this problem I've discovered that it's referred to as "The Devil's Chessboard." In one discussion[2] someone dismissed the puzzle saying:

They then gave reference [0] below:

To someone well versed in the theory of Hamming Codes this probably does turn out to be trivial. In fact, for someone well versed in the ideas of NIM sums it's fairly straight-forward to produce a solution, suggesting that there is value in knowledge of both areas.


Here is some further reading:

[0] "Two applications of a Hamming code" -- Andy Liu, Mathematics Magazine, January 2009

[1] "Yet another prisoner puzzle" -- Oliver Nash, blog post [2] "Coins on chess-board puzzle" -- Nicholas Nash, Google groups post [3] "The Prisoners and the Chessboard Solution" -- John Faben, blog post [4] "Impossible Escape?" -- DataGenetics blog post A web search for "The Devil's Chessboard" turns up many more references, although very few explorations of generalisations.


The author

Colin Wright has a PhD in Pure Maths (Combinatorics and Graph Theory) from Cambridge University, and is a part time teaching fellow at Keele University. He is also a director of Denbridge Marine Ltd, a company that specialises in Maritime Surveillance, and Solipsys Ltd, a company that specialises in mathematical enrichment and enhancement for students of all ages.

He also unicycles, juggles, ballroom dances, and fire-breathes, although not all at the same time.