4 ms·

Found 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/Pu

by srgseg 16y ago

Found 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 ago
Assume the prisoners do not have access to the internet.
RiderOfGiraffes 16y ago
Thanks for spoiling the fun for everyone. 8-(
photon_off 16y ago
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 16y ago
  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 16y ago
    I've explained it to many non-mathematicians, and they certainly seemed to have understood.
    - srgseg 16y ago
      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 16y ago
        Here's another link that explains it pretty well without using any fancy math: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf 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 16y ago
        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 16y ago
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 16y ago
  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 16y ago
    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 16y ago
      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 16y ago
        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 16y ago
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-boxes-proof-of-optimality http://mathoverflow.net/questions/31499/100-prisoners-100-bo...

by srgseg 16y ago

photon_off 16y ago

Assume the prisoners do not have access to the internet.

RiderOfGiraffes 16y ago

Thanks for spoiling the fun for everyone. 8-(

photon_off 16y ago

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 16y ago
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 16y ago
  I've explained it to many non-mathematicians, and they certainly seemed to have understood.
  - srgseg 16y ago
    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 16y ago
      Here's another link that explains it pretty well without using any fancy math: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf 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 16y ago
        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 16y ago

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 16y ago
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 16y ago
  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 16y ago
    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 16y ago
      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 16y ago

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-boxes-proof-of-optimality http://mathoverflow.net/questions/31499/100-prisoners-100-bo...