From: veritasium
The 100 Prisoners Riddle is a logic puzzle considered so counterintuitive that it “still seems wrong even if you know the answer” [00:00:03]. It is a problem that tests one’s mathematical reasoning and understanding of probability theory [00:03:32]. The solution involves an “incredible feature of math” [00:03:34].
The Riddle Setup
One hundred prisoners, numbered 1 to 100, face a challenge [00:00:35].
- Slips of paper, each containing one of their numbers, are randomly placed in 100 sealed boxes within a room [00:00:39].
- Each prisoner, one at a time, enters the room and can open any 50 of the 100 boxes, searching for their number [00:00:46].
- After searching, they must leave the room exactly as they found it, and they cannot communicate with other prisoners [00:00:54].
- Success Condition: If all 100 prisoners find their own number during their turn, they are all freed [00:01:01].
- Failure Condition: If even one prisoner fails to find their number, they are all executed [00:01:08].
- Pre-Strategy: The prisoners are allowed to strategize before any of them enters the room [00:01:13].
Initial Probability: Random Guessing
If each prisoner searches for their number randomly, each has a 50% chance of finding it [00:01:22]. The probability that all 100 prisoners succeed is (1/2) multiplied by itself 100 times, or (1/2)^100 [00:01:27]. This results in an incredibly small probability: 0.000… (30 zeros) …8 [00:01:38]. This chance is less than two people picking the same grain of sand from all Earth’s beaches and deserts [00:01:46].
The Counterintuitive Strategy
Despite the seemingly impossible odds, a specific strategy can raise their chances of success to nearly one in three [00:01:59]. This improves their odds by almost 30 orders of magnitude [00:02:06]. This riddle was devised by computer scientist Peter Bro Miltersen, who himself didn’t think of the strategy until a colleague pointed it out [00:02:49].
The Loop Strategy
The optimal strategy for the prisoners is as follows:
- When a prisoner enters the room, they open the box labeled with their own number [00:03:08].
- If the slip inside is not their number, they go to the box labeled with the number they just found [00:03:19].
- They continue this process – opening the box matching the number on the slip they just found – until they find their own number [00:03:27].
- If they find their number, they stop and leave the room [00:03:39].
This strategy leads to “over a 30% chance that all the prisoners will find their number” [00:03:45].
How the Loop Strategy Works
The key insight is that any random arrangement of slips in boxes forms one or more “loops” [00:04:03].
- A “loop of one” occurs if a box contains its own number (e.g., box 1 contains slip 1) [00:04:08].
- Longer loops occur when boxes point to other boxes in a sequence that eventually returns to the starting box (e.g., box 1 points to 7, box 7 points to 1) [00:04:20].
- Any random arrangement of slips will result in a mixture of shorter and longer loops [00:04:40].
When a prisoner starts by opening the box labeled with their own number, they are guaranteed to be on the loop that includes their slip [00:04:50]. This is because every box contains a slip that points to another box, creating a chain that must eventually close into a loop [00:11:37].
The success of a prisoner depends on the length of the loop their number is part of [00:04:56].
- If a prisoner’s number is part of a loop shorter than 50 (the maximum number of boxes they can open), they will find their slip [00:05:01].
- If a prisoner’s number is part of a loop that is 51 or longer, they will not find their number within the allowed 50 box openings [00:05:07].
Crucially, if a loop is longer than 50, all prisoners whose numbers are part of that long loop will fail [00:05:35].
Calculating the Probability of Success
The probability that all prisoners succeed is the probability that a random arrangement of 100 numbers contains no loops longer than 50 [00:05:57].
- Total Permutations: There are 100! (100 factorial) different ways to arrange the 100 slips in the 100 boxes [00:07:16].
- Unique Loops of Length N: The total number of unique loops of length N (e.g., 100) is N! / N, because each loop can be written N different ways while remaining the same loop [00:08:08].
- Probability of a Specific Loop Length: The probability that a random arrangement contains a loop of a specific length ‘L’ (e.g., 100) is (L! / L) / 100! = 1/L [00:08:16].
- Probability of a loop of length 100 is 1/100 [00:08:43].
- Probability of a loop of length 99 is 1/99 [00:08:51].
- And so on.
- Probability of Failure: The prisoners fail if there is any loop longer than 50. This is the sum of the probabilities of loops of length 51, 52, …, up to 100 [00:09:02]: 1/51 + 1/52 + … + 1/100 This sum approximately equals 0.69 [00:09:12].
- Probability of Success: The probability of success is 1 minus the probability of failure: 1 - 0.69 = 0.31 or 31% [00:09:15].
Key Insights
- Individual vs. Collective Probability: While each prisoner still individually has a 50% chance of finding their number (since they can only open half the boxes), these probabilities are no longer independent [00:09:46].
- Linked Outcomes: The loop strategy links everyone’s outcomes [00:15:56]. The prisoners either “all win together or the majority loses together” [00:10:26]. Once the boxes are arranged, each prisoner’s chance of finding their number is either 100% or 0% [00:16:11].
“I still find it difficult to believe.” [00:09:27] “This feels a bit like magic.” [00:09:29]
Variations and Extensions
Sympathetic Prison Guard
If a sympathetic guard were to sneak into the room before the prisoners, they could guarantee success by swapping the contents of just two boxes [00:12:27]. This is because there can be at most one loop longer than 50, and swapping two box contents breaks that long loop into two shorter loops, both less than 50 [00:12:40].
Malicious Prison Guard
If a malicious guard knows the prisoners will use the loop strategy and arranges the numbers to ensure a loop longer than 50, the prisoners are still not doomed [00:12:56]. They can counter by arbitrarily renumbering the boxes (e.g., adding five to each box number) [00:13:13]. Renumbering boxes is equivalent to redistributing the slips, effectively restoring the problem to a random arrangement of loops, bringing their chance of survival back to 31% [00:13:28].
Scaling to More Prisoners
The probability of success changes very little even with a much larger number of prisoners:
- For 1,000 prisoners (each checking 500 boxes), the chance of success is 30.74% [00:14:01].
- For 1 million prisoners, it’s 30.685% [00:14:18].
The probability of winning this game approaches a limit as the number of prisoners increases [00:14:31]. The formula for the probability of failure (the sum of 1/N for N from 51 to 100) approximates the integral of 1/X from n to 2n [00:14:50]. This integral evaluates to the natural logarithm of two (ln(2)) [00:15:14].
Therefore, the probability of success approaches 1 - ln(2), which is approximately 30.7% [00:15:25]. This means that no matter how many prisoners there are, using this strategy, they will always have at least a 30% chance of escaping [00:15:34].
The problem, described as a complex problem solving exercise, offers a “delightful math puzzle” [00:17:08]. Resources like Brilliant offer courses on perplexing probability and the joy of problem solving for those interested in similar counterintuitive riddles [00:16:56].