This one became quite famous.
It's sometimes known as the Names and Boxes Problem.
In this problem, there are 100 prisoners,
and the warden comes and tells them that they will be given their freedom
if they can win the following game:
100 boxes are going to be put on the table.
In each box will be put one of the prisoner's names on a piece of paper.
They'll be lined up on a table in a room,
and the prisoners will be brought into the room one-by-one,
and each prisoner is permitted to look in 50 boxes, trying to find his own name.
When he is done, he is escorted out of the room.
He must leave the room exactly as he found it.
He has no further communication with the other prisoners.
In order to win the game, every prisoner must find his own name.
Now, this sounds really completely hopeless.
Just say again how many prisoners and how many boxes?
There are 100 prisoners. >>100 prisoners.
100 boxes. One name in each box. >>100 boxes.
Oh, you can only look in 50 of the 100.
But each prisoner can only look in 50.
Any individual prisoner's probability of finding his own name is 50%--one-half.
Nothing he can do about that.
So, how do you do this? What's your algorithm?
Well, one possibility is everybody looks in a random 50 boxes.
That gives you a probability of winning the game of 2⁻¹⁰⁰. Not very good.
Another algorithm is everybody looks in the same 50 boxes.
That has a probability of success of 0.
Right, which is essentially the same as the first one. >> Indistinguishable. All right.
So, the story with this puzzle is that Peter Bro Miltersen
and Anna Gal, a theoretical computer scientist that you may know,
were working on a problem, and they needed to be able to show that in a certain version of this problem,
that the prisoners had no algorithm which would give them any decent probability--
one over a polynomial or anything like that--
and they didn't see how to prove it,
and one day Miltersen happened to be passing a problem onto a friend of his,
Sven Skyum, over lunch,
and Sven Skyum said, "Well, have you tried this?"
And Miltersen told me he fell off his chair.
It turns out that there is an algorithm which will guarantee the prisoners
a better than 30% chance to win the game.
Irrespective of what N is here, it works for 100 prisoners,
but also for 1 million prisoners with probability of winning as better than 30%.
Even after you see the solution, it's hard to believe that this really works.
Remember, every individual prisoner has probability of only 50%.
There's no communication.
How could you possibly get enough correlation into this problem
to have the probability of all of them finding their own names to be 30%? It's ridiculous.
But here's the algorithm that's absolutely wonderful.
The prisoners first assign ownership of the 100 boxes randomly.
In other words, they choose a random permutation of the boxes
and assign ownership of the boxes, and every prisoner gets to know
all the ownerships, gets to memorize all the ownerships and everything.
Of course, these ownerships may have nothing to do with the names
that are inside the boxes, but that's okay.
So, now prisoner A goes into the room,
and he opens his box--he opens the box that's been assigned to prisoner A.
He looks inside, and it's got some other prisoner's name in it,
maybe prisoner G.
Then he goes over and he looks like prisoner G's box,
and maybe prisoner Q is there.
Then he opens the box for prisoner Q.
He opens it and finds prisoner C there, etc.
He keeps doing this, and he's hoping that he'll find his own name.
If he doesn't, too bad. Then he leaves the room.
The next prisoner does exactly the same thing.
Prisoner B goes in, and he opens the box for prisoner B,
looks for at the name inside, opens that box, and hopes that eventually
he'll get back to his name.
That's the algorithm. Right? Why in the world should this work? Right?
What's going on here?
Why would this be better than just going through in their permutation order
or something like that?
It's not at first at all clear why this would work.
In fact, the only way I know people come up with this algorithm
is they're looking for something for prisoners to do.
The problem is once you think of this algorithm to now dismiss it
but instead to think about what would make it work.
What's going on here is that this random permutation combined with the permutation
of the prisoner's names in the boxes
gives you a permutation of the prisoners,
which is a uniformly random permutation.
But the permutation is defined in the following way.
You take a prisoner, you look inside his box, you see whose name is there.
That defines the permutation.
I said that prisoner A's box contained the name of prisoner G.
That means that in the permutation, A goes to G.
So, what's going to happen is that prisoner A will find his own name
if in this permutation the cycle that his name is in, the cycle that A is in
has length at most 50.
If that cycle has length less than 50--length of 50 or less--
he comes back and find his own name. Otherwise, he doesn't.
So, what does that mean?
Well, that means that the prisoners will actually win this game
if there are no long cycles.
Because then everybody will start in their own cycle come back around,
and find their own name.
Now, it turns out that it's actually very easy
to compute the probability that a permutation contains a long cycle.
Wait. Hang on one second.
Not only short, but it has to be short and contain that prisoner's information,
that prisoner's name. Right?
Well, we know it contains that prisoner's name, because he starts at the box that he owns.
For example, suppose the cycle is A, G, C, A.
Oh, the only way to get back to it is if you found the name. >>That's right.
Ah. Okay. All right. So, now your next step was you can find the probability
that there is a long cycle.
It's to compute the probability that a random permutation contains a long cycle.
Well, it's actually quite easy to show.
It's just a little--just write down the binomial coefficients--
that the probability that the permutation contains a cycle of length k
where k is bigger than n/2 is exactly 1/k.
So, the probability that our permutation contains a cycle of length greater than 50
is 1/51 + 1/52 + 1/53 + … + 1/100,
which is about n log 2--0.69 something.
So, the probability of the prisoners winning is about 0.31.
You know, you could sit and stare at this thing
and still not really understand why it works so well. >>Crazy.
So it's go harmonic numbers in it and logarithms
and a kind of simple tail-chasing kind of algorithm.
That's right. It's just nice reasoning, right? Nice, undergraduate reasoning.