Trishock

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 = [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.