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

41–50 of 59 posts

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

#41

Post by RiderOfGiraffes »

Someone wrote: post #39
RiderOfGiraffes wrote: post #9

Earlier quoted context omitted.

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 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 is put back exactly as it was, and they're not allowed to communicate with the others.

What does the third person do? They're confronted by 100 closed boxes with no idea of anything, except that the first person's name is in the first 50 boxes, and the second person's name is in the second 50 boxes.

So, what now?

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

#42

Post by fleitz »

Easy, first prisoner randomizes the order of the boxes, opens and sorts the first 50 boxes, hoping to find his name. Chance 1 in 2

Next prisoner uses a binary search to find his name in the first 50. Should have to open 6 boxes (log2(50)), if he finds it in the first 50 great. Either way he then sorts the next 44 boxes. Chance around 88%

3rd prisoner sorts the remaining 6 boxes, and finds his name in one of three piles using binary search. Chance, 100%

All remaining prisoners can use a binary search. log2(50) + log2(44) + log2(6)

I don't know how to integrate the 50% -> 88% chance, I'd estimate the answer to be around 44% based on my gut.

If the prisoners don't know the order they enter the room then they should each turn the first unturned box sideways to communicate the state of order. eg. if the first box is turned sideways you are prisoner #2.

I don't know if this is a brain teaser or just asking how to calculate the chances of 1/2 50 times in a row. (eg. the probability of correctly predicting 50 coin flips in a row)

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

#43

Post by dedward »

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…

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?

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

#44

Post by dedward »

Jabbles wrote: post #4
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.

Is the wording completely correct?

Seem so - I haven't worked out the math yet - but remember the goal here isn't "waht's the guaranteed winning strategy" - because there isn't one. Odds are everyone is doing prison for life - but there is an optimal strategy that's better than it might seem at first that the group could use to at least reduce their odds of life in prison.

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

#45

Post by dedward »

fleitz wrote: post #42

Easy, first prisoner randomizes the order of the boxes, opens and sorts the first 50 boxes, hoping to find his name. Chance 1 in 2 Next prisoner uses a binary search to find his name in the first 50. Should have to open 6 boxes (log2(50)), if he finds it in the first 50 great. Either way he then sorts the next 44 boxes. Chance around 88% 3rd prisoner sorts the remaining 6 boxes, and finds his name in one of three pil…

The boxes are closed and each person enters the room in the exact state as the previous one, with no knowledge of what the other person found.

I'm not seeing how a binary search will help you find your name in a randomized set of names - there is no order to work from to perform the search.

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

#46

Post by RiderOfGiraffes »

dedward wrote: post #43
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…

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.

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

#47

Post by dedward »

Late in the day hypothesizing here.

As the boxes are random, and the order is unknown, and there is no hidden information passed between each prisoner, and the room is reset each time - the only controllable factor the prisoners can agree on ahead of time is the strategy for which boxes each one will open.

Given the boxes are already randomized, using a random order is no more useful than using a sequential order.

So assuming they know the layout of hte boxes (is it 100 in a line or 100 in a square... presumably this can be figured out or some other strategy accounted for so everyone approaches things the same way) - each person opening 50 boxes has the same odds of finding their name. To maximize the odds of the entire GROUP finding their name, we need to ensure that each box is opened the same number of times by the end of the exercise. As we can't pass any information back and forth, this is the best we can do.

First 50 people open the first 50 boxes. Second 50 people open the second 50 boxes.

Or - as they may or may not know their position - they only need a strategy that ensures that each box is opened an equal number of times by the end.

To me that still looks like (1/2)^100..... which by definition isn't the answer - so I'm missing something. Eager to see the answer.

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

#48

Post by RiderOfGiraffes »

dedward wrote: post #47

Late in the day hypothesizing here. As the boxes are random, and the order is unknown, and there is no hidden information passed between each prisoner, and the room is reset each time - the only controllable factor the prisoners can agree on ahead of time is the strategy for which boxes each one will open. Given the boxes are already randomized, using a random order is no more useful than using a sequential order. So…

  > To maximize the odds of the entire GROUP finding their
  > name, we need to ensure that each box is opened the same
  > number of times by the end of the exercise.
You were doing really well up to this point, but this doesn't follow.
Post reply on HN