1/2^50. Half the prisoners are assigned to look in 1-50, and the other half in 51-100.
Each prisoner in the first group only has a 50% chance of being correctly assigned. So it's a 1/2^50 chance that the first group was chosen correctly. And if they're all correct, so is the second half.
The prisoners don't get any information from previous attempts, but they can assume it. In particular, the prisoners should adopt a strategy that assumes each previous prisoner has found the name among the boxes they opened, because if this assumption is correct, it helps them, but if it is incorrect, the prisoners have already lost (since for them to succeed, every prisoner must be correct.
For example, suppose there were only four prisoners and boxes, and each prisoner could only open one. If each prisoner guesses two random boxes, you only have a 1/2^4 chance of winning, as you suggest, but if the first guesses 1 and 2, the second 3 and 4, the third 1 and 3, and the fourth 2 and 4, the chance of successful guesses is 50% for the first prisoner, 2/3 for the second (assuming the first was right), 50% for the third prisoner, and 2/3 for the last (assuming the third was right), for a total chance of winning of 1/9, or 11.11...%, which is almost double the 6.35% chance of winning when randomly guessing.
To put it another way, every prisoner, viewed individually, has a 50% chance of being correct, but one can engineer a strategy where the chances are not independent variables, so that while the individual odds remain at 50%, each correct guess increases the odds of other guesses being correct, and each incorrect guess decreases those odds.
Also, your strategy doesn't have the chance of winning you expect. Your strategy wins if the first 50 names are in the first 50 boxes. The chances of this is 50!*50!/100!~1/10^29, which is nowhere near as good as the 1/2^50~1/10^15 you assumed.
I see where I went wrong now. At first I briefly thought about non-independent probabilities like you mentioned, but my thoughts went like this: If the first prisoner picks 1-50 and he's correct, the best boxes for the second prisoner to choose are 51-100. But now the third prisoner doesn't have any way to link his success to the other two. He might as well pick 1-50, and the process repeats. Half end up picking 1-50, half end up picking 51-100. Since order isn't important, you might as well have half do 1-50 first.
Here's where my thoughts went really wrong. First, I basically ignored the slightly improved chances that the second half has. Second, I figured that if the first 50 prisoners are right, then the second 50 automatically are too - ignoring how in the way I initially set up the problem, it's a near-50% chance for all 100 prisoners instead of 50.
If I thought about my answer directly instead of going through this process, I should have seen what you said - that their overall probability with this method is (1/2)*(49/99)*(48/98)*...
But I agree, there are probably many better methods. I'm trying to work on one - let's hope I at least get the math right this time.
Cauchy wrote:I have a strategy that works just over 31% of the time, but I've never seen a proof that it's optimal. I'm pretty sure it's the intended solution, though.
The boxes are distinguishable, and the prisoners know this beforehand and know what the 100 boxes look like. For ease of argument, the boxes are numbered from 1 to 100 and the prisoners know this, so they can formulate strategies like "John, you open boxes 1 through 50; Billy, you open boxes 26 through 75."
but I am unable to find the proof anywhere.Eugene Curtain and Max Washauer
Small hint about the nature of the problem that you probably already figured out, but it's also probably good to get reassurance wrote:Like most of these "no one can guess incorrectly" games, you want to make it so that when one person messes up, a lot do. Since each prisoner by himself has only a 50% chance of finding his own name, you want to try to avoid cases where, say, 98 of the prisoners find their name, and two don't. Ideally, there'd be a strategy where either everyone wins or everyone loses, as this would have the prisoners being freed 50% of the time, but I'm fairly sure no such strategy exists.
Real information about the intended solution pertaining to the above hint wrote:In the intended solution, when one prisoner messes up, at least 51 do, and there's a chance that all 100 do.
H-Bar wrote:I might be misinterpreting the problem, but I don't see how 31% is remotely possible. Even with just the first two prisoners you're down to 25.2525...% at best no matter how you arrange it.
Cauchy wrote:How expected is it for newcomers to introduce themselves? I didn't, and I really don't like intro threads on principle, but I've been posting here for three months. Am I sufficiently not a newcomer to escape my otherwise unavoidable fate?
[color=white]I assumed that we could not adapt our strategy to the actual contents of the boxes. Why? The prisoners can't collude during the picking - they follow a "program," in a sense, and can't tell each other whether or not they've found their names. But this doesn't mean that they gain no information during the process, and that their program must always point them to the same box every time...
If the boxes remain, you get 6.25% with random guessing.
If the boxes dissappear, you get ~33% with random guessing.
Skeptical, your strategy doesnt seem to be any improvement. Even if 1 and 2 find their names, it wont have any effect on the combined probability of 3 and 4 finding their names.
Assume 1 finds his name in box A, and 2 finds his name in box D. If 3 looks in box B and D, he has a 50% chance of finding his name in box B. The same goes for 4 looking in box C.
Hint wrote:The answer has to do with which boxes the prisoners will pick.
Bigger hint wrote:The prisoners will find out which boxes to chose as they go along.
First, the prisoner looks for his name among the first 50 boxes with the assumption that they're sorted. He starts at 32, moving to 16 if his name comes earlier alphabetically or to 48 if his name comes later, etc. Either he finds his name in at most 6 tries, or he doesn't find his name but they appear sorted, or he discovers that these names aren't sorted. If they aren't sorted, he looks through all the first 50 and sorts them.
If he didn't find his name with those 6 tries but they appeared sorted, he does the same thing for 51-94. If he discovers they're not sorted, he sorts them. If they appear sorted but he doesn't find his name there either, he looks in 95-100.
The first person to enter, unless he's fooled by the first 50 appearing sorted when they're not, will sort the first 50 boxes. There's a better than 31/32 (>96.8%) chance that he wasn't fooled, so it's at least a 48.4% chance that he both found his name and sorted the first 50. Every subsequent prisoner with their name in those 50 will find it.
The first prisoner with his name not in the first 50 will sort 51-94 unless he was fooled. Again, the chances are better than 96.8% that he wasn't. There's an 88% chance that he found his name there, so the prisoners' overall chances to get to this point successfully are 41.3%. Now all prisoners with their name in 51-94 will find it there.
The first prisoner with his name in 95-100 will only have spent 12 guesses to find that it doesn't appear to be in 1-94. He can check the last 6 without problem, and has a 100% chance of success. Every prisoner after this point also has a 100% chance of success.
So the prisoners' chances aren't worse than 41.3%. But that ignores many factors that could improve their odds - we assume failure if a prisoner is fooled, but they still have a good chance of salvaging the situation. We also ignore the unused sorting abilities of prisoners who find their name quickly. And we assume the chance of being fooled is (1/2)^5, but this is an upper limit and the actual number is much smaller - each opened box narrows the range of names that could continue the deception in the next one.
H-Bar wrote:From the rest of the comments I assume the prisoners can do something with the names, but this can't be it.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.
Users browsing this forum: 3de4296t and 3 guests