The 100 Prisoners riddle

Introduction

If you are a trivia fan like I am, and you like to learn about math/physics/science aspects of our daily life, then you’re probably already subscribed to the Veritasium Youtube channel. If not, I highly recommend it.

In the recent video, an interesting riddle has been introduced. It is called “The 100 prisoners riddle” and you can learn all the details from the original video.

Implementation in Python

With a riddle like this, I always want to implement the solution by myself, to see the problem “with my own eyes”. The problem description was rather straightforward, so I could immediately jump to my IDE and start coding with Python.

That is the beauty of Python language. It’s almost like you describe the problem in a pseudo-code and then after a few tweaks, you have a working Python solution.

Let’s start with defining a function that can generate a random distribution of boxes with prisoner numbers. The best structure for that will be a plain old dictionary that will map the box number with the prisoner number as key-value pairs. We can use random.shuffle function from the standard library to shuffle the prisoner numbers before we put them into the boxes.

from typing import Dict
from random import shuffle

def distribute_tags_in_boxes(size: int = 100) -> Dict[int, int]:
    tags = list(range(size))
    shuffle(tags)
    boxes = {i: tag for i, tag in enumerate(tags)}
    return boxes

Now we can implement the solution proposed in the video.

The idea is simple:

Prisoners should start with a box that matches their number. If they find their number in it they are done. Otherwise, they should go to the box with the found number on it.

That would create a loop because eventually one of the boxes would point to the prisoner number. The only problem is if the loop is smaller than the max number of tries.

We can create a function that returns True if the strategy worked for a given prisoner and False otherwise.

def simulate_strategy(
    prisoner_number: int,
    box_distribution: Dict[int, int],
    max_tries: int,
) -> bool:

    # We start from the box with the same number as the prisoner number
    next_box_to_try = prisoner_number

    no_of_tries = 0
    while no_of_tries < max_tries:
        found_number = box_distribution.get(next_box_to_try, None)
        # If we find the prisoner number in the box, then we are done
        if found_number == prisoner_number:
            return True
        # Otherwise, we continue with the number found in the box
        next_box_to_try = found_number
        no_of_tries += 1
    # If we don't find the prisoner number in `max_tries`, then we failed
    return False

Now we have all the building blocks, so we can test this solution.

The easiest way to do it is to perform many experiments and calculate the success rate. It’s not a formal proof, but it still can provide us the intuition about the correctness of the solution.

if __name__ == "__main__":

    # Experiment parameters
    no_of_prisoners = 100
    max_no_of_tries = 50

    # The bigger the number, the more precise the output
    no_of_experiments = 10000

    experiment_results = []
    for experiment_no in range(no_of_experiments):
        random_boxes = distribute_tags_in_boxes(size=no_of_prisoners)
        prison_results = []
        for _id in range(no_of_prisons):
            prisoner_result = simulate_strategy(
                prisoner_number=_id,
                box_distribution=random_boxes,
                max_tries=max_no_of_tries,
            )
            prisoner_results.append(prisoner_result)
        # Experiment succeeds if all prisoners succeed
        experiment_result = all(prisoner_results)
        experiment_results.append(experiment_result)

    success_rate = sum(experiment_results) / len(experiment_results) * 100
    print(f"For {no_of_experiments} success rate is {success_rate:.2f}%.")

Conclusion

As we can see in the console the success rate is at the level of 31% which matches our expectations.

Still, at first look, it is very counterintuitive, that such a simple strategy can so dramatically increase the success chance. By choosing the box at random each prisoner has a 0.5 probability of success, which for 100 prisoners is reduced to 0.5^100 ~= 8e-31.

Using the proposed strategy updates the odds by 30 orders of magnitude. Not bad!