Earlier today I set you a puzzle about Piper and Alex, two prisoners who are set a seemingly impossible challenge.
Here is the problem again, this time with the solution.
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 women are freed. If it doesn’t have the paper in it, the women 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’ she gives Alex by turning over a single coin.
Solution
I suggested that the way to tackle this problem is to simplify the situation, to see if any insights jump out. Let’s start by solving the exact 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. Piper knows which box has the paper, and she can see both coins, each of which has a 50/50 chance of being heads or tails.
Piper must turn only one coin over and then leave the room. How does she communicate with that ‘move’ which of the boxes has the paper?
In this case, the solution is almost trivial. Here’s the simplest strategy: the prisoners decide that one box will take the role of ‘indicator’, that is, the coin on it will indicate where the paper is. Let’s say they decide that Box 1 is the indicator box, with the rule that if the coin on Box 1 is heads, the paper is in Box 1, and if the coin on Box 1 is tails, the paper is in Box 2.
So, if Piper sees the guard put the paper in Box 2, all she needs to do is make sure that the coin on Box 1 is showing tails. If the coin on Box 1 is heads, she turns it over, and if it is tails, she turns the coin on Box 2. (Which is fine, since the status of the coin on Box 2 is irrelevant to the identification of the correct box.)
Now to the four box version. The solution uses the same idea. In this case, three boxes, lets say Boxes 1, 2 and 3, will make up the ‘indicator’. As above, the coin on the remaining box, Box 4, is only turned if the coins on 1, 2 and 3 are indicating the correct box.
Let’s look more closely at our three-box indicator. There are eight possible positions of the coins on these boxes:
HHH, TTT, HHT, TTH, HTH, THT, THH and HTT
What is remarkable and unexpected (or it certainly was to me!) is that there is a way of assigning combinations to indicate boxes in such a way that whatever the given combination of coins, you can indicate any of the four boxes by turning over at most one coin.
Here’s a way to do it. Let the combinations indicate the boxes in the following way:
Box 1: HHH and TTT
Box 2: HHT and TTH
Box 3: HTH and THT
Box 4: THH and HTT
In other words, if the first three boxes have HHH, or TTT, then this means that the paper is in Box 1, and so on.
Now just say Piper wants to indicate Box 2. And let’s say that when she arrives in the cell, the boxes show HTH (which indicates box 3). All she needs to do is turn the first coin over, to get TTH, which indicates box 2.
If you look closely at the combinations, you can get from a combination that indicates any box, to a combination that indicates any other box by turning over a single coin.
This diagram may help you see what is gong on. Blue indicates box 1, red Box 2, pink Box 3, and green Box 4. Combinations are linked to other combinations that involve only one coin being turned over. Every combination is linked to three other combinations, each of a different colour.
The diagram tells us that whatever combination on our ‘indicator’, we can change it to indicate another box by turning over a single coin. Now what about if Piper sees a combination that is already indicating the correct box? Easy: she turns over the coin on Box 4. (Just like in the first challenge, we need a ‘redundancy’ box whose position has no bearing on the indication.)
It’s a stunning result. Whatever combination Piper sees on the first three boxes, she can change it to whatever combination she needs, by turning over at most a single coin.
If you want to read more about the mathematics behind this puzzle, a more complicated version using a chessboard originally appeared in the Data Genetics blog and was discussed by maths communication legends Matt Parker and Grant Sanderson (aka 3blue1brown) in this video here.
Pierre Chardaire, a retired computer scientist, simplified the chessboard puzzle to create the version we have solved here.
I hope you enjoyed today’s puzzle, I’ll be back in two weeks.
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.
