100 Prisoners Problem - Page 2

hmm, probably it is the fact that they do not choose all boxes at once, but they open one at a time. Then they can use the name in the first box they open, to choose which box to open afterwards. yeah, that's must be it... brb.

I would have never have got it, I didn't understand the mathematics behind the explanation, I'll believe it though

Prisoner number a starts a box number a. He will there find the name of prisoner number b, and he will next open box number b, and so on.

This will work as long as there are no "loops" longer than 50 among the boxes. A loop is when you follow boxes with the algorithm above, you will eventually come back to where you started. Which is your number! So as long as you finish one lap in your loop within 50 steps, you're fine. If the loop is longer than 50, everyone with numbers in that loop will fail, which is what correlates the success of the prissoners. and since this is everyone or noone thingy, you want as much correlation as possible.

Next thing would be to calculate the probability of not having loops longer than 50. But I wont do that. If this is correct solution, the calculation will be in walrus' spoiler. if im wrong, it wont make snece to calculate it. But 30% sounds plausible at first sight.

Then proving that there are no other better strategies... no idea right now. Maybe you can make som smart argument, or it will be very complicated.
I'll have a look at the spoiler anyway.

And they didnt prove that it was the best strategy, or calculate the probability exactly, which suggest that both are complicated. Which probably forgives my omission of those two...

First of all i dont understand how they get the 30% probability. Second isn't there a high probability that a box has the name written on it in it? What is the prisoner supposed to do then?

the probability of it having the name in it is 1%. If he finds it on the first try, that's just good =)

And he wont find it on the second try or later, because to get there he would have to pick the name which is in the box he should go to. If name number 5 is in box number 5, then he cant get to box number 5 by picking name 5 from another box.

The 30% isnt obvious at all. :/ If you understand the picture with the loops it will seem a bit more reasonable that it is in the range 10%-50% instead of 10^-9 though.

Actually, we're going to designate two prisoners. If they both find their name, then everybody lives. Otherwise, everybody dies; if there were a 30% chance of everybody finding in any one situation each of those 30%s would satisfy these requirements too, so the chance of living is greater than or equal to 30%. We might as well remove all the boxes with the names of other prisoners, and all the other prisoners don't need to open any boxes since it has no effect in this scenario as opening a name of another prisoner has no effect and with zero information transfer somebody whose choices do not directly affect the chance of instadeath has no effect on whether the two designated prisoners find their name. As the boxes are effectively indistinguishable from the start, there is only one variable involved, how many chosen boxes overlap for designated prisoner A and designated prisoner B. We may as well rearrange the boxes in our minds so that there are first X blocks that A chooses only, 50-X that A and B choose, X that B chooses only, and 50-X that neither choose. This number X is a constant for any given runthrough. Now, lets examine where A's name is - there is a 50% chance of it lying in the first 50, and in fact, a X% chance of lying in a box B is not choosing and a 50-X% of lying in a box A and B are choosing. Examine, now, where B's name is - in the X% chance case that A's name is not in the fifty boxes that B is choosing, there are 50 boxes that say life with 99 to choose from - a (X/100)(50/99) chance that A's name is in a box he chooses but not in a box that B has chosen and that B's name is in a box that B has chosen. Consider the other case that spells life - that A's name is in the 50-X that B has also chosen. Then there are 49 unoccupied boxes that spell life for B, and 99 that spell death, giving us a ((50-X)/100)(49/99) chance that A's name is in a box that both A and B have chosen and that B's name is in a box he has chosen. This covers all cases where the names of A and B are in the fifty they have chosen, giving us a total of (X/100)(50/99) + ((50-X)/100)(49/99) chance that they have survived, or (50X + (50*49 - 49X)/(99*100) = (X + 49*50)/(99*100). But since X must be between zero and fifty, (X + 49*50)/(99*100) <= (50 + 49*50)/(99*100) = 50/198 ~= 25.2525% < 30%.