One hundred people, one hundred boxes, and no chance to communicate once the game starts. At first glance, the odds seem overwhelming. However, there is a strategy that transforms the seemingly impossible into something that happens almost one in three times.
The hundred numbered boxes
Riddle statement
There are 100 prisoners numbered from 1 to 100 and 100 boxes also numbered from 1 to 100. Inside each box there is a different number from 1 to 100, placed at random.
Before starting, the prisoners can agree on a common strategy. Then they enter the room one by one. Each prisoner can open a maximum of 50 boxes, must close them as they were and leave without communicating anything to the others. Prisoner i is successful if he finds the number i inside any of the boxes he opens.
The entire group is saved only if all 100 prisoners are successful. Which strategy gives them the greatest chance of being saved?
Show solution
Solution
Optimal strategy: each prisoner follows the permutation cycle that begins at his own number.
The procedure is as follows:
- Prisoner $i$ first opens box number $i$.
- If you find your own number inside, you have finished successfully.
- If you find another number $j$, then open box number $j$.
- Repeat the process until you find its number or until you have opened 50 boxes.
The placement of the numbers inside the boxes defines a permutation: each box points to the number it contains, and that number indicates the next box to open. Following this chain from box $i$, the prisoner cycles through exactly the cycle of the permutation containing the number $i$. It will find its number if and only if that cycle has length at most 50.
Everyone survives exactly when the permutation contains no cycle of length greater than 50.
The probability that a cycle of length exactly $k$ exists, for $k > 50$, is $1/k$. Since two cycles of length greater than 50 cannot coexist, the probability of failure is:
The probability of success is then:
approximately 31%.
Compared to opening boxes at random —whose collective probability is around $(1/2)^{100}$, an infinitesimal number—the cycle strategy is incomparably superior.