Hacker News Reader

Hacker News

Comment by srgseg | Hacker News Reader

Full thread

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.

View on HN

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

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.

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.

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.

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

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.

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.

<shrug> Not much point in debating it further.

Assume the prisoners do not have access to the internet.

Thanks for spoiling the fun for everyone. 8-(

Reply on news.ycombinator.com