There is a riddle that
is so counterintuitive, it still seems wrong even
if you know the answer. - You'd think it's an
almost impossible number. - I feel like you probably
hit me with some truth bomb. - I mean, if you're trying
to create controversy and you're trying to confuse people, you're gonna succeed. (both laughs) - There are a bunch of
YouTube videos about it, but I find all of them either
incorrect or incomplete. So in this video, I'm going to dive deeper and explain it fully. Here is the setup. (suspenseful music) Say there are 100 prisoners
numbered 1 to 100. Slips of paper containing
each of their numbers are randomly placed in 100
boxes in a sealed room. One at a time, each prisoner
is allowed to enter the room and open any 50 of the 100 boxes, searching for their number. And afterwards, they must leave the room exactly as they found it, and they can't communicate in any way with the other prisoners. If all 100 prisoners find their own number during their turn in the room, they will all be freed. But if even one of them
fails to find their number, they will all be executed. The prisoners are allowed to strategize before any of them goes into the room. So what is their best strategy? If they each search for
their own number randomly, then each prisoner has a
50% chance of finding it. So the probability that all 100
prisoners find their numbers is 1/2 times 1/2 times 1/2 a hundred times or 1/2 to the power of 100. This is equal to 0.00000000 30 zeros, and then an eight. To put this probability into perspective, two people have a better
chance of picking out the same grain of sand from all the beaches and deserts on earth than by escaping this way. But what have I told you
that with the right strategy, there's a way to raise their
chances to nearly one in three. It improves their odds of a random chance by nearly 30 orders of magnitude. That's like taking a
millimeter and scaling it up to the diameter of the
observable universe. - But they can only coordinate
this strategy beforehand. - Correct? - Is this true? - Yes. - Teach me. - This is not a trick question. The solution just involves an
incredible feature of math. So what is this mathematical strategy? Well, if you don't
already know the answer, feel free to pause the video
here and try it for yourself. And if you don't come
up with it, don't worry, you're in good company. Even the person who came
up with this riddle, computer scientist Peter Bro Miltersen, he didn't even think of this strategy until a colleague pointed it out. Miltersen, ultimately published
this problem in a paper where he generously left the solution as an exercise for the reader. So here is the solution. Pretend you are one of the prisoners, when you go into the room, open the box with your number on it, the number on the slip inside
probably won't be yours, but that's okay. Go to the box with that number on it. look at the number inside, then go to the box with that
number on it, and so on. Keep doing this until you find
the slip with your number. If you find your number, that essentially tells you to go back to the box where you started. It closes the loop of numbers
you've been following. But if you've found your
number, then you're done. You can stop and leave the room. This simple strategy
gives over a 30% chance that all the prisoners
will find their number. - The entire pool has a 30... - Everyone can find their
number 31% of the time. - What? - But how does it work? The first thing to
notice is that all boxes become part of a closed loop. The simplest loop would be a box that contains its own number. If you're prisoner number
one and you go to box one, it contains slip one, then you're done. Your number was part of a loop of one, but you could also have a loop of two. Say box one points to box seven and box seven points back to box one. Or you could have a loop
of three, or four, or five, or any length all the way up to 100. The longest loop you
could have would connect all the numbers in a single loop. But more generally, any random arrangement of the slips in these boxes will result in a mixture of some shorter and some longer loops. When you start with a box
labeled with your number, you are guaranteed to be on the loop that includes your slip. So the thing that
determines whether or not you find your slip is
the length of the loop. If your number is part of a
loop that is shorter than 50, then you will definitely find your slip. But if your number is part of
a loop that is 51 or longer, you are in trouble. You won't find it before you've exhausted the 50 boxes you're allowed to search. When you open the box
labeled with your number, you are in fact starting at the farthest point on
the loop from your slip. You wanna know where is the
slip that points to this box, but to find it, you have to
follow the loop of numbers all the way around to the end. That means if the prisoners
follow this strategy and the longest loop is 51, not just one or two prisoners will fail to find their number, but all 51 on this loop won't make it. They make it to the box just
before the box with their slip, but they have to stop searching there. (both laughs) So the probability that all
of the prisoners succeed is just the probability
that a random arrangement of a hundred numbers contains
no loops longer than 50. Now I promised that this
probability would come out to around one in three, but how do we calculate it? Well, imagine writing down
all the different ways that you could connect
100 boxes to form a loop of length 100. So you could have box
one points to box two, box two points to box three
to box four, and so on, all the way to 100, and then box 100 would
point back to box one, or you could have something random. Box five points to box
99 to box 17 and so on, and let's pick the last one, is 63. And box 63 points back to box five. So how many different arrangements
of these a hundred boxes or permutations could you have? Well, for the first box, I have 100 different boxes
that I could choose from. The second box, because
I've already used one, I can only pick from 99 boxes, and the next one, I can pick
from 98 boxes, and so on, down to the very last box. I don't really have a choice. There's only one box left I
could put in the last position. So the total number of
different permutations would be 100 times 99, times 98, times 97, all the way down to one. That is just 100 factorial. There are 100 factorial different ways that you could create a
loop of a hundred boxes. But what we can't forget is that these are not
just lines of numbers. They are loops. So some of these lines that look different are actually the same loop. For example, two, three,
four, five, and so on up to 100 and then 1 is the same thing as 1, 2, 3, 4, 5 to 100. You can rearrange the way
you write these numbers a hundred different ways, but they all represent the same loop. So the total number of
unique loops of length 100 is 100 factorial divided by 100. So what is the probability that any random arrangement of 100 boxes will contain a loop of length 100? Well, it's just equal to the
number of unique such loops that we just calculated, 100 factorial over 100, divided by the total number of ways that you could put a
hundred slips in 100 boxes, which is 100 factorial. So the answer is 1 over 100. So there is a 1% chance that
a random arrangement of slips results in a loop of length 100, and this is a general result. The probability that you
get a loop of length 99 is 1 over 99. The probability that you
get a loop of length 98 is 1 over 98. So the probability that there
is a loop longer than 50 is 1 over 51 plus 1 over 52 plus one over 53, et cetera. Add all these up, and it equals .69. There is a 69% chance of
failure for the prisoners, meaning a 31% chance of success where the longest loop is 50 or shorter. - I still find it difficult to believe. - [Derek] This feels a bit like magic. Using the loop strategy, all the prisoners are more
likely to find their numbers than even just two prisoners
choosing at random. So using the loop strategy, what is the probability
that each prisoner alone finds their number? It is still 50%. Each prisoner can still
only open half the boxes, so their individual chance is still 1/2, but these probabilities are no longer independent of each other. Imagine running this experiment
a thousand times over. If everyone is guessing randomly, you'd expect that on most
runs around 50 prisoners would find their number. On lucky runs, the number
would be a bit higher, on unlucky runs, a bit lower. But using the loop strategy, all of the prisoners
would find their numbers 31% of the time. And 69% of the time, fewer
than 50 find their number. The prisoners all win together or the majority loses together. That's how this strategy works. - Why are you assuming that
your number will always be on the loop that you're on? - I feel like-
- I don't understand that. - This is a key question, right? - 'Cause I feel like
it's possible to start and go on a complete loop and not come back to your own number because you got on the wrong loop and then you'd have to
get on another loop, so I don't know that I'd buy this. - Right, right, right,
right, right, right. Now, the big question everyone asks is how do you know that if you start with a box with your number on it you are guaranteed to be on the loop that contains your slip? Well, if you think about it, the slip that says 73,
if anyone sees that, they will definitely go to
the box with the number 73. So the slip and box with the same number essentially form a unit. They're like a little Lego brick. And then every slip is
hidden inside another box. So as I start laying out
slips and boxes randomly, you can see that there's no way that we can end up with a dead end. It's not like you can just
get to a box and then stop because every box contains a slip and that points at another box. So the only way for you to see only boxes when you walk into the room is for every slip to be
contained within a box, and that necessarily will mean that we are forming loops. So when I start with box 73, I must eventually find slip 73, because then and only then will I be directed to go back to box 73 which closes the loop. - Who is the warden to this prison? And what kind of sadistic
mathematical warden are you dealing with here? This is awful. - Now, what if there is a
sympathetic prison guard who sneaks into the room before
any of the prisoners go in? Well, then they can guarantee
success for the prisoners by swapping the contents
of just two boxes. That's because there
can be at most one loop that is longer than 50, and you can break it in half just by swapping the
contents of two boxes. And now I have two separate loops that are each shorter than 50. But what if there was a malicious guard who figured out that the prisoners were going to use this loop strategy? Well, then they could
put the numbers in boxes to ensure they formed
a loop longer than 50. In this case, are the prisoners doomed? Surprisingly, no. They can counter by arbitrarily
renumbering the boxes. They could, for example,
add five to each box number. The loops are set both by
the locations of the slips and by the box numbers. Renumbering the boxes
is essentially the same as redistributing the slips. So the problem is back to a
random arrangement of loops, meaning the prisoners are back to their 31% chance of survival. Now, what happens if you
increase the number of prisoners? - Fun fact, nobody knows if as you have more and more prisoners it's going towards a limit, or if it'll eventually
go down to zero, or what? - That is my friend Matt Parker, and I think what he meant to say is we know exactly what happens as you increase the number of prisoners. With a thousand prisoners each
allowed to check 500 boxes, you might expect their chance of success to drop dramatically, but you can calculate
it like we did before, and it comes out to 30.74%, only half a percentage point
lower than for 100 prisoners. For 1 million prisoners, the probability of success is 30.685%, which is only a little
higher than for 1 billion. Of course, their bigger problem would be the time it takes to open all the boxes. So your probability of winning this game does indeed approach a limit. So what is that limit? The formula we've been using is one minus the chance of failure, which is the series 1
over 51 plus 1 over 52, and so on, up to 1 over 100. We can depict this series as
the sum of areas of rectangles, and there is a curve that follows the heights of these blocks. That curve is one over X. The area under that curve from 50 to 100 approximates the area
of all the rectangles. And as the number of
prisoners goes to infinity, it becomes a better and
better approximation. So to find the probability of failure, we can just take the
integral of one over X from n to 2n. And we find that it's equal to
the natural logarithm of two. This gives a probability of success of one minus the natural log of two, which is about 30.7%. The bottom line is that no matter how many
prisoners you have, you'll always end up
with above a 30% chance of escaping using this strategy. And that feels really wrong. I mean, at first it seemed
essentially impossible for all 100 prisoners
to find their numbers. But now we're seeing that you could have a hundred, a million, or any arbitrarily large
number of prisoners with at least a 30% chance that
they all find their numbers. The beauty of the loop strategy is linking everyone's outcomes together, instead of each prisoner walking in with their own 50-50 shot. Following the same loops
means that they have the exact same chance
of finding their number as everyone else in their loop. And once the boxes and slips are arranged, that chance is set at either 100% or 0%. With this strategy, you can't
ever get close to winning with only a few people
missing their numbers. You can only fail hard
or succeed completely. Now, if you like solving puzzles even outside of life-threatening
prison situations, well, you'll love Brilliant,
these sponsor of this video. Brilliant is a website and app that builds problem-solving skills and guides you through
engaging interactive lessons in math and science. They have great courses on tons of topics, from statistics to astrophysics to logic. Now, if you liked this riddle and you want more just like it, I'd recommend their
perplexing probability course, featuring other seemingly impossible odds and even another mathematically
inclined prison warden. They've also got a joy
of problem solving course to take you through some of their most delightful math puzzles. Every lesson builds on
what you learned previously to give you an in-depth understanding with any course you take. Your knowledge is constantly developed and tested through interactive
experiments and quizzes. And if you get stuck, there's
always a helpful hint. Head over to brilliant.org/veritasium to check out all these courses and test your instincts
after learning about the 100 prisoners riddle. If you click through right
now, Brilliant are offering 20% off an annual premium subscription to the first 200 people to sign up. So I wanna thank brilliant
for supporting Veritasium, and I want to thank you for watching.
Does anyone have a proof of optimality? Or even a proof that you can't get exactly 50% for n>2? (Clearly you can't do better than 50%)
The title of paper in which this problem was introduced was obviously called, "The Cell Probe Complexity of Succinct Data Structures", obviously.
Also was it Sven Skyum that found the solution? I feel like Derek should have at least mentioned his name if he was the first person to find the solution.
Related to the video, I wanted to add another way of thinking about why you can't have a box that leads to a loop the box itself isn't in. Let's say we have Box 9 that has Slip 20. Box 20 has Slip 31. Now, why can't Box 31 go to Box 20 and leave out Box 9 from the loop? Because then there would have to be *two "*Slip 20"s. This isn't possible, since the rules at the beginning state that there's only one slip for each number. Proof by contradiction.
Edit: If there are other good explanations for questions about the video, feel free to post them here :)
Very interesting video!
At 9:25 he shows a distribution graph of the probability. How would one actually calculate the green portion of the graph?
I want to know the probability of there being a loop with L < 51. The 1/L only works for L>50 where there can be no multiple loops of max length.
For instance, the probability of a loop 42 in length is not 1/42, so how would I calculate it?
Someone needs to build a prison to be run by mathematicians - and they better get a large hat budget!
Wow this is really cool
Reminds of The Game You Quit and The Demonetization Game by Vsauce2
I felt lost during the video, I could not really follow the logic that he was trying to show.
Disappointed at his handwaiving for the P(n) for n less than 100. The rigorous math requires additional care that is absent from the n=100 case.