Kind: captions
Language: en
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're about to hit me with some
truth bombs i mean if you're trying to
create controversy and you're trying to
confuse people you're gonna succeed
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
say there are 100 prisoners numbered one
to a hundred slips of paper containing
each of their numbers are randomly
placed in a hundred boxes in a sealed
room
one at a time each prisoner is allowed
to enter the room and open any 50 of the
hundred 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 one-half times a half times a
half a hundred times or a half to the
power of a hundred
this is equal to point zero zero zero
zero zero zero zero zero thirty 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 if 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 over 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 peterborough
milterson he didn't even think of this
strategy until a colleague pointed it
out
milterson 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 one hundred 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're 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 want to 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
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 and three
but how do we calculate it
well imagine writing down all the
different ways that you could connect a
hundred 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 5
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 5. so how
many different arrangements of these
hundred boxes or permutations could you
have well for the first box i have a
hundred 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 1. 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 a
hundred and then one is the same thing
as one two three four five to a hundred
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 100
slips in 100 boxes which is
100 factorial
so the answer is
one over a hundred so there is a one
percent 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 1 over
etc
add all these up and it equals 0.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
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 percent
each prisoner can still only open half
the boxes so their individual chance is
still one half
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 percent 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 still understand that this is a key
question right i feel like
it's possible to start
and go on a complete loop and not come
back to your own number
because you gotta you got on the wrong
loop and then you have to get on another
loop so i i don't know that i buy this
right right right right right now the
big question everyone asks is how do you
know that if you start with the 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
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 it will 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
400 prisoners
for 1 million prisoners the probability
of success is
30.685 percent which is only a little
higher than 41 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 1 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 1
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 1 over x from
n to 2n and we find that it's equal to
the natural logarithm of 2. this gives a
probability of success of one minus the
natural log of two which is about thirty
point seven percent
the bottom line is that no matter how
many prisoners you have you'll always
end up with above a thirty 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
one hundred percent or zero percent 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
[Music]
now if you like solving puzzles even
outside of life-threatening prison
situations well you'll love brilliant
the 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 or offering
20 off an annual premium subscription to
the first 200 people to sign up so i
want to thank brilliant for supporting
veritasium and i want to thank you for
watching