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

51–59 of 59 posts

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

#51

Post by Someone »

RiderOfGiraffes wrote: post #41
Someone wrote: post #39

Earlier quoted context omitted.

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

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

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?

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

#52

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

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

#53

Post by dedward »

RiderOfGiraffes wrote: post #46
dedward wrote: post #43

Earlier quoted context omitted.

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?

They don't know that, but you may as well assume they do, because otherwise anything they do is pointless and has no effect.

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.

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

#54

Post by RiderOfGiraffes »

dedward wrote: post #53
RiderOfGiraffes wrote: post #46

Earlier quoted context omitted.

They don't know that, but you may as well assume they do, because otherwise anything they do is pointless and has no effect.

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.

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.

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

#55

Post by RiderOfGiraffes »

Rhapso wrote: post #52

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.

Unless I've misunderstood you, you are wrong.

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

#56

Post by RiderOfGiraffes »

Someone wrote: post #51
RiderOfGiraffes wrote: post #41

Earlier quoted context omitted.

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

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

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.

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

#57

Post by o_nate »

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.

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

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

#58

Post by Someone »

RiderOfGiraffes wrote: post #56
Someone wrote: post #51

Earlier quoted context omitted.

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

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

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

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

#59

Post by Rhapso »

RiderOfGiraffes wrote: post #55
Rhapso wrote: post #52

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.

Unless I've misunderstood you, you are wrong.

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.
Post reply on HN