馃攳
The Riddle That Seems Impossible Even If You Know The Answer - YouTube
Channel: Veritasium
[0]
There is a riddle that
is so counterintuitive,
[3]
it still seems wrong even
if you know the answer.
[6]
- You'd think it's an
almost impossible number.
[8]
- I feel like you probably
hit me with some truth bomb.
[11]
- I mean, if you're trying
to create controversy
[13]
and you're trying to confuse people,
[14]
you're gonna succeed.
[15]
(both laughs)
[17]
- There are a bunch of
YouTube videos about it,
[19]
but I find all of them either
incorrect or incomplete.
[23]
So in this video, I'm going to dive deeper
[25]
and explain it fully.
[27]
Here is the setup.
[33]
(suspenseful music)
[35]
Say there are 100 prisoners
numbered 1 to 100.
[39]
Slips of paper containing
each of their numbers
[41]
are randomly placed in 100
boxes in a sealed room.
[46]
One at a time, each prisoner
is allowed to enter the room
[49]
and open any 50 of the 100 boxes,
[52]
searching for their number.
[54]
And afterwards, they must leave the room
[56]
exactly as they found it,
[57]
and they can't communicate in any way
[59]
with the other prisoners.
[61]
If all 100 prisoners find their own number
[64]
during their turn in the room,
[66]
they will all be freed.
[68]
But if even one of them
fails to find their number,
[71]
they will all be executed.
[73]
The prisoners are allowed to strategize
[76]
before any of them goes into the room.
[79]
So what is their best strategy?
[82]
If they each search for
their own number randomly,
[84]
then each prisoner has a
50% chance of finding it.
[87]
So the probability that all 100
prisoners find their numbers
[91]
is 1/2 times 1/2 times 1/2 a hundred times
[95]
or 1/2 to the power of 100.
[98]
This is equal to 0.00000000 30 zeros,
[104]
and then an eight.
[106]
To put this probability into perspective,
[108]
two people have a better
chance of picking out
[111]
the same grain of sand from all
[114]
the beaches and deserts on earth
[116]
than by escaping this way.
[119]
But what have I told you
that with the right strategy,
[122]
there's a way to raise their
chances to nearly one in three.
[126]
It improves their odds of a random chance
[128]
by nearly 30 orders of magnitude.
[132]
That's like taking a
millimeter and scaling it up
[134]
to the diameter of the
observable universe.
[139]
- But they can only coordinate
this strategy beforehand.
[143]
- Correct?
[143]
- Is this true?
[145]
- Yes.
[147]
- Teach me.
[149]
- This is not a trick question.
[152]
The solution just involves an
incredible feature of math.
[155]
So what is this mathematical strategy?
[158]
Well, if you don't
already know the answer,
[160]
feel free to pause the video
here and try it for yourself.
[166]
And if you don't come
up with it, don't worry,
[168]
you're in good company.
[169]
Even the person who came
up with this riddle,
[171]
computer scientist Peter Bro Miltersen,
[173]
he didn't even think of this strategy
[174]
until a colleague pointed it out.
[177]
Miltersen, ultimately published
this problem in a paper
[180]
where he generously left the solution
[182]
as an exercise for the reader.
[185]
So here is the solution.
[188]
Pretend you are one of the prisoners,
[191]
when you go into the room,
[193]
open the box with your number on it,
[196]
the number on the slip inside
probably won't be yours,
[199]
but that's okay.
[200]
Go to the box with that number on it.
[203]
look at the number inside,
[204]
then go to the box with that
number on it, and so on.
[207]
Keep doing this until you find
the slip with your number.
[211]
If you find your number,
[212]
that essentially tells you
[214]
to go back to the box where you started.
[216]
It closes the loop of numbers
you've been following.
[219]
But if you've found your
number, then you're done.
[222]
You can stop and leave the room.
[225]
This simple strategy
gives over a 30% chance
[228]
that all the prisoners
will find their number.
[231]
- The entire pool has a 30...
[233]
- Everyone can find their
number 31% of the time.
[238]
- What?
[240]
- But how does it work?
[243]
The first thing to
notice is that all boxes
[245]
become part of a closed loop.
[248]
The simplest loop would be
[250]
a box that contains its own number.
[252]
If you're prisoner number
one and you go to box one,
[254]
it contains slip one, then you're done.
[257]
Your number was part of a loop of one,
[260]
but you could also have a loop of two.
[262]
Say box one points to box seven
[264]
and box seven points back to box one.
[267]
Or you could have a loop
of three, or four, or five,
[272]
or any length all the way up to 100.
[276]
The longest loop you
could have would connect
[277]
all the numbers in a single loop.
[280]
But more generally, any random arrangement
[283]
of the slips in these boxes
[284]
will result in a mixture of some shorter
[287]
and some longer loops.
[290]
When you start with a box
labeled with your number,
[292]
you are guaranteed to be on the loop
[294]
that includes your slip.
[296]
So the thing that
determines whether or not
[298]
you find your slip is
the length of the loop.
[301]
If your number is part of a
loop that is shorter than 50,
[304]
then you will definitely find your slip.
[307]
But if your number is part of
a loop that is 51 or longer,
[310]
you are in trouble.
[311]
You won't find it before you've exhausted
[313]
the 50 boxes you're allowed to search.
[317]
When you open the box
labeled with your number,
[319]
you are in fact starting
[321]
at the farthest point on
the loop from your slip.
[323]
You wanna know where is the
slip that points to this box,
[327]
but to find it, you have to
follow the loop of numbers
[330]
all the way around to the end.
[332]
That means if the prisoners
follow this strategy
[335]
and the longest loop is 51,
[337]
not just one or two prisoners
[339]
will fail to find their number,
[340]
but all 51 on this loop won't make it.
[344]
They make it to the box just
before the box with their slip,
[347]
but they have to stop searching there.
[353]
(both laughs)
[357]
So the probability that all
of the prisoners succeed
[360]
is just the probability
that a random arrangement
[362]
of a hundred numbers contains
no loops longer than 50.
[366]
Now I promised that this
probability would come out
[369]
to around one in three,
[370]
but how do we calculate it?
[373]
Well, imagine writing down
all the different ways
[376]
that you could connect
100 boxes to form a loop
[379]
of length 100.
[381]
So you could have box
one points to box two,
[384]
box two points to box three
to box four, and so on,
[388]
all the way to 100,
[389]
and then box 100 would
point back to box one,
[393]
or you could have something random.
[396]
Box five points to box
99 to box 17 and so on,
[400]
and let's pick the last one,
[402]
is 63.
[405]
And box 63 points back to box five.
[407]
So how many different arrangements
of these a hundred boxes
[411]
or permutations could you have?
[414]
Well, for the first box,
[416]
I have 100 different boxes
that I could choose from.
[419]
The second box, because
I've already used one,
[422]
I can only pick from 99 boxes,
[425]
and the next one, I can pick
from 98 boxes, and so on,
[428]
down to the very last box.
[430]
I don't really have a choice.
[431]
There's only one box left I
could put in the last position.
[436]
So the total number of
different permutations
[438]
would be 100 times 99, times 98, times 97,
[442]
all the way down to one.
[443]
That is just 100 factorial.
[447]
There are 100 factorial different ways
[451]
that you could create a
loop of a hundred boxes.
[455]
But what we can't forget
[457]
is that these are not
just lines of numbers.
[460]
They are loops.
[462]
So some of these lines that look different
[466]
are actually the same loop.
[470]
For example, two, three,
four, five, and so on
[473]
up to 100 and then 1
[475]
is the same thing as 1, 2, 3, 4, 5 to 100.
[479]
You can rearrange the way
you write these numbers
[482]
a hundred different ways,
[485]
but they all represent the same loop.
[488]
So the total number of
unique loops of length 100
[492]
is 100 factorial divided by 100.
[496]
So what is the probability that any
[500]
random arrangement of 100 boxes
[502]
will contain a loop of length 100?
[504]
Well, it's just equal to the
number of unique such loops
[508]
that we just calculated,
[509]
100 factorial over 100,
[511]
divided by the total number of ways
[513]
that you could put a
hundred slips in 100 boxes,
[516]
which is 100 factorial.
[519]
So the answer is 1 over 100.
[523]
So there is a 1% chance that
a random arrangement of slips
[526]
results in a loop of length 100,
[529]
and this is a general result.
[531]
The probability that you
get a loop of length 99
[534]
is 1 over 99.
[537]
The probability that you
get a loop of length 98
[539]
is 1 over 98.
[542]
So the probability that there
is a loop longer than 50
[546]
is 1 over 51 plus 1 over 52
[549]
plus one over 53, et cetera.
[552]
Add all these up, and it equals .69.
[555]
There is a 69% chance of
failure for the prisoners,
[559]
meaning a 31% chance of success
[561]
where the longest loop is 50 or shorter.
[567]
- I still find it difficult to believe.
[569]
- [Derek] This feels a bit like magic.
[572]
Using the loop strategy,
[573]
all the prisoners are more
likely to find their numbers
[576]
than even just two prisoners
choosing at random.
[579]
So using the loop strategy,
[581]
what is the probability
that each prisoner alone
[584]
finds their number?
[586]
It is still 50%.
[589]
Each prisoner can still
only open half the boxes,
[592]
so their individual chance is still 1/2,
[595]
but these probabilities
[597]
are no longer independent of each other.
[600]
Imagine running this experiment
a thousand times over.
[603]
If everyone is guessing randomly,
[605]
you'd expect that on most
runs around 50 prisoners
[608]
would find their number.
[610]
On lucky runs, the number
would be a bit higher,
[612]
on unlucky runs, a bit lower.
[614]
But using the loop strategy,
[617]
all of the prisoners
would find their numbers
[619]
31% of the time.
[621]
And 69% of the time, fewer
than 50 find their number.
[626]
The prisoners all win together
[628]
or the majority loses together.
[631]
That's how this strategy works.
[635]
- Why are you assuming that
your number will always be
[638]
on the loop that you're on?
[639]
- I feel like-
- I don't understand that.
[640]
- This is a key question, right?
[642]
- 'Cause I feel like
it's possible to start
[645]
and go on a complete loop
[647]
and not come back to your own number
[650]
because you got on the wrong loop
[652]
and then you'd have to
get on another loop,
[654]
so I don't know that I'd buy this.
[656]
- Right, right, right,
right, right, right.
[658]
Now, the big question everyone asks is
[661]
how do you know that if you start
[662]
with a box with your number on it
[664]
you are guaranteed to be on the loop
[667]
that contains your slip?
[669]
Well, if you think about it,
[671]
the slip that says 73,
if anyone sees that,
[675]
they will definitely go to
the box with the number 73.
[679]
So the slip and box with the same number
[683]
essentially form a unit.
[685]
They're like a little Lego brick.
[687]
And then every slip is
hidden inside another box.
[693]
So as I start laying out
slips and boxes randomly,
[697]
you can see that there's no way
[699]
that we can end up with a dead end.
[702]
It's not like you can just
get to a box and then stop
[704]
because every box contains a slip
[706]
and that points at another box.
[709]
So the only way for you to see only boxes
[712]
when you walk into the room
[714]
is for every slip to be
contained within a box,
[720]
and that necessarily will mean
[722]
that we are forming loops.
[724]
So when I start with box 73,
[727]
I must eventually find slip 73,
[730]
because then and only then
[732]
will I be directed to go back to box 73
[735]
which closes the loop.
[739]
- Who is the warden to this prison?
[741]
And what kind of sadistic
mathematical warden
[745]
are you dealing with here?
[746]
This is awful.
[747]
- Now, what if there is a
sympathetic prison guard
[749]
who sneaks into the room before
any of the prisoners go in?
[753]
Well, then they can guarantee
success for the prisoners
[756]
by swapping the contents
of just two boxes.
[760]
That's because there
can be at most one loop
[763]
that is longer than 50,
[765]
and you can break it in half
[767]
just by swapping the
contents of two boxes.
[771]
And now I have two separate loops
[773]
that are each shorter than 50.
[776]
But what if there was a malicious guard
[779]
who figured out that the prisoners
[780]
were going to use this loop strategy?
[782]
Well, then they could
put the numbers in boxes
[784]
to ensure they formed
a loop longer than 50.
[788]
In this case, are the prisoners doomed?
[790]
Surprisingly, no.
[793]
They can counter by arbitrarily
renumbering the boxes.
[797]
They could, for example,
add five to each box number.
[801]
The loops are set both by
the locations of the slips
[805]
and by the box numbers.
[808]
Renumbering the boxes
is essentially the same
[810]
as redistributing the slips.
[812]
So the problem is back to a
random arrangement of loops,
[815]
meaning the prisoners are back to their
[817]
31% chance of survival.
[821]
Now, what happens if you
increase the number of prisoners?
[825]
- Fun fact, nobody knows if
[827]
as you have more and more prisoners
[829]
it's going towards a limit,
[830]
or if it'll eventually
go down to zero, or what?
[833]
- That is my friend Matt Parker,
[835]
and I think what he meant to say
[837]
is we know exactly what happens
[839]
as you increase the number of prisoners.
[841]
With a thousand prisoners each
allowed to check 500 boxes,
[845]
you might expect their chance of success
[847]
to drop dramatically,
[849]
but you can calculate
it like we did before,
[851]
and it comes out to 30.74%,
[855]
only half a percentage point
lower than for 100 prisoners.
[858]
For 1 million prisoners,
[860]
the probability of success is 30.685%,
[864]
which is only a little
higher than for 1 billion.
[867]
Of course, their bigger problem would be
[869]
the time it takes to open all the boxes.
[871]
So your probability of winning this game
[873]
does indeed approach a limit.
[876]
So what is that limit?
[879]
The formula we've been using
[881]
is one minus the chance of failure,
[883]
which is the series 1
over 51 plus 1 over 52,
[887]
and so on, up to 1 over 100.
[890]
We can depict this series as
the sum of areas of rectangles,
[895]
and there is a curve that follows
[897]
the heights of these blocks.
[899]
That curve is one over X.
[901]
The area under that curve from 50 to 100
[905]
approximates the area
of all the rectangles.
[908]
And as the number of
prisoners goes to infinity,
[911]
it becomes a better and
better approximation.
[914]
So to find the probability of failure,
[916]
we can just take the
integral of one over X
[919]
from n to 2n.
[921]
And we find that it's equal to
the natural logarithm of two.
[925]
This gives a probability of success
[927]
of one minus the natural log of two,
[929]
which is about 30.7%.
[933]
The bottom line is
[934]
that no matter how many
prisoners you have,
[937]
you'll always end up
with above a 30% chance
[939]
of escaping using this strategy.
[941]
And that feels really wrong.
[943]
I mean, at first it seemed
essentially impossible
[945]
for all 100 prisoners
to find their numbers.
[947]
But now we're seeing that you could have
[949]
a hundred, a million,
[950]
or any arbitrarily large
number of prisoners
[953]
with at least a 30% chance that
they all find their numbers.
[956]
The beauty of the loop strategy
[958]
is linking everyone's outcomes together,
[961]
instead of each prisoner walking in
[963]
with their own 50-50 shot.
[965]
Following the same loops
means that they have
[967]
the exact same chance
of finding their number
[969]
as everyone else in their loop.
[971]
And once the boxes and slips are arranged,
[973]
that chance is set at either 100% or 0%.
[977]
With this strategy, you can't
ever get close to winning
[980]
with only a few people
missing their numbers.
[982]
You can only fail hard
or succeed completely.
[993]
Now, if you like solving puzzles
[995]
even outside of life-threatening
prison situations,
[998]
well, you'll love Brilliant,
these sponsor of this video.
[1001]
Brilliant is a website and app
[1002]
that builds problem-solving skills
[1004]
and guides you through
engaging interactive lessons
[1007]
in math and science.
[1008]
They have great courses on tons of topics,
[1010]
from statistics to astrophysics to logic.
[1013]
Now, if you liked this riddle
[1015]
and you want more just like it,
[1016]
I'd recommend their
perplexing probability course,
[1019]
featuring other seemingly impossible odds
[1022]
and even another mathematically
inclined prison warden.
[1025]
They've also got a joy
of problem solving course
[1028]
to take you through some of their
[1029]
most delightful math puzzles.
[1031]
Every lesson builds on
what you learned previously
[1034]
to give you an in-depth understanding
[1035]
with any course you take.
[1037]
Your knowledge is constantly developed
[1039]
and tested through interactive
experiments and quizzes.
[1042]
And if you get stuck, there's
always a helpful hint.
[1045]
Head over to brilliant.org/veritasium
[1048]
to check out all these courses
[1049]
and test your instincts
after learning about
[1051]
the 100 prisoners riddle.
[1053]
If you click through right
now, Brilliant are offering
[1056]
20% off an annual premium subscription
[1058]
to the first 200 people to sign up.
[1060]
So I wanna thank brilliant
for supporting Veritasium,
[1062]
and I want to thank you for watching.
Most Recent Videos:
You can go back to the homepage right here: Homepage