7 ms·
Puzzle HN: 100 prisoners, 100 boxes...
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?
- RiderOfGiraffes 16y agoI know this, but I won't spoil it for those who don't. It's a staple in some circles I frequent.
- Jabbles 16y agoIs the wording completely correct?
- RiderOfGiraffes 16y agoYes, I shall clarify a few points in another comment.
- dedward 16y agoSeem 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 16y agoI 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 16y agoI 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 16y agoI 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 16y agoI 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 16y agoApparently, 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.
- o_nate 16y agoSo if I understand this correctly, once the prisoners start opening boxes, there is no communication allowed between them, right?
- photon_off 16y agoCorrect, and after each prisoner goes, the boxes are restored to their original state.
- o_nate 16y agoI'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 16y agoThe 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 16y agoOK, 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 16y agoSome 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 16y agoI 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 16y agoI'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 16y agoThere 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.
- srgseg 16y agoThanks for the clarification. Could you post a link to the solution? Or post it as a ROT-13 comment? Otherwise I might never find out the answer!
- RiderOfGiraffes 16y agoemail me - address is in my profile. In return, consider this: http://news.ycombinator.com/item?id=1891084 http://news.ycombinator.com/item?id=1891084
- deleted 16y ago[deleted]
- evanchen 16y agoThe 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 16y agoThe 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 16y agoSo how does this gel with "They cannot move the paper around between boxes"?
- srgseg 16y agoFound the solution here: http://www.sciencenews.org/view/generic/id/7649/title/Puzzling_Names_in_Boxes http://www.sciencenews.org/view/generic/id/7649/title/Puzzli... http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ 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 16y agoAssume the prisoners do not have access to the internet.
- RiderOfGiraffes 16y agoThanks for spoiling the fun for everyone. 8-(
- photon_off 16y agoYou 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 16y agoI'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 16y agoI've explained it to many non-mathematicians, and they certainly seemed to have understood.
- srgseg 16y agoEven 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.
- fleitz 16y agoEasy, 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 16y agoThe 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 16y agoLate 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 16y ago> 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.
- WettowelReactor 16y agoIsn't this problem a more complex version of the Monty Hall Problem? (http://en.wikipedia.org/wiki/Monty_Hall_problem http://en.wikipedia.org/wiki/Monty_Hall_problem).
- RiderOfGiraffes 16y agoNo.
- Rhapso 16y agoThe 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 16y agoUnless I've misunderstood you, you are wrong.
- Rhapso 16y agoWell, 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.