Imagine your life or death depended on solving a math problem. This scenario - a nightmare for lots of students - is the premise for a tricky puzzle known as the 100 Prisoners Problem. If the prisoners in the title can solve the puzzle, they'll all go free. If they fail, they'll all be executed. The stakes are high!
For most puzzles, the point is to find the solution. The 100 Prisoners Problem is a puzzle where the interesting thing isn't the solution itself (at least, as long as you aren't one of the prisoners!), but understanding why the solution works. Even once you've been told the answer, the solution isn't intuitive.
This problem wasn't created to be a puzzle at all. It was originally posed as a tool to figure out a searching problem in the field of computer science. Anna Gal and Peter Bro Miltersen modeled the process of searching for a specific substring inside of a longer string (e.g. searching for "red" inside of "tired") as a game involving guessing the colors of slips of paper. When the problem's creators showed their game to a friend of theirs, he pointed out that there was an elegant solution for a specific case of their scenario. This case became the basis for the 100 Prisoners Problem we know today.
Understanding the solution to this clever problem will lead us to look at simple probability, independent and dependent events, cycles, combinations and permutations, and more. For more information about the history of the problem, please see the history page. To learn about the problem and its solution, please see the explanation of mathematics section.
Back to top