The 100 Prisoners Problem
[Category: Programming and Databases] [Date: 2014-12-17 03:11:11]
Continuing my loose tradition of exploring novel problems in computing and mathematics, I felt the impetus to implement a quick simulation of the novel solution to the 100 prisoners problem. This time, the motivation came from a video from MinutePhysics.
For this problem, there are 100 prisoners and 100 boxes in two separate rooms. Each prisoner and box is numbered from one to 100. The boxes containing the numbers 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.
Surprisingly, there exists a solution to the prisoners' dilemma in which their chance of survival is 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. By following the breadcrumbs or "chain" that the random shuffle created, the prisoners take advantage of the fact that the the boxes remain identical for each prisoner. Only when a chain is longer than fifty do the prisoners fail to find their number.
This is an elegantly simple solution that is surprisingly easy to implement. To satiate my own curiosity, I decided to write a pseudo-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 =  * 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.