The 100 prisoners problem was stated as follows by Philippe Flajolet and Robert Sedgewick:
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 his number in one of the drawers, all prisoners are pardoned. 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 each prisoner opens 50 drawers at random, each has a 50% chance (probability ½) of finding his number. Thus, the probability of all 100 prisoners finding their number is (\frac{1}{2})^{100}\approx 0.0000000000000000000000000000008. Can you devise a better strategy—one which is a lot better?