Today’s puzzle involves two prisoners. Let’s call them Piper and Alex. You will be asked to find a strategy that wins them their freedom.
Puzzles about prison escape strategies are a relatively new genre of mathematical challenge, only a few decades old. They emerged from computer science. A prison – a place where access to information is limited – is a perfect venue for puzzles about the efficient communication of information.
The solution to today’s puzzle will blow your mind. Lock me up if it doesn’t.
Now back to Piper and Alex.
The four boxes
Piper and Alex share the same cell. A guard comes in and tells them that they are to be set a challenge that may win them their freedom. It involves both prisoners being taken one after the other into a separate cell where there are four identical empty boxes, numbered 1, 2, 3 and 4. The procedure is as follows:
i) Piper will be led into the new cell. The guard will then take a piece of paper from his pocket and randomly place it into one of the four boxes. Piper will see which box the paper is in. The guard will shut the boxes. He will flip a coin and place it on Box 1. He will flip another coin and place it on Box 2, and so on for Boxes 3 and 4. Each coin has a 50/50 chance of being heads or tails. Piper will be able to see the faces of all coins.
ii) Piper must turn a single coin over. (She can choose any one of the four coins, and when she does, a head becomes a tail, or vice versa.) She will then be led out the cell and taken to a third cell on her own.
iii) Alex is now taken into the cell with the boxes. She will not be able to see inside the boxes since they are closed. But she will be able to see the faces of the coins. She will be asked to open a box. If the box has the paper in it both prisoners are freed. If it doesn’t have the paper in it, the prisoners are returned to their cell.
What strategy guarantees that the prisoners will win their freedom?
The prisoners are allowed to discuss their strategy before Piper is taken into the cell with the boxes, and settle on a plan. But once Piper goes into that cell she has no communication with Alex, apart from the ‘message’ that she gives by turning over a single coin.
This is an amazing puzzle because it seems utterly impossible that there is a way Piper can convey to Alex with a single coin which box has the paper in it when she needs to take into consideration the four possible locations and 16 possible combinations of heads and tails. You will marvel at the result when you see it.
Like many puzzles, the way to tackle this one is to simplify the situation, to see if any insights jump out. Let’s do that. Try to solve exactly the same puzzle when there are only two boxes in the cell. That is, Piper will be led into a room with only TWO boxes. The guard goes through the rigmarole of putting the paper in one of the boxes, and placing a coin randomly on each box. Each coin has a 50/50 chance of being heads or tails. Piper will be able to see the faces of both coins.
When there are only two boxes, how does Piper communicate which box has the paper by turning over only one coin?
In other words, what strategy guarantees that the prisoners will win their freedom?
If you solve the two-box version, you’ll be doing well. If you solve the four-box version, you are top of the class.
I’ll be back at 5pm UK with the solutions. Meanwhile, NO SPOILERS. Instead discuss your favourite prison movies and which two prisoners you think would have had the best chance of solving this puzzle.
Thanks to Pierre Chardaire, a retired computer scientist, who wrote the puzzle.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
I give school talks about maths and puzzles (online and in person). If your school is interested please get in touch.
