100 prisoners need to find their names
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
100 prisoners need to find their names
Once again 100 prisoners are locked up with a quirky chance of being released. This time the guard tells them he will bring them one at a time into a room with 100 boxes. Each box contains one of their names (they all have unique names and each of their names is in some box). Each prisoner may look inside up to 50 of the boxes to try to find his name. If every single prisoner ends up finding his name, they will all be released. The prisoners are allowed to discuss before any of them are sent into the room, but after the guessing starts, there is no more collusion.
How likely are they to be released?
solution thread
How likely are they to be released?
solution thread
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
 Nuclear Spoon
 Posts: 153
 Joined: Tue Jun 19, 2007 8:22 pm UTC
 Location: Surrey, England
 Contact:

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Are we to assume the boxes are numbered or otherwise distinguishable? Otherwise I don't see how any strategizing is possible.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
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."
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."
Cauchy, how are you getting 31%?
If the prisoners never have any information from the previous attempts, the best I can figure out right now is
(edited for spoilers if I'm right)
If the prisoners never have any information from the previous attempts, the best I can figure out right now is
1/2^50. Half the prisoners are assigned to look in 150, and the other half in 51100.
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.
(edited for spoilers if I'm right)
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Hbar, here are my thoughts so far, which is not anywhere close to a solution, but will tell you why your suggestion is wrong.
Also, I would like to point you towards the intro thread in the general discussion subforum, as we really like it when newcomers introduce themselves. (Plus it's kind of expected.)
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.
Also, I would like to point you towards the intro thread in the general discussion subforum, as we really like it when newcomers introduce themselves. (Plus it's kind of expected.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Thanks. I hadn't looked in general discussion before, so I didn't know about the intro thread. I just made a post there.
I see where I went wrong now. At first I briefly thought about nonindependent probabilities like you mentioned, but my thoughts went like this: If the first prisoner picks 150 and he's correct, the best boxes for the second prisoner to choose are 51100. But now the third prisoner doesn't have any way to link his success to the other two. He might as well pick 150, and the process repeats. Half end up picking 150, half end up picking 51100. Since order isn't important, you might as well have half do 150 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 near50% 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.

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
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."
Absolutely. Let's say the boxes are numbered just as you suggest. I have seen only a claim that the 31% figure is optimal. Supposedly it was proved by
but I am unable to find the proof anywhere.Eugene Curtain and Max Washauer
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
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.
HBar 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.
No, I don't think you're misinterpreting the problem. What's wrong is that you're saying "the first prisoner has a 50/100 chance of finding his name, and the second prisoner has at most a 50/99 chance of finding his name, so together, they have only a 2500/9900 chance of finding their names." This clearly can't be the case, because I have a solution for which all prisoners find their names with probability higher than 2500/9900.
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?

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
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?
I agree wholesale.
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
Can the prisoners move names between boxes? (and/or the boxes themselves?)
Edit  Apparently not. If they could, the prisoners would have at least a 49% chance of success.
Double edit  But then again, that was assuming the prisoners could choose the order they enter the room. If the guard chooses, 31% seems like it might be just right. I'll see if it works out that way.
Edit  Apparently not. If they could, the prisoners would have at least a 49% chance of success.
Double edit  But then again, that was assuming the prisoners could choose the order they enter the room. If the guard chooses, 31% seems like it might be just right. I'll see if it works out that way.
Last edited by HBar on Sun Jul 01, 2007 9:57 pm UTC, edited 2 times in total.
I made a critical false assumption in trying to solve this, and ended up looking it up. The solution is simple, yet elegant.
Hint (my false assumption):
Hint (my false assumption):
[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...

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
Do the boxes remain even after a prisoner has found his name in it? I am assuming they do.
This is hard, I can't seem to find anything that gives me anything better than 6.25%. But I am not very good at math yet. I will keep working at it.
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.
This is hard, I can't seem to find anything that gives me anything better than 6.25%. But I am not very good at math yet. I will keep working at it.
I must still be missing something. Assuming the prisoners can move names but don't know how many prisoners have been in the room before them, they can do better than 41.3%.
From the rest of the comments I assume the prisoners can do something with the names, but this can't be it.
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 5194. 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 95100.
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 5194 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 5194 will find it there.
The first prisoner with his name in 95100 will only have spent 12 guesses to find that it doesn't appear to be in 194. 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.
From the rest of the comments I assume the prisoners can do something with the names, but this can't be it.

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
HBar wrote:From the rest of the comments I assume the prisoners can do something with the names, but this can't be it.
The room is exactly the same for each prisoner. If they move names around, first they are beaten, then the guard puts the names back where they should be.
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
An interesting idea, HBar. Unfortunately, the prisoners aren't allowed to change the contents of the room. The 31% strategy works when no changes to the room are made and no prisoner can pass information to any other prisoner after the event has started. You might as well think of it as 100 identical rooms with 100 identical arrangements of names. The 100 prisoners are led into the rooms at the same time (one to each room), they make their selections, and then they all leave and the results are announced.
Okay, thanks for the clarification.
Now I suppose that they use the names they find as a program, but I can't figure out yet how they can do this in a way that links their success together...
Edit: How good is their memory? Are they all able to memorize each name and its alphabetical position before they start?
2nd edit: Got it! To answer my own question, yes. I'll take my solution to the other thread if the same thing isn't posted there already.
Now I suppose that they use the names they find as a program, but I can't figure out yet how they can do this in a way that links their success together...
Edit: How good is their memory? Are they all able to memorize each name and its alphabetical position before they start?
2nd edit: Got it! To answer my own question, yes. I'll take my solution to the other thread if the same thing isn't posted there already.
Sure, if they get to mess with the contents of the boxes, the easiest way I can think of is:
1) Open box 1.
2a) If you find one name in box 1, open boxes 250. If one of them was your name, put all 50 names in box 1. Otherwise, you all lose anyway, put all the names in box 2.
2b) If you find 50 names in box 1, open boxes 5199. If your name was in box 1, or 5199, put them all in box 1. Otherwise, you were in box 100, so put them all in box 2.
2c) If you find 99 names in box 1, open box 100, and put the name from it in box 1. Yay, everybody wins.
2d) If you find 100 names in box 1, one of them is yours. Yay, everybody wins.
2e) If you find box 1 is empty, everybody loses. Leave notes for other prisoners, to organize a riot...
Chance of success= 50% * 99%, or 49.5%. Which can't be beaten, without changing the problem some more.
HBar managed to work within the restriction "after the prisoners leave, each box still only has one name," which wasn't given...but it could have been, creating a different logic puzzle. And in that case, his solution gave them a better chance than 32%, but not so good as 48%. (See, once again I'm unwilling to do the arithmetic.)
But that's all moot, because they don't get to mess with the boxes, in the problem as given....
1) Open box 1.
2a) If you find one name in box 1, open boxes 250. If one of them was your name, put all 50 names in box 1. Otherwise, you all lose anyway, put all the names in box 2.
2b) If you find 50 names in box 1, open boxes 5199. If your name was in box 1, or 5199, put them all in box 1. Otherwise, you were in box 100, so put them all in box 2.
2c) If you find 99 names in box 1, open box 100, and put the name from it in box 1. Yay, everybody wins.
2d) If you find 100 names in box 1, one of them is yours. Yay, everybody wins.
2e) If you find box 1 is empty, everybody loses. Leave notes for other prisoners, to organize a riot...
Chance of success= 50% * 99%, or 49.5%. Which can't be beaten, without changing the problem some more.
HBar managed to work within the restriction "after the prisoners leave, each box still only has one name," which wasn't given...but it could have been, creating a different logic puzzle. And in that case, his solution gave them a better chance than 32%, but not so good as 48%. (See, once again I'm unwilling to do the arithmetic.)
But that's all moot, because they don't get to mess with the boxes, in the problem as given....
Pseudomammal wrote:Biology is funny. Not "haha" funny, "lowest bidder engineering" funny.
Who is online
Users browsing this forum: No registered users and 8 guests