Prisoners and Boxes
There are 100 inmates living in solitary cells in a prison. In a room inside the prison there are 100 boxes and in each box there is a paper with some prisoner’s name (all different). One day the warden tells the prisoners that he has aligned next to the wall in a special room 100 closed boxes, each of them containing some prisoner’s name (all different). He will let every prisoner go to the room, open 50 of the boxes, then close them and leave the room the way it was, without communicating with anybody. If all prisoners find their names in the boxes they open, they will be set free, otherwise they will be executed. The prisoners are allowed to come up with a quick plan before the challenge begins. Can you find a strategy which will ensure a success rate of more than 30%?
The prisoners can assign numbers to their names – 1, 2, 3, … , 100. When prisoner X enters the room, he should open first the X-th box in the line. If he sees inside prisoner’s Y name, he should open next the Y-th box in the line. If he sees in it prisoner’s Z name, he should open next the Z-th box in the line and so on.
The only way which will prevent all prisoners from finding their names is if there is a long cycle of boxes (length 51 or more), such that the first box in the cycle directs to the second box in it, the second box to the third box, the third box to the fourth box and so on.
It is not hard to compute that the probability of having a cycle of length K>50 is exactly 1/K. Then the probability for failure will be equal to the sum 1/51 + 1/52 + … + 1/100, which is very close to ln(100) – ln(50) = ln(2) ~ 69%. Therefore, this strategy ensures a success rate of more than 30%.
