## 100 prisoners need to find their names

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

GreedyAlgorithm
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?

GENERATION 1-i: 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:
Are we to assume that more than one prisoner can look in the same box?

www.gaming4charity.org

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
Yep. The guard closes all the boxes after a prisoner is done with his <= 50 tries. Assume the room is memoryless, prisoners can't talk with subsequent prisoners, etc. etc.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

skeptical scientist
closed-minded 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

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
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."

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC
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
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.

(edited for spoilers if I'm right)

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco
H-bar, here are my thoughts so far, which is not anywhere close to a solution, but will tell you why your suggestion is wrong.

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

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC

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.

GreedyAlgorithm
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
Eugene Curtain and Max Washauer
but I am unable to find the proof anywhere.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC
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
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
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.

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?

GreedyAlgorithm
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 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

V
Posts: 49
Joined: Thu Nov 09, 2006 1:15 pm UTC
Supposedly it was proved by
Eugene Curtain and Max Washauer
but I am unable to find the proof anywhere.

Theese guys are named
Curtin and Warshauer
. The paper is called
The locker puzzle
.

EDIT: damn, i never get those tags right...

V.

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC
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.
Last edited by H-Bar on Sun Jul 01, 2007 9:57 pm UTC, edited 2 times in total.

jwwells
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am UTC
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):

[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...

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
V wrote:Theese guys are named
Curtin and Warshauer
. The paper is called
The locker puzzle
.

Good find!
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Zyphen
Posts: 4
Joined: Sun Jul 01, 2007 10:17 pm UTC
Location: Orlando, Florida
Do the boxes remain even after a prisoner has found his name in it? I am assuming they do.

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.

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC
I already know the answer to this one. I enjoyed the puzzle quite a bit. Here are two hints:

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.

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC
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%.

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.

From the rest of the comments I assume the prisoners can do something with the names, but this can't be it.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
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.

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 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
An interesting idea, H-Bar. 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.

H-Bar
Posts: 27
Joined: Sat Jun 30, 2007 9:22 pm UTC
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.

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC
Even if it wasn't the intended solution, I think H-Bar's solution was pretty clever.

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland
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 2-50. 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 51-99. If your name was in box 1, or 51-99, 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.

H-Bar 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 "ha-ha" funny, "lowest bidder engineering" funny.