An image showing a possible setup for the 100 prisoners problem.
The 100 prisoners problem is a math-based puzzle involving prisoners, boxes, and a very specific set of rules. Simply put, it is a puzzle in which 100 prisoners have to find their own number in a room full of boxes. In this article, we will talk about how this puzzle goes and how to go about solving it.
First, as mentioned earlier, there is a set of 100 prisoners, each with a different number from 1 to 100. Then, there is a room with 100 boxes, each containing one of the numbers from 1 to 100. The numbers in the boxes are shuffled at random, with no one knowing which number is in which box. The prisoners enter the room one at a time and are not allowed to communicate with each other. Each prisoner can open up to 50 boxes on his or her turn. If one finds his number among those, he leaves the room and the next one enters. If some prisoner does not find his number, they all lose. If each prisoner is able to find his number, they all win and get released from jail.
At first glance, the chances of winning this game would appear very slim. The chances that one prisoner finds his number by a random guess is 50% but the chance of all 100 prisoners doing this is minuscule, nearly zero. To be exact, it would be the number 0.5 raised to the 100th power.
There is, however, a strategy that significantly raises the chances of winning. The strategy rests on the concept of cycles in permutations.
When the first prisoner enters the room, he does not just open any 50 boxes but opens the box with his number on it. If he finds his number, then he is done. If he doesn’t, he will open the box with a number corresponding to the number he found in the first box. This process goes on and on, and if he finds his number before opening the 51st box, then he has succeeded; otherwise, he and all of the other prisoners fail.
This strategy employs the fact that every number must eventually go back to itself. In other words, if box 50 is opened, and it has the number 77 in it, there will always be a chain of box openings that will lead the prisoner back to box 50; it's just a matter of how long this chain will be. If this method is followed by every prisoner, the chances of all of the prisoners finding their numbers are very high. As a matter of fact, the probability of all prisoners succeeding with this strategy is approximately 31%.
There is a reason for why this strategy is so successful. When numbers are placed randomly into boxes, they form, as briefly discussed above, chains or cycles. A cycle is a sequence such that if you follow the numbers, you eventually return to your starting point. If the prisoners adopt this strategy, each prisoner is essentially testing the length of the cycle that their number is contained in. If the cycles for all of the prisoners are of length 50 or less, all prisoners will find their numbers. The amazing fact is that for 100 numbers, the probability that the longest cycle is 50 or less is approximately 31%.
It may even sound too simple, almost tricky, to be true. But here it is, and it has everything to do with the nature of random permutations and cycles. This puzzle is a real example of how an apparently impossible problem can have its solution rooted in probability and combinatorics, not brute force or luck. This strategy mathematically exploits the structure of permutations in a way that random guessing does not. It doesn't guarantee success, but it dramatically increases the odds, from nearly impossible to about one in three. It is not only a math puzzle but also a problem of how we think about probability and strategy. This shows that sometimes, to solve a complex problem, the key lies in understanding the underlying patterns and not just in guessing or hoping for the best.