4 ms·

Correct, and after each prisoner goes, the boxes are restored to their original state.

o_nate 16y ago
I'm going to post my current thinking on this, in the hopes that maybe someone can give me a hint without revealing the whole solution: It seems to me that the best that the prisoners can do is 1/2^50 (and the worst they can do is 0). For instance, if the prisoners decided that everyone would just open boxes 1-50, then they would have zero chance of finding all 100 names (since 50 of the boxes would never even be opened). It seems like the best they can do to maximize their chances is to make sure that each box is tried exactly 50 times. One way to do that is to divide the prisoners into two groups of 50, then assign the first group to boxes 1-50 and the second group to boxes 51-100. Then the chances that the first group all find their names is 1/2^50 (not 100% sure about this number, but it seems reasonable) - and if the first group all find their names, then the second group will too (since if all 50 in the first group were found in boxes 1-50, then all 50 in the second group must be in boxes 51-100). So the total probability of success is 1/2^50. What's wrong with this?
- RiderOfGiraffes 16y ago
  The number isn't exactly right, but the reasoning is broadly right. That number is still unreasonably small, and nowhere near what can be achieved.
  - o_nate 16y ago
    OK, I gave up and looked at the answer. Pretty amazing. Just out of curiosity, why isn't the probability of my solution equal to 1/2^50? edit: I think I found the answer: it should be equal to (50!)^2/100!, right? Now, how to decide if that's smaller or larger than 1/2^50? edit: Awesome! thanks for the answer.
    - RiderOfGiraffes 16y ago
      Because if the first person succeeds in finding their name in the first half it then makes it less likely for the next person to find their name there. Once the first 49 people have found their name in the first half, there's only a 1/51 chance that the last person will. It's late and my brain has turned off for the day, but it's something like this ... Arrange 100 people, and ask in how many ways the first 50 are in the first 50 places. There are 50!.50! ways of arranging things with the first 50 first, and the others next. That's out of 100! arrangements in total. So you get 50!50!/100! You can evaluate that approximately by using Stirling's approximation: n! ~ (n/e)^n.sqrt(2.pi.n). The answer is about sqrt(100.pi)/2^100. Probably. Too tired to check it. Follow the reasoning and check that, not the answer.

I'm going to post my current thinking on this, in the hopes that maybe someone can give me a hint without revealing the whole solution: It seems to me that the best that the prisoners can do is 1/2^50 (and the worst they can do is 0). For instance, if the prisoners decided that everyone would just open boxes 1-50, then they would have zero chance of finding all 100 names (since 50 of the boxes would never even be opened). It seems like the best they can do to maximize their chances is to make sure that each box is tried exactly 50 times. One way to do that is to divide the prisoners into two groups of 50, then assign the first group to boxes 1-50 and the second group to boxes 51-100. Then the chances that the first group all find their names is 1/2^50 (not 100% sure about this number, but it seems reasonable) - and if the first group all find their names, then the second group will too (since if all 50 in the first group were found in boxes 1-50, then all 50 in the second group must be in boxes 51-100). So the total probability of success is 1/2^50. What's wrong with this?

RiderOfGiraffes 16y ago
The number isn't exactly right, but the reasoning is broadly right. That number is still unreasonably small, and nowhere near what can be achieved.
- o_nate 16y ago
  OK, I gave up and looked at the answer. Pretty amazing. Just out of curiosity, why isn't the probability of my solution equal to 1/2^50? edit: I think I found the answer: it should be equal to (50!)^2/100!, right? Now, how to decide if that's smaller or larger than 1/2^50? edit: Awesome! thanks for the answer.
  - RiderOfGiraffes 16y ago
    Because if the first person succeeds in finding their name in the first half it then makes it less likely for the next person to find their name there. Once the first 49 people have found their name in the first half, there's only a 1/51 chance that the last person will. It's late and my brain has turned off for the day, but it's something like this ... Arrange 100 people, and ask in how many ways the first 50 are in the first 50 places. There are 50!.50! ways of arranging things with the first 50 first, and the others next. That's out of 100! arrangements in total. So you get 50!50!/100! You can evaluate that approximately by using Stirling's approximation: n! ~ (n/e)^n.sqrt(2.pi.n). The answer is about sqrt(100.pi)/2^100. Probably. Too tired to check it. Follow the reasoning and check that, not the answer.