There are 100 prisoners in a jail.
Each one has a number from 1 to 100.
In a room, there are 100 boxes numbered from 1 to 100.
Each box contains a number from 1 to 100.
Each prisoner enters the room with the boxes once and can open up to 50 boxes to find his number. Once they stop opening boxes, whether they find their number or not, they leave the room as they found it. If all prisoners find their numbers, they are released. If one fails to find his number, they are all executed.
The first question is: what is the probability of them surviving?
The second question is: is there a strategy they can devise regarding how to open the boxes to increase their chances?
Think a little before looking at the solution.
Solution:
Each prisoner has a 1/2 (50%) chance of finding his number and 1/2 chance of not finding it. Therefore, the probability of all of them finding their numbers is:
P = (1/2)^100
This is approximately 7.888609×10^(-31) or approximately 0.0000000000000000000000000000789, which is very close to zero.
So, if each prisoner opens boxes randomly, it's almost certain they will fail.
There is a strategy, though, that if followed, will increase their survival probability to 31%. That means in 31 out of 100 instances, ALL prisoners will have found their numbers, and in 69 out of 100 instances, at least one will not have found his number. There is, therefore, a significant improvement. But how is this achieved?
There are 100! = 1234...*100 = 9.332622 * 10^157 ways to arrange the numbers inside the boxes. However, the sequence 1 2 3 ... 100 is the same as the sequence 100 1 2 3 ... 99, just with a different starting point. So, there are (100!/100) ways to arrange the numbers. In the end, for a sequence of numbers of length 100, the probability is 1/100; for a sequence of 99 numbers, it's 1/99, and so on. Therefore, the probability of a prisoner not finding his number is if his number is in a sequence of 51 numbers or 52 numbers, etc., which is 1/51+1/52+1/53+...+1/100. This is a percentage of 69%, so the probability of all prisoners finding their numbers is 31%.
To make this happen, each prisoner must start with the box containing his number, and each time, the next box they open should be the number they found inside the previously opened box. If they all follow this strategy, each will still have a 50% chance of finding their number, and collectively, they will have a 31% chance of all finding their numbers and surviving. Whereas if they make random choices, as we said before, the probability of survival is 0.00000000000000000000000000789%.
Think about it...
Comments