The Prisoner's Dilemma

D2. Find Yourselves

In this classic dilemma, the director of a prison offers $100$ prisoners, who have been assigned numbers from $1$ to $100,$ a last chance at freedom. A room contains $100$ boxes. The director randomly puts one prisoner’s number in each closed box. The prisoners enter the room, one after another. Each prisoner may open and look into $50$ boxes in any order. The boxes are closed again afterwards. If, during this search, every prisoner finds his number in one of the boxes, all prisoners are pardoned and given $5,000 each. If just one prisoner does not find his number, all prisoners are admonished and never get another chance with this dilemma.

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 boxes. There’s no way for them to always win, but what is their best strategy?

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 50/50 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 50th 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 > 6.8% 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.

But wait!

Figure 1: Possible contents of the first five boxes.

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 $n$th box, where $n$ is their own number. If they don’t find their number, they look at whatever number was found in that box, say $m,$ and next open the $m$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 $1-\ln 2 \approx 0.307$ 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. ■

Main Maker