Simulating the Riddle of 100 Prisoners.
I've developed a simulator for the 100 prisoners problem (optimal solution), which allows you to interactively explore different strategies and see how they impact the prisoners' chances of success in this challenging thought experiment.
Watch the video to understand the riddle or see learn more.
The actual riddle of the 100 prisoners.
Source:
Wikipedia
"The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners' best strategy?""
Pretty Unlikely
At first glance, this seems a pretty hopeless problem. In fact, it appears that the chances of all the prisoners finding their own tickets is microscopically small. After all, there is no way for the prisoners to communicate any information to each other.
With just one prisoner, he has a 50:50 chance. There are 100 boxes, and he gets to open (up to) 50 boxes looking for his ticket. If he opens the boxes at random he’ll open half the boxes, and his ticket will, or, will not be in the half he opens. His chance of success is ½.
With two prisoners, if both select at random, it would also by ½ chance of success each, so for two prisoners, it is ½ × ½ = ¼.
(They will succeed one time in four).
For three prisoners it’s ½ × ½ × ½ = ⅛.
With 100 prisoners, it’s ½ × ½ × … ½ × ½ (100 times).
This is:
Pr ≈ 0.000000000000000000000000000008
That’s a pretty small chance. It appears as though the prisoners are as good as dead.
Source:
DatageneticsOptimal Solution
The strategy is amazingly simple. First of all you open up the box corresponding to your own number. If you find your ticket, great!, if not you look up the number on the ticket in your box and that is the box your check next. You carry on this strategy … daisy-chaining your way through the boxes. That's it!
31.18% of the time, the length of the maximum chains formed will be less than 50 boxes and so every prisoner will be able to find his ticket before hitting the 50 box limit.