A hundred Prisoner Problem
Problem
You have a room with 100 boxes each with a piece of paper with one of the numbers 1 to 100 on them (every number is in one of the boxes). Each prisoner is also numbered with an inmate number between 1 and 100.
The chief of the prison give the prisoners a chance to to be free. They all get a chance to enter the room and open 50 (maximum) of the 100 boxes. If any of the boxes contain the paper with their own inmate number they have succeeded. If all the prisoners succeed to find their inmate number they will all be set free. If one of them fail no one will be free. Some rules apply.
- After each prisoner have left the room the boxes and papers are returned to the same state and order as it was before entering the room
- The prisoners are allowed to speak to each other before starting the challenge, but not during the challenge
So what are the chances that the prisoners will be set free? If each prisoner open 50 boxes randomly when entering the room the chance of finding the box with their inmate number will be 50%. The probability that all prisoners succeed is then (0.5)^100 = 1/(2^100) which is an extremely slim chance.
What if I said that there are a simple strategy that raise the probability to about 1/3. Would you believe me? Could you give some guidance to the prisoners to increase their chances?
Solution
The solution and a good explanation is included in the first reference below (PDF).
The strategy is simple. Always start with the box with your number on it. Then take the box with same number as the paper in the first box. Continue the same way until you find the paper with your number on it. All prisoner should use this same strategy.
In this way you will find your box if the sequence of opened boxes ends with a box with your number on it and if that total sequence is below 50 boxes. Note that all prisoners that starts with any of the boxes in the same sequence (the sequence is cyclic) will find their number in the last box they open. The only difference between these prisoners is that they start the cyclic sequence at different locations. So the probability that all prisoners succeeds to find their number is the same as the probability that the maximum sequence among the 100 boxes are below or equal to 50.
References
- The condemned prisoners and the boxes
- The 100 prisoners puzzle - A python program to further motivate why this is true