You and a friend are imprisoned but have a chance for freedom. To earn it, you must walk alone into a separate room where a chess board is laid out with a coin per square randomly showing heads or tails. You are shown a particular square on the chess board, and are then allowed to touch one coin to flip it. Then you must leave without making any contact with your friend. Your friend enters the room and must pick the square which was pointed out to you. You and your friend may discuss a strategy before you enter the room.
This site contains the problem in more detail, along with the solution in mathematical terminology. However, I thought I'd share the way that I thought through this problem using plain English, without the mathematical language.
One big clue is that we have to use coins in this puzzle to transfer information. Coins can be heads or tails. This suggests the information we send to the other prisoner about which square leads to freedom might be done through using yes/no questions. In other words, a yes/no question can be answered by which side of a coin is face up.
Let's see if that idea would work.
First we have to know if a series of yes/no questions can uniquely determine the square's location. Clearly, yes. For example, I could ask "Is it square number 1? Number 2? Number 3?..." until the answer is yes. But that's inefficient. I only eliminate one square at a time. What's the best question to eliminate the most squares? I can eliminate half the squares at a time by asking questions which successively split the board in two parts.
Here is one possible series of questions which cut the board in half each time:
This makes 6 questions total, and that's very efficient. In fact, mathematically, you can't do better than 6 questions, but we won't get into that.
We should agree with our fellow prisoner in advance on the 6 specific ordered questions to use. Can we figure out a way to indicate the answer to the 6 yes/no questions using the coins? If we had 6 coins available to change, we'd be home free. In that case, we would simply plan with the other prisoner to set the first 6 coins as the answers, with heads meaning "yes" and tails meaning "no". But, we can only touch one coin on the board. This is the hard part.
The next realization to make is that we don't necessarily need to just use single coins to represent the answers "yes" and "no". We can instead look for a way to use specific groups of coins to somehow produce answers to each question. In that case, it might be possible to cleverly structure the coins into groups so that some coins belonged to multiple groups. That way, flipping one coin could actually affect some or all of the question's answers.
How might that work? Let's think it through.
First, is there a way to use a group of coins to get a single yes/no answer such that changing one coin in the group changes the answer? Yes. We can check whether the group of coins has an even or odd number of heads. An even number of heads can mean "yes", and an odd number can mean "no". This way, flipping any one coin in the group changes the answer for that group.
Now, how can we arrange the groups? We have 64 available coins, and we'll need 6 groups (one group per question). Once we know which coins form each group, then the randomly placed coins will automatically create 6 random answers. We can then figure out which answers need to change. We want a coin available that belongs to only the groups for the answers we want to change. Therefore, we need some coins which belong to only one group, and other coins which belong to several groups at once. And each possible combination of groups must have one coin somewhere on the board which is unique to that group combination.
To see how we might accomplish this, let's first simplify it and imagine we only need 2 groups. What would that simpler scenario look like?We'll make the first square only belong to the first group. Changing that coin only changes the first answer. Similarly, let's make the second square only belong to the second group so we have a way to only change the second answer. Finally, we'll make the third coin belong to both groups, so that we have a way to change both answers simultaneously with one coin flip. A map indicating which squares belong to which groups would look like this:
We just used 3 coins to create 2 groups such that we can choose a coin to change either or both answers any way we like by one flip. No matter what the initial random layout is of those 3 coins, we can figure out which answers need to change, and then flip one coin to change just the specific answers we need.
But that's the simple imaginary scenario of just 2 yes/no questions. What would the groups look like for 3 questions? Again, we need a square for every possible combination of questions. That would take 7 squares and look like this:
How many squares do we need for all 6 questions? The grand total is 63. Luckily, we have 64 squares on a chessboard. Coincidence? This is one possible mapping of squares to groups, which you and your fellow prisoner would agree to use beforehand:
And so, to sum up, your strategy would be:
At this point, the jailer is likely to be hopping mad, so you might want to just go. Quickly.