HN Explorer

Puzzle HN: 100 prisoners, 100 boxes...

13 points by jlees ↗ HN
There are 100 prisoners and a sadistic prison warden. The warden has 100 boxes labeled 1-100, in which he randomly distributes 100 pieces of paper. Each prisoner's name is written on one and only one piece of paper.

The warden says to the prisoners: "You may each open any 50 of these boxes that you choose. If all 100 of you find the box with your name in it, you may all go free. If any of you fail, you will be imprisoned forever." He tells the prisoners that they may agree on their strategy beforehand, but that he will choose them to enter the room in a random order, and they will not know anything about the previous prisoners' experiences ahead of time. They cannot move the paper around between boxes.

What are the best odds the prisoners can give themselves? (Hint: it's better than 1/2^100.)

Bonus question: in the limit as the number of prisoners goes to infinity (and correspondingly, the number of boxes), what value do the optimal odds approach?

58 comments

[ 2.4 ms ] story [ 104 ms ] thread
RiderOfGiraffes
I know this, but I won't spoil it for those who don't. It's a staple in some circles I frequent.
Jabbles
Is the wording completely correct?
dedward
Seem so - I haven't worked out the math yet - but remember the goal here isn't "waht's the guaranteed winning strategy" - because there isn't one. Odds are everyone is doing prison for life - but there is an optimal strategy that's better than it might seem at first that the group could use to at least reduce their odds of life in prison.
photon_off
I know this one too, and I'm pretty sure a set of problems containing this one was posted on hn a long while back. I suggest using the constraints of the problem to your advantage. There's only a limited number of ways one could choose boxes to open, and there's a limited amount of information to work with.

Here's a hint: If the prisoners cannot communicate after deciding on the strategy, is it possible there's any benefit of prisoners performing different strategies?

Beyond that, try to consider the different ways to select 50 boxes. They are randomized, so picking any 50 boxes at once will give you a 50% success rate, which with 100 ppl is unacceptably low. What other ways are there to select boxes? Are there any ways to pick boxes using information that's given?

Someone
I think you messed up the formulation of the problem. As stated, a strategy would be - first prisoner opens 50 boxes. - second prisoner opens the other 50. - each prisoner finds the box with the paper with his   name on it.

Success rate: 100%. There probably are other constraints but I can only guess at them (do they visit the room one by one, and must they decide on a box to choose before leaving? Who can talk to whom? Must they close all boxes before leaving the room?)

jonafato
I think the problem statement means that each prisoner must find his name independently of one another. e.g. Prisoner 1 opens 50 boxes, finds his name, then the boxes are closed and Prisoner 2 must do the same without any help.
RiderOfGiraffes
I believe the statement as made is correct, although not necessarily as clear as it could be.

For example, your suggested "strategy" is wrong - the first prisoner as you've stated only has a 50% chance.

Further, after each prisoner the boxes are closed so that each prisoner finds the room is exactly the same state, with no communication between them.

Someone
Apparently, my formulation isn't as clear as it could be, either :-)

My 'solution' has all of the prisoners point out 'their' box after the second one has opened the last 50 boxes.

As to the 'no communication between': if there is no communication, it seems each of them cannot do better than 51/100 (50 opened boxes, and if their name isn't there, a 2% gamble)

However that isn't true. Suppose the first 51 each open the first 50 boxes and decide to choose the 51st box if they do not find their name, Then, all others, working under the assumption that the first 51 found their name (if they didn't, the game is lost anyways), can just open the last 49 and be certain to find their name.

That would bring the probability to about 2^-50. I doubt that is the optimal strategy, though. There seems to be much more room between 1/100! and 0.01^100.

RiderOfGiraffes
I still, really don't understand what you're suggesting. Let's go carefully.

The first person opens 50 boxes. Let's suppose they find their own name (otherwise we're dead anyway). They leave the room, everything is put back exactly as it was, they're not allowed to communicate with the others.

It seems to me you're suggesting the next person opens the second batch of 50. OK. But then they leave the room, everything is put back exactly as it was, and they're not allowed to communicate with the others.

What does the third person do? They're confronted by 100 closed boxes with no idea of anything, except that the first person's name is in the first 50 boxes, and the second person's name is in the second 50 boxes.

So, what now?

dedward
How do they even know that? Does the game continue until the end - or does it end as soon as one person fails to find their name?
RiderOfGiraffes
They don't know that, but you may as well assume they do, because otherwise anything they do is pointless and has no effect.
dedward
True - but you only know that at the end of the puzzle. The point of the exercise is to maximize their strategy of winning. There is no "winning" strategy - but there is one that is significantly better than what immediately comes to mind.
RiderOfGiraffes
But that's not the point. The point is that without loss of generality each person can assume that the people before have all found their own names. If not then it makes no difference what they do, they're all doomed.

Unless I've misunderstood you.

Someone
The word 'close' does not appear in the problem formulation at all. Apparently, we must deduce that all boxes get closed between visits from "they will not know anything about the previous prisoners' experiences ahead of time". I am OK with that, but I still do not think it is a clear way to describe the problem.

So, ignoring that IMO fairly implicit message, the 'answer' I proposed is: prisoner #1 opens 50 boxes, prisoner 2 opens the other 50, and then each prisoner trivially searches for his name.

Nitpicking the text further: what is that ahead of time doing there? What time? What can they learn afterwards?

RiderOfGiraffes
I can't decide if you're trolling, or genuinely don't understand. This is becoming like explaining a joke, and turning into and endless sequence of refinements.

I'll answer you once more. If you don't get it after that, I don't really care.

  > The word 'close' does not appear in the problem 
  > formulation at all
No, but "open" does. The implication is that the boxes each contain a piece of paper on which exactly one name is written, and that each box is closed.

  > the 'answer' I proposed is: prisoner #1 opens 50 boxes,
  > prisoner 2 opens the other 50, and then each prisoner
  > trivially searches for his name.
You are assuming that the boxes can be left open. That is ruled out when the puzzle says:

  > and they will not know anything about the previous
  > prisoners' experiences ahead of time.
If the boxes remain open then, specifically, the second prisoner will know the names that have been seen by the first prisoner. That's not allowed.

  > Nitpicking the text further: what is that ahead of
  > time doing there? What time?
The time that they enter the room.

  > What can they learn afterwards?
If, for example, their strategy is that everyone opens the first box (which is pretty pointless, but this is just an example) then easch one will learn something about what the others knew. In this way they know things that the prisoners before them knew.

There are puzzles where this is significant. I'm not going to tell you if this is one of them.

I feel that your objections to the wording are very like the programmer who insists on more and more refinements to a specification, and eventually just transliterates the spec into code. Anything that can't be trivially transliterated is queried, until finally the specification is isomorphic to the code.

My apologies if I'm doing you a disservice, but I find it very difficult to find a position from which your questions become reasonable, and I offer answers and explanations in an attempt to learn more. Currently I'm failing, and perhaps it's time to give up.

Someone
No, I am not trolling. My initial remark (very early in this thread) was just that the formulation wasn't clear to me. I thought that might trigger a rewording that would help later readers. After that, I just answered questions about why I found (past tense!) it not clear. I also think I made clear that I do understand the problem:

  *Apparently, we must deduce that all boxes get closed between visits from "they will not know anything about the previous prisoners' experiences ahead of time". I am OK with that,*
but I guess I should have been even clearer. It may seem nitpicking, but to solve this, I need two things:

    - an understanding of what the problem is.
    - a solution to the problem.
I find it natural that, getting stuck at step 2, to revisit step 1, looking for something I missed on reading it first (Quoting Polya: 'What is the unknown? What are the data? What is the condition?'). When I did that, I started to wonder what the description tried to say. Since the trivial answer that I gave in my initial reply, I did get that, but it didn't exactly jump out to me.

Thanks for the polite replies, but let's close this discussion. It is helping neither of us.

[Dmn: initially, I thought "of course the probability is way better than (1/2)^100'. There are only 100! permutations to choose between", but rereading the problem once more I begin to wonder whether 'in which he randomly distributes 100 pieces of paper'* actually implies that each box receives one piece of paper. Please don't reply, or I may feel obliged to apologize again.]

photon_off
I see what you mean. Prisoner 1 could memorize all of the names and just tell the next one if he's in the front or back 50.

The catch is: once the prisoners decide on a strategy, they are not permitted to communicate anymore.

o_nate
So if I understand this correctly, once the prisoners start opening boxes, there is no communication allowed between them, right?
photon_off
Correct, and after each prisoner goes, the boxes are restored to their original state.
o_nate
I'm going to post my current thinking on this, in the hopes that maybe someone can give me a hint without revealing the whole solution:

It seems to me that the best that the prisoners can do is 1/2^50 (and the worst they can do is 0). For instance, if the prisoners decided that everyone would just open boxes 1-50, then they would have zero chance of finding all 100 names (since 50 of the boxes would never even be opened). It seems like the best they can do to maximize their chances is to make sure that each box is tried exactly 50 times. One way to do that is to divide the prisoners into two groups of 50, then assign the first group to boxes 1-50 and the second group to boxes 51-100. Then the chances that the first group all find their names is 1/2^50 (not 100% sure about this number, but it seems reasonable) - and if the first group all find their names, then the second group will too (since if all 50 in the first group were found in boxes 1-50, then all 50 in the second group must be in boxes 51-100). So the total probability of success is 1/2^50.

What's wrong with this?

RiderOfGiraffes
The number isn't exactly right, but the reasoning is broadly right. That number is still unreasonably small, and nowhere near what can be achieved.
o_nate
OK, I gave up and looked at the answer. Pretty amazing. Just out of curiosity, why isn't the probability of my solution equal to 1/2^50?

edit: I think I found the answer: it should be equal to (50!)^2/100!, right? Now, how to decide if that's smaller or larger than 1/2^50?

edit: Awesome! thanks for the answer.

RiderOfGiraffes
Because if the first person succeeds in finding their name in the first half it then makes it less likely for the next person to find their name there. Once the first 49 people have found their name in the first half, there's only a 1/51 chance that the last person will.

It's late and my brain has turned off for the day, but it's something like this ...

Arrange 100 people, and ask in how many ways the first 50 are in the first 50 places. There are 50!.50! ways of arranging things with the first 50 first, and the others next. That's out of 100! arrangements in total.

So you get 50!50!/100!

You can evaluate that approximately by using Stirling's approximation: n! ~ (n/e)^n.sqrt(2.pi.n). The answer is about sqrt(100.pi)/2^100.

Probably. Too tired to check it. Follow the reasoning and check that, not the answer.

RiderOfGiraffes
Some clarification:

Each prisoner finds the room in the same state as each other. After opening the boxes they are subsequently closed again before the next prisoner. I believe this was intended to be inferred from:

     ... they will not know anything about the
     previous prisoners' experiences ahead of time.
Hint - the probability of success is greater than 10%.

There is a modification of the "obvious" solution that even works if the warden knows the prisoners' strategy beforehand and behaves in a maximally pessimal (from the prisoners' point of view) manner.

o_nate
I can see that the prisoners can do better than 1/2^100, but I don't see how they could get anywhere close to 10% success - so I must be missing something big here.
srgseg
I've looked up this puzzle elsewhere and it is described as allowing the prisoners to manipulate the contents of the boxes they open to a limited degree.
RiderOfGiraffes
There is a way of doing this that does not require doing so. The places you have looked up might have described a weaker version of the puzzle.
[deleted]
(comment deleted)
evanchen
The first prisoner opens 50 and sorts the 50 in alphabetical order (in an obvious manner). The second prisoner, upon seeing the sort, can quickly see if his name was in the original 50 (My name is Evan, I should be before Henry and after Bobby, etc). If he finds it quickly, he has plenty of "openings" to help sort the remaining boxes (maybe in a second row behind the first).

The rest of the prisoners should be able to easily find their names within 50 trials.

Success rate is PRETTY close to 50%.

photon_off
The boxes' states are restored after each prisoner leaves the room, so there's no way to sort them. The ideal solution would actually work even if the order of the boxes was shuffled each time.
RiderOfGiraffes
So how does this gel with "They cannot move the paper around between boxes"?
srgseg
Found the solution here:

http://www.sciencenews.org/view/generic/id/7649/title/Puzzli...

http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/

Warning: Don't spend hours of lateral thinking trying to solve this puzzle unless you have a degree in mathematics.

photon_off
Assume the prisoners do not have access to the internet.
photon_off
You don't need math skills to solve this, only problem solving skills. There are only so many ways to systematically choose 50 boxes from 100 when the only information is a name on the inside and a number on the outside.
srgseg
I'm just trying to help people that might spend an hour looking for a simple kind of solution to this, when the answer is really quite complicated and the math involved in the linked solutions are way beyond the understanding of most non-mathematicians.
RiderOfGiraffes
I've explained it to many non-mathematicians, and they certainly seemed to have understood.
srgseg
Even the first solution linked to doesn't explain it. It only declares the result that the probabilities work out in a particular way.

The second link contains the math, and no way would a non-mathematician have been able to come up with that math.

o_nate
Here's another link that explains it pretty well without using any fancy math:

http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf

edit: I agree that this does involve some math, but I like that it all can be derived from basic principles of probability.

srgseg
That explanation is not consistent with the claim

You don't need math skills to solve this, only problem solving skills.

I'm just saying, it'd be nice if there is a warning when something that looks like a standard lateral thinking brain teaser is actually the topic of a paper submitted by a pair of professors of mathematics to the 2003 Conference on "Compexity".

RiderOfGiraffes
Just because the explanations you've found use mathematical terminology, that doesn't mean you need a degree in math to understand the solution if it's explained properly.
srgseg
I'd be very interested if you could explain it properly without using math, natural logarithms and Euler's constant as the linked solution does.
RiderOfGiraffes
Your arguing a different question. Getting the exact answer isn't the same as making it understandable. You don't need the math to get a feel for what's happening.
srgseg
To be fair, when the puzzle specifically asks:

What are the best odds the prisoners can give themselves? (Hint: it's better than 1/2^100.)

that is clearly an impossible ask without advanced mathematics, and anyone without such advanced math knowledge will not be therefore able to solve the problem.

RiderOfGiraffes
I think we're arguing from different premises. I think that once you know the algorithm, getting an answer of "around 30% to 35%" is both easily within the grasp of a reasonably educated person, and within the spirit of the statement.

The problem is getting the algorithm at all. The idea of chasing cycles is pretty common to mathematicians, and should be well-known to computer scientists, but is not well-known otherwise. To that extent, finding the algorithm will come more naturally to people who are familiar with discreet math.

If you want an answer that's exactly right in the limit then you certainly need more math, and quite a lot of it, but simple counting arguments get you between 20% and 40%. A little more care gets you "around 30%."

Perhaps you think that's "advanced math." I don't, and have done it in math enrichment classes for 14 year-olds. It's not in their curriculum, but the curriculum is so impoverished that's no surprise to anyone.

<shrug> Not much point in debating it further.

o_nate
This is an amazing solution, but the original question asked for the "optimal" solution. How can we be sure that this solution is the optimal solution? Is there a way to prove that no better solution can exist?

Edit: apparently there is a proof of optimality, mentioned here: http://mathoverflow.net/questions/31499/100-prisoners-100-bo...

fleitz
Easy, first prisoner randomizes the order of the boxes, opens and sorts the first 50 boxes, hoping to find his name. Chance 1 in 2

Next prisoner uses a binary search to find his name in the first 50. Should have to open 6 boxes (log2(50)), if he finds it in the first 50 great. Either way he then sorts the next 44 boxes. Chance around 88%

3rd prisoner sorts the remaining 6 boxes, and finds his name in one of three piles using binary search. Chance, 100%

All remaining prisoners can use a binary search. log2(50) + log2(44) + log2(6)

I don't know how to integrate the 50% -> 88% chance, I'd estimate the answer to be around 44% based on my gut.

If the prisoners don't know the order they enter the room then they should each turn the first unturned box sideways to communicate the state of order. eg. if the first box is turned sideways you are prisoner #2.

I don't know if this is a brain teaser or just asking how to calculate the chances of 1/2 50 times in a row. (eg. the probability of correctly predicting 50 coin flips in a row)

dedward
The boxes are closed and each person enters the room in the exact state as the previous one, with no knowledge of what the other person found.

I'm not seeing how a binary search will help you find your name in a randomized set of names - there is no order to work from to perform the search.

dedward
Late in the day hypothesizing here.

As the boxes are random, and the order is unknown, and there is no hidden information passed between each prisoner, and the room is reset each time - the only controllable factor the prisoners can agree on ahead of time is the strategy for which boxes each one will open.

Given the boxes are already randomized, using a random order is no more useful than using a sequential order.

So assuming they know the layout of hte boxes (is it 100 in a line or 100 in a square... presumably this can be figured out or some other strategy accounted for so everyone approaches things the same way) - each person opening 50 boxes has the same odds of finding their name. To maximize the odds of the entire GROUP finding their name, we need to ensure that each box is opened the same number of times by the end of the exercise. As we can't pass any information back and forth, this is the best we can do.

First 50 people open the first 50 boxes. Second 50 people open the second 50 boxes.

Or - as they may or may not know their position - they only need a strategy that ensures that each box is opened an equal number of times by the end.

To me that still looks like (1/2)^100..... which by definition isn't the answer - so I'm missing something. Eager to see the answer.

RiderOfGiraffes 

  > To maximize the odds of the entire GROUP finding their
  > name, we need to ensure that each box is opened the same
  > number of times by the end of the exercise.
You were doing really well up to this point, but this doesn't follow.
Rhapso
The answer you think you have to this it outside the bounds of the question you gave. Re-phrase the question honestly. The answer is .5^100. I am sorry, you will have to allow more power on the prisoners parts, perhaps the ability to label things.
RiderOfGiraffes
Unless I've misunderstood you, you are wrong.
Rhapso
Well, you insist there was no communication, but all solutions I can find that yield a probability you describe involve communication. Exemplar being that each box itself is labeled by a name. Each prisoner starts at the box with their name and reads the slip inside. following a chain of names until they reach their name. The flaw is that this solution violates the premise, the convicts will have knowledge about how the other convicts acted (similar to how they did, otherwise the system fails), which directly violates the premise.