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

11–20 of 59 posts

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

#11

Post by srgseg »

o_nate wrote: post #10
RiderOfGiraffes wrote: post #8

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

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

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

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

#12

Post by RiderOfGiraffes »

srgseg wrote: post #11
o_nate wrote: post #10

Earlier quoted context omitted.

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

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

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

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

#13

Post by srgseg »

RiderOfGiraffes wrote: post #12
srgseg wrote: post #11

Earlier quoted context omitted.

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

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

Thanks 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!

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

#14

Post by RiderOfGiraffes »

srgseg wrote: post #13
RiderOfGiraffes wrote: post #12

Earlier quoted context omitted.

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

Thanks 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!

email me - address is in my profile.

In return, consider this: http://news.ycombinator.com/item?id=1891084

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

#15

Post by photon_off »

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 see what you mean. Prisoner 1 could memorize all of the names and just tell the next one if he's in the front or back 50.

The catch is: once the prisoners decide on a strategy, they are not permitted to communicate anymore.

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

#17

Post by photon_off »

RiderOfGiraffes wrote: post #2

I know this, but I won't spoil it for those who don't. It's a staple in some circles I frequent.

I 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?

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

#18

Post by evanchen »

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

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

#20

Post by photon_off »

evanchen wrote: post #18

The 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 t…

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