For this problem, there are 100 prisoners and 100 boxes in two separate rooms. Each box contains a slip of paper with a prisoners number in it. Each prisoner and box is numbered from one to 100. The numbers in the boxes are randomly shuffled. Each prisoner is then given 50 attempts to find their own number. If every prisoner finds their own number, they are all set free. If even one prisoner fails to find their own number, all the prisoners perish. Prisoners that have entered the room with boxes and attempted to locate their own number are not allowed to communicate with prisoners who have yet to enter the room with boxes.
The famous prison Chateau D’if is featured above.
Surprisingly, there exists a solution to this problem in which their chance of survival is nearly 1 in 3 (31.8%). This is significantly higher than if each prisoner randomly chose fifty boxes. In that case, each prisoner has a 50% chance of finding their number. For 100 prisoners, this would make the odds a terrible 0.5^100 or 0.0000000000000000000000000000008%. The solution is for each prisoner to start at their own box, then opening the next box indicated in the chain until their own number is found.
The distribution of numbers in boxes randomly form “chains” - essentially closed loops of numbers. The prisoners can take advantage of the fact that the the boxes remain identical. Only when a chain is longer than fifty do the prisoners fail to find their number.
To satiate my own curiosity, I decided to write a sort of basic simulation that runs tests consecutively.
import random
simulation_count = 1000
search_count = 50
prisoner_count = 100
simulation_results = [-1] * simulation_count
simulation_passed = 0
for i in range(simulation_count):
prisoners = range(prisoner_count)
boxes = list(prisoners)
random.shuffle(boxes)
results = [0] * prisoner_count
for prisoner in prisoners:
boxes_visited = 0
current_prisoner = prisoner
while boxes_visited < search_count:
if boxes[current_prisoner] == prisoner:
results[prisoner] = 1
break
else:
current_prisoner = boxes[current_prisoner]
boxes_visited += 1
simulation_results[i] = float(sum(results))/float(prisoner_count)
if simulation_results[i] == 1.0:
simulation_passed += 1
print ("Success level: " +
str(100*(float(simulation_passed)
/
float(simulation_count))) + "%")
The results are as expected. Of the three simulations (each with 1000 tests) I ran, all were surprisingly close to the proven number of 31.8%.
Success level: 33.0%
Success level: 32.0%
Success level: 32.1%
While a one in three chance of survival seems paltry, it sure beats the infinitesimally small odds provided by each prisoner choosing fifty boxes randomly.
This is a reproduction of an older post from 2014 that has been updated for 2025. It was originally inspired by this video from MinutePhysics, but more recently, by another video from Veritasium.