User:Cnzx/Drafts/The condemned prisoners and the boxes

The condemned prisoners and the boxes is a problem in recreational mathematics.

Problem

There are 100 condemned prisoners who are offered a chance to play a game to gain a reprieve. In the game, there is a room in which there are 100 identical closed boxes placed on a long table. Each box contains the name of one prisoner, with no prisoner's name being repeated. One prisoner is allowed to enter the room at a time, When a prisoner enters the room, they may open 50 boxes of their choosing. The prisoner then must leave the boxes exactly as they were found, and may not communicate with other prisoners until the game is over. This process is repeated until all of the prisoners have finished. The prisoners will be granted a reprieve if and only if all of them had found their name when opening the boxes. Therefore, it is necessary that every prisoner find his name or all will be executed.

Although the prisoners may not communicate during and after the process, they are informed of the game in advance and may communicate to determine a strategy.

Solution

Given that each prisoner has a half chance of finding their name, one would expect the probability of surviving to be

${\frac {1}{2}}^{100}\approx 7.88*10^{-31}$

However, this is not the case.

References

Category:Recreational mathematics