100 prisoners problem
The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem,100 numbered prisoners, to survive, must find their own numbers in one of 100 drawers, the rules state that each prisoner may open only 50 drawers, and cannot communicate with other prisoners. At first glance the situation appears hopeless—but a clever strategy offers the prisoners a chance of survival. Danish computer scientist Peter Bro Miltersen first proposed the problem in 2003, the 100 prisoners problem has different renditions in the literature. The following version is by Philippe Flajolet and Robert Sedgewick, The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a room contains a cupboard with 100 drawers. The director randomly puts one prisoners 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 his number in one of the drawers, if just one prisoner does not find his 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. If every prisoner selects 50 drawers at random, the probability that a single prisoner finds his number is 50%, the probability that all prisoners find their numbers is the product of the single probabilities, which is 100 ≈0.0000000000000000000000000000008, a vanishingly small number. Surprisingly, there is a strategy that provides a probability of more than 30%. The key to success is that the prisoners do not have to decide beforehand which drawers to open, Each prisoner can use the information gained from the contents of previously opened drawers to help decide which drawer to open next. Another important observation is that way the success of one prisoner is not independent of the success of the other prisoners. To describe the strategy, not only the prisoners, but the drawers are numbered from 1 to 100, the strategy is now as follows, Each prisoner first opens the drawer with his own number.
If this drawer contains his number he is done and was successful, the drawer contains the number of another prisoner and he next opens the drawer with this number. The prisoner repeats steps 2 and 3 until he finds his own number or has opened 50 drawers and this approach ensures that every time a prisoner opens a drawer, he either finds his own number or the number of another prisoner he has not yet encountered. The reason this is a strategy is illustrated with the following example using eight prisoners and drawers. The prison director has distributed the numbers into the drawers in the following fashion The prisoners now act as follows, Prisoner 1 first opens drawer 1