Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Puzzle HN: 100 prisoners, 100 boxes...

news.ycombinator.com

Post reply on HN
Print view View original

31–40 of 59 posts

Re: Puzzle HN: 100 prisoners, 100 boxes...

#31

Post by srgseg »

RiderOfGiraffes wrote: post #27
srgseg wrote: post #19

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.

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#32

Post by RiderOfGiraffes »

o_nate wrote: post #29
photon_off wrote: post #21

Earlier quoted context omitted.

Correct, and after each prisoner goes, the boxes are restored to their original state.

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 ope…

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#33

Post by RiderOfGiraffes »

srgseg wrote: post #31
RiderOfGiraffes wrote: post #27

Earlier quoted context omitted.

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.

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#34

Post by srgseg »

RiderOfGiraffes wrote: post #33
srgseg wrote: post #31

Earlier quoted context omitted.

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.

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#35

Post by o_nate »

srgseg wrote: post #30
RiderOfGiraffes wrote: post #28

Earlier quoted context omitted.

I've explained it to many non-mathematicians, and they certainly seemed to have understood.

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#36

Post by o_nate »

RiderOfGiraffes wrote: post #32
o_nate wrote: post #29

Earlier quoted context omitted.

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 ope…

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#37

Post by srgseg »

o_nate wrote: post #35
srgseg wrote: post #30

Earlier quoted context omitted.

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.

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.

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".

Re: Puzzle HN: 100 prisoners, 100 boxes...

#38

Post by RiderOfGiraffes »

srgseg wrote: post #34
RiderOfGiraffes wrote: post #33

Earlier quoted context omitted.

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.

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.

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.

Not much point in debating it further.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#39

Post by Someone »

RiderOfGiraffes wrote: post #9
Someone wrote: post #3

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…

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.

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.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#40

Post by RiderOfGiraffes »

o_nate wrote: post #36
RiderOfGiraffes wrote: post #32

Earlier quoted context omitted.

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.

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.

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.

Post reply on HN