The 100 Prisoner Problem

November 21, 2023

Share this article:

[supsystic-social-sharing id='1']

Written by

Imagine if tomorrow you were abducted, and before you knew it, you were trapped in a room with 99 other people who seemed to know nothing more about what was happening than you. You notice that everyone is wearing an orange jumpsuit, which is uniquely numbered. You also notice a door, and you can not help but wonder what is behind it. At this moment, a voice can be heard telling you the rules of the game you are about to play.

Your circumstance is referred to as the “100 Prisoners Problem.” This issue was first proposed in 2003 by the Danish computer scientist Peter Bro Miltersen. In this problem, 100 prisoners, numbered from 1 to 100, are given the same task. They are required to find their corresponding number in 1 of 100 drawers. But here is the catch: everyone is limited to opening 50 drawers. Additionally, after the first prisoner begins its attempt of finding its number, no form of communication between the prisoners is allowed. 

At first glance, it appears that the chances of winning this game are slim. Every inmate possesses a probability of 50 in a 100 equal to 50% of locating their own identification number. Since we have a hundred prisoners who all need to find their own number, this gives us a chance of ½^100  = 0.00000000000000000000000000008%. However, this is under the assumption that every prisoner opens their drawers randomly, independently of each other. 

Suppose you had 100 attempts instead of 50 and opened your drawers in the following way: You start by opening the drawer of your own number; let us assume it is one. Upon opening your drawer, you will discover the number seven. Now, proceed to open drawer seven and discover number thirteen. After this, you open drawer thirteen. You can continue this approach until you find your own number. To realize this, it is important to note that every number is only hidden once. Hence, in our example, it is impossible to find number seven again after opening drawer thirteen. Hence, starting at number one, we are guaranteed to create a loop of numbers eventually containing one. To be more exact, one will be the final number we find to complete this loop. Since if you would continue opening drawers after finding your number, you would start opening the drawers you opened when you started. 

Now let us return to the original example, where you are limited to opening 50 drawers. Using the same approach, we know that we will find our own number as long as the loop we create does not contain more than 50 numbers (since, again, the final number in the loop is one). Assuming that this is the case, then not only will you find your own number, but all other people with a number contained in your loop will also find their own number. Since their number is also contained in this loop, and this loop is still not bigger than 50. To see this, assume that after you have found your number, number seven enters the room. This prisoner will open drawer seven, again find number thirteen, and start following the same loop as you, eventually arriving at drawer one, where it will find its own number. Notice that it will take number seven the same amount of attempts to find its number as you. 

We have now created an approach where the rate of success of a prisoner is correlated to that of the other prisoners. Instead of the success of the total group being determined by individual independent trials, the success is now dependent on the size of the loops that are created. To be more specific, the group is successful if there exists no loop with more than 50 numbers. Let us look at the chances of that happening. Let us start with the case that every number is used in one big loop; hence, we have a loop of a hundred numbers. For a loop, there are a hundred options for the first number, 99 for the second, 98 for the third, etc. Hence, we can create 100! Different number loops. Now for our hundred number loop, this is also the case; however, note that the loop 1,2,…,100 is the same as 2,3,…,100,1 and also the same as 3,4,…,100,1,2 etc. Hence, to find the probability of a hundred-number loop, we have: (100!/100)/100! = 1/100. Calculating these probabilities gives 1/99 for the 99 number loop, 1/98 for the 98 number loop, etc. Now adding up all probabilities of cases with loops bigger than 50, we get a total chance of roughly 69%. Hence, our rate of success is roughly 31%. Not perfect by a long shot, but much better odds than our previous calculation of a 0.00000000000000000000000000008% chance of success.

After the rules are explained, you recognize The 100 Prisoner Problem and tell all other people the strategy that they should use. Now, let us hope you are lucky.

Read more

Regression analysis: A beginner’s guide

Regression analysis: A beginner’s guide

Econome­­trics, the int­­ersection of economics and statistics, employs sophisticated methods to analyse and quantify relationships within economic systems. One of its fundamental tools is regression analysis, a statistical technique that allows economists tot model...

Are you tying your shoelaces wrong?

Are you tying your shoelaces wrong?

We tie our shoelaces to ensure that our shoes stay on tight, and we do these by tying a knot. There are different ways to tie your shoelaces, you may have learnt the “around the tree” technique, but somehow, they still always come undone, why? This all has to do with...