How to solve the Impossible Escape puzzle with almost no math

How to solve it

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.

Using yes/no questions to locate the square

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:

1. Is the square in the left half or right half of the board?
2. Is it in the top half or bottom half of the board?
3. At this point, we know which quadrant the square is in. Using that 4x4 quadrant as a new "board", ask the above two questions again, narrowing it down to a 2x2 area.
4. Ask the first two questions once more about the 2x2 area, and we'll have narrowed it down to the exact square.

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.

Combining coins

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.

Building the groups

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.

That's impressive.

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:

Putting it all together

And so, to sum up, your strategy would be:

1. Take the above mapping into the room (or memorize the pattern) and look at the chessboard with the random coins.
2. The jailer tells you the secret square to your freedom.
3. Determine what the answers to the 6 questions should be for locating that square.
4. Look at your map, find all squares with "1", and count heads in those squares.
5. Remember this question if the count of heads leads to the wrong answer for question #1 (remembering that an even number of heads means "yes" and an odd number means "no").
6. Repeat the above two steps for all 6 questions.
7. You now know which question numbers need to be changed. Find the one square on your map that contains that unique combination of numbers, and flip that coin so that just those answers change.
8. Leave the room and your fellow prisoner will use a copy of the same mapping and questions to find the right square and earn your freedom.

At this point, the jailer is likely to be hopping mad, so you might want to just go. Quickly.