This is one of the most difficult riddles I have ever encountered. It does not require a lot of mathematical skills, but you certainly have to have some intuition in solving riddles. This riddle is called “The 100 prisoners problem”. Do you have what it takes to solve this challenge?
Problem
100 prisoners are given the chance to be released from prison. Their names will be put in 100 different labelled wooden boxes. These boxes are labelled with the names of the prisoners, but the name in the box is never the same as the name on the box. Every prisoner has a different name. The wooden boxes are lined up on a table in a room with one entrance and one exit. One by one the prisoners may enter the room. When the room is entered they have to go through the exit, so there is no communication possible with the other prisoners when the first prisoner enters the room. Each prisoner is allowed to look in 50 boxes, but must leave the room when he or she finds his or her name in the box. The prisoners have a chance to plot a strategy before everyone enters the room. This will be very important because they will only be set free when every single prisoner finds his or her own name. Find a strategy for them such that their probability of success is maximized.
Goal: “Find the best strategy such that the probability that the prisoners will be released is maximized.”
Conditions:
- When the first prisoner enters the room there is no communication allowed.
- Each prisoner is allowed to look in 50 boxes, but has to stop when he finds his name.
- The prisoners are only allowed to enter the room one by one.
- Every wooden box is labelled with a name (name in the box is not the same as the name labelled on the box).
Sketch
Example of a box. (the name in the box will always be different)
Solution
If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable (1/2)100 ≈ 0.0000000000000000000000000000008. They could do worse if they all look in the same 50 boxes, their chances will drop to zero. So we need a different strategy. A study has shown that the best strategy will get a probability of 31.18%. How?
Every box is labelled with a name of a prisoner. The best strategy is that every prisoner first looks at the box with their own name. So the first prisoner that enters the room looks in the box with his own name on it. He is allowed to look in 50 boxes so he continues to look in the second box of the name he just found in the first box. Then he will look in the third box belonging to the name he found in the second box, until he finds his name or looked in 50 boxes. The second prisoner and all the others will do exactly the same. If they use this strategy they will always find their name if the cycle where their name is in is smaller or equal to 50, since we are only allowed to open 50 boxes. For example, if your name is in the 51th box of your cycle, you will obviously not find your name. So if your name is within the cycle we will always find our name. For everyone to find their name, every name has to be within their cycle. So it could be that only one prisoner has his name in the 51th box in his cycle, then no one is set free. Hence every name must be within this cycle of 50 boxes to make sure the prisoners are set free. As mentioned before, the probability that every name is within this cycle is 31.18%.
This is a visual representation of the best strategy.
Dit artikel is geschreven door Sam Ansari
