In this classic dilemma, the director of a prison offers 100 people slated to be locked up one last chance at freedom. The individuals have been assigned different numbers from 1 to 100, and the director sets up a room containing 100 boxes. Each number from 1 to 100 has been put on a slip of paper and randomly placed in one of the closed boxes, one per box.
The people in jeopardy will enter the room, one after another. Each one of them may open and look into 50 of the boxes in any order. The boxes are closed again afterwards. If, during this search, every person finds their associated number in one of the boxes, all of them are pardoned and given $5,000 each. If just one does not find the right number, they are all admonished and never given another chance with this dilemma.
Before the first person enters the room, they may discuss strategy — but may not communicate once anyone has entered to look in the boxes. There’s no way for them to always win, but what is their best strategy? (I.e., the strategy that maximizes the chance that they will be set free?)
This problem originally appeared in the Prisoner’s Dilemma in the 2021 Fall issue of the PMP Newsletter. Solutions are no longer being accepted for this Dilemma.
Show solution?
Solution.
Admittedly, it looks bleak for the people in this situation. If each person involved simply checks half of the boxes at random, there’s only a chance of finding the right number, and so only a 1 in 2100 chance of everyone finding their number. That’s a truly minuscule chance, because 2100 is a 30-digit number. Reader William Jones responded to this Dilemma, and emphasized how unlikely this random method is to work by correctly pointing out that “Winning the lottery is better.”
William continued with a very clever idea for the individuals involved in this situation: Each person entering the room with the boxes presumably knows the number assigned to the next one to enter. So the first one checks boxes 1-50 to look for their own number, but if they happen to see the next person’s number, they swap it for whatever is in box 50. The second person first checks box 50, and whether or not that’s right, they continue checking boxes 51 through 99 (which would be their box). If the second person finds the third person’s number, they swap it with whatever is in box 50. Then the third person checks box 50, and then box 100, and then boxes 1 through 48, swapping if they find the fourth person’s number. This process continues, with each person checking box 50 first, and then checking the next 49 boxes in a cycle.
In this scheme, there is a 50% chance of the first person finding the right number, but a 99% chance the second person finds the right number, and then a slightly better than 98% chance for each person thereafter (since each participant after the first looks in 49 new boxes for themselves or their successor, plus then there’s a small chance that their number happened to be in box 50 without anyone putting it there). That translates into at least a (0.5)(0.99)(0.98)98 % chance of all of the participants finding the right number and earning freedom, far better than the random method! And as the problem did not say anything about the participants not moving numbers, it would have to be taken as a valid method to use truly a creative idea.
Figure 1: Possible contents of the first five boxes.
But wait! As it happens, though, it’s possible for the people stuck in this situation to do even better than this strategy without moving any of the numbers. Here’s the idea. Each person who enters the room starts by opening the th box, where is their own number. If they don’t find their number, they look at whatever number was found in that box, say , and next open the th box. They continue in this fashion, opening the box corresponding to the number they just found in the last box, until either they find their own number or they hit their 50-box limit. See figure 1 for a diagram showing one possible sequence of box openings of the first participant.
Why does this help? Imagine 100 people in a room, where each one points to one other person in a way that no two people are pointing to the same person. It has to be possible to arrange the people in a collection of “loops” where each person points to the next: just start with any person, go to the person they point to, and then the person they point to, and so on. Since there are only 100 people and everyone is pointing to someone, eventually you have to come back to the person you started with. That’s your first loop. If it doesn’t contain everyone, start again with a person that was left out, and create another loop. (It can’t intersect with the first loop because no two people point to the same person.) Continuing this process with all of the people eventually splits everyone up into loops.
The numbers in the boxes are just like the people, if you interpret the number in the box as the position of another box. So every box is in a loop, and that loop must contain a box where the number inside is the position of the box you started with, that is, the number assigned to the person that started opening boxes.
That brings us to the kicker: if all of the loops have length 50 or less, then all of the prisoners find their own numbers! (For example, in figure 1 the first person is very lucky and happened to be in just a five-member loop.) So the question becomes how likely is it that all of the loops are short enough? In other words, if you had 100 people and they all pointed at random, and then you divided them into loops, what are the chances that all of the loops would end up size 50 or less?
It turns out those chances are pretty good: using the combinatorics of permutations (as these arrangements of things all pointing to different members of their same group are called), it is possible to calculate that there is more than a probability, or over a 30% chance, that the group will earn its freedom with this strategy. That’s truly a long way from our initial bleak estimate of one chance in 2100. ■
