Who doesn't love a good puzzle? They challenge us, intrigue us, and sometimes even frustrate us. But most importantly, they provide a unique opportunity to test our problem-solving skills and stretch our minds. Today, we're going to delve into an intriguing logic problem known as the 100 Prisoners Problem.
Eventually we'll come to a surprising result that seems to go against the odds, but first let's set the stage by presenting the problem.
Unraveling the 100 Prisoners Problem
Imagine 100 prisoners, each assigned a unique number from 1 to 100. Their freedom is at stake in a peculiar game, the rules of which are quite simple but the strategy anything but.
In the warden's room, there are 100 drawers and 100 pieces of paper with the numbers from 1 to 100 written on them in a random order. The warden places these pieces of paper in the drawers, one per drawer, and closes the drawers.
The prisoners are allowed to strategize before the game starts; once they are ready, the game begins. Each prisoner, one at a time, is led into the room and allowed to open 50 drawers of their choosing. If they locate their own number, they quietly exit the warden's room into a holding cell, and the drawers are returned to their undisturbed state before the next prisoner enters.
If all prisoners find their number, they are all set free. If even one fails, they all are returned to their cells.
Now that you've been introduced to the problem, have a moment to ponder. What strategy would you employ if you were one of these prisoners?
Simulation
A visual representation can help solidify one's understanding of a problem, so I created the following simulation. Try it out and see if you can figure out the optimal strategy, and then continue reading to see if you were right.
Make sure to increase the simulation tick to slow down the simulation to see what the optimal strategy is doing. The 'Group by cycle' and 'Color by cycle' checkboxes will also help you visualize what the strategy is.
Give it a try here:
The Strategies
Now, let's dive deeper into the strategies our prisoners can use.
The Random Strategy
Perhaps the most intuitive approach for the prisoners would be to adopt a random strategy. Each prisoner could simply open 50 drawers at random, hoping to find their number among them. At first glance, this approach seems reasonable. After all, with 50 attempts, each prisoner has a 50% chance of finding their number, right?
Unfortunately, the reality is not quite so rosy. While the probability that a single prisoner finds their number using the random strategy is indeed 50%, the situation changes dramatically when we consider all the prisoners together.
Remember, the prisoners will only be freed if all of them find their numbers. So what we're really interested in is not the probability of one prisoner finding their number, but the probability of all 100 prisoners doing so. To calculate this, we need to multiply the individual probabilities together.
Mathematically, this looks like:
(1/2) * (1/2) * ... * (1/2) = (1/2)^100
When you calculate this out, the result is approximately 0.0000000000000000000000000000008, a number so close to zero that it's practically negligible. In layman's terms, the odds of all the prisoners finding their numbers using the random strategy are, for all intents and purposes, zero.
This situation is akin to asking the prisoners to flip 100 coins and freeing them only if all the coins land on heads. While it's certainly possible for a single coin to land on heads, the likelihood of all 100 coins doing so is astronomically small. It's a vivid demonstration of the fact that probabilities can be deceptive when compounded on a large scale.
Thus, while the random strategy may seem appealing due to its simplicity, it's a gamble that the prisoners are unlikely to win. So what strategy should they use instead?
The Optimal Strategy
In the face of such bleak odds, you may think that the prisoners are doomed to failure. However, a remarkable strategy exists that provides the prisoners with a survival probability of over 30%. This strategy hinges on the crucial observation that the prisoners don't have to decide beforehand which drawers to open. Instead, they can use the information they gain from the contents of each opened drawer to inform their next choice. This dynamism is the key to the optimal strategy.
Here's how it works:
- Each prisoner begins by opening the drawer labeled with their ownf number.
- If the drawer contains their own number, they've succeeded and can exit the warden's room.
- If the drawer contains the number of another prisoner, they then open the drawer labeled with this newly found number.
- The prisoner repeats steps 2 and 3 until they either find their own number or fail because their number is not found in the first fifty opened drawers.
This strategy might seem like it's overly dependent on chance, but there's a method to the madness. The crucial point is that by starting with their own number, each prisoner guarantees they are on the unique permutation cycle of drawers containing their number. The question then becomes whether this cycle is longer than fifty drawers.
The concept of a "permutation cycle" might sound complex, but it's a straightforward concept. In our context, a permutation cycle refers to the sequence of numbers that a prisoner encounters when they follow the strategy outlined above. For instance, if prisoner 1 opens a drawer containing the number 20, then opens the drawer labeled 20 to find the number 35, and so on, the permutation cycle is the sequence of numbers (1, 20, 35, ...). The length of this cycle is the number of steps it takes for the sequence to return to the starting number—in this case, 1. Since the prisoner starts with the drawer labelled with their own number, the length of the cycle is the number of drawers they must open before they find their own number. If there is a cycle of length greater than fifty, the prisoners will fail; otherwise, they will succeed.
The beauty of this strategy lies in its blend of determinism and adaptability. Each prisoner starts with a deterministic choice, the drawer labeled with their own number, but then adapts their subsequent choices based on the numbers they encounter. It transforms the probability of success into a simple question, "What is the probability that there is a permutation cycle of length greater than fifty?" Turns out, this probability is about 70%, meaning the prisoners have a about a 30% chance of success.
if you know the prisoners are following this strategy, given any drawer configuration, you could determine whether the prisoners will succeed or fail before the game even begins.
A JavaScript Detour: Promise.resolve() vs setTimeout(() => {}, 0)
When developing an interactive simulation like this, it's crucial to ensure the simulation doesn't block the browser's main thread. If we're not careful, an intensive computation could freeze up the browser and render it unresponsive. To prevent this, we can use JavaScript's built-in asynchronous mechanisms to break up the simulation into manageable chunks.
Originally, I used setTimeout(runSimulationTick, simulationTickMs) to achieve this. setTimeout not only allows us to divide the computation into smaller pieces, but it also gives us control over the simulation speed by adjusting the simulationTickMs value. This means we can slow down or speed up the simulation as desired.
Now, you might think that setting simulationTickMs to 0 would make the simulation run as fast as possible. While it certainly speeds things up, there's an even faster method: Promise.resolve(1).then(runSimulationTick). However, there's a catch: this approach doesn't allow for speed control and, if overused, can block the main thread, leading to a browser crash.
To strike the right balance, I fine-tuned the simulation loop:
- If
simulationTickMsis greater than 0, we usesetTimeout(runSimulationTick, simulationTickMs). - If
simulationTickMsis 0, we primarily usePromise.resolve(1).then(runSimulationTick), but interspersesetTimeout(runSimulationTick, 0)every 1 in X ticks. X is a number I fine-tuned for maximum speed that wouldn't crash the browser.
But what makes these two methods so different?
The distinction lies in the JavaScript event loop. setTimeout schedules a macrotask, while Promise.resolve schedules a microtask. The key difference is that the event loop executes macrotasks after all microtasks have completed. Furthermore, the browser prioritizes microtasks over rendering the page. This means that excessive use of Promise.resolve in a recursive function can monopolize the browser's resources, preventing it from rendering the page and potentially leading to a crash.
However, by alternating Promise.resolve with setTimeout, we ensure the browser has regular opportunities to render the page, preventing crashes and maintaining a responsive user interface.
Conclusion
In our journey through the 100 Prisoners Problem, we've grappled with probability, tested our strategic thinking, and even delved into some simulation implementation details. The optimal strategy, with its inherent cycle-based approach, offers an interesting exploration into the heart of problem-solving. It's a testament to the power of logic, even in seemingly impossible situations. Conversely, the random strategy serves as a reminder that sometimes, chance can play a surprising role in determining outcomes.
Remember, the power of logic, strategy, and even a bit of luck can together open the door to solutions in the most challenging scenarios.
Want to dive deeper? Feel free to explore the source code of the simulation. The simulation itself is hosted on GitHub Pages here.