**The Riddle That Seems Impossible Even If You Know The AnswerThe 100 Prisoners Riddle feels completely impossible even once you know the answer. **

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.

Share this –The Riddle That Seems Impossible Even If You Know The Answer

Pingback: I Visited The Yellowstone Zone Of Death - GreatPage.Org