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.
"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 ..."
"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."
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.
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?
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?
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.
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 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.
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:
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.
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:
In researching the origins of this problem I've discovered that it's referred to as "The Devil's Chessboard." In one discussion someone dismissed the puzzle saying:
Here is some further reading:
 "Two applications of a Hamming code" -- Andy Liu, Mathematics Magazine, January 2009
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.