[bushindo]

I misread the OP on the Prisoner on a death row problem ( http://brainden.com/forum/index.php?showtopic=8355 ), and thus solved a completely different problem. This is that problem. The initial conditions are the same as kidsrange's

There are 100 prisoners who are sentenced to die tomorrow. However, the warden has decided to give them a chance to live. He will put each of their names on a slip of paper inside an opaque, numbered (from 1-100) jar. Each prisoner will be able to open 50 jars in order to try to find their name. The prisoners will each do this individually, and in sequential order.

1) Each prisoner does not have to open the 50 jar sequentially. Each prisoner can remove the 50 slips from the jar and place them back in any order he desired. However, at the end, each jar must contain exactly 1 slip and no modification can be made to the jars' appearances, placement, orientation, etc.

2) After open and closing the 50 jars, each prisoner can select the jar that he thinks contain his name. That jar is not removed from the game. After this, the prisoner will be moved to a new room and have no communication with the ones who have yet to make their selection.

At the end of the selection process, prisoners who correctly identify their jar will live, and those who don't will die. Devise a strategy to save, on average, the maximum number of prisoners.

Edited May 12, 2009 by bushindo

[Guest]

Assuming the prisoners know each others names and are willing to cooperate, they could all live. Starting with the first prisoner, he selects jars 1-50, and places the largest value alphabetically in jar 50, then prisoner 2 comes in and selects jars 50-100 knowing that prisoner 1 put the largest value in 50 he searches 51-100 for to determine if that is infact the largest value, once prisoner 2 has checked all 50 jars he places the largest value in jar 100, now each subsequent prisoner simply has to compare only 2 jars, prisoner 3 would compare 99 and 98 and swap the values so they are in alphabetical order. and so on. By putting them in alphabetical order using this method after the last prisoner finishes, everyone would know which jar corresponded to their name, similar to how you find the contents of an array by index.

[HoustonHokie]

My guess is that you can always save 99 of the prisoners, and the other prisoner has a 50% chance of survival. Here's how it operates:

Each prisoner first opens the jar labeled with his number. If he finds the piece of paper with his number in it, he's spared. If not, he opens the jar labeled with the number of the piece of paper he holds. Again, if he finds his own number, he's spared. If not, he continues in the same fashion until he either finds his own number, or exhausts his 50 attempts. If he finds his own number, he places that slip of paper in the first jar he opened (labeled with his own number) and then opens the next highest jar that he has not yet opened. If jar and paper match, he moves on to the next highest jar. If they don't, he continues as before to move slips of paper to their corresponding jars until he completes the circuit or exausts his 50 attempts.

The first prisoner has a 50% chance of finding his own number. You can't change those odds much because he has no knowledge of the jars and there is no organization to any of them. But when he's done, 49 other prisoners have a 100% chance of finding theirs. If #1 finds the #2 piece of paper, then #2 will find his own number right off the bat. Otherwise, he opens jars and continues the sorting process begun by #1. Because #1 correctly sorted every slip he found, #2 won't open any of the jars #1 opened until he's found his own number, which he will be guaranteed to do in 50 attempts. After he finds his number, #2 uses the same procedure as #1 to sort higher jars.

Thus each prisoner #2 or higher will find his own number and live, and prison #1 has a 50% chance of finding his own number. So, on average, 99.5 prisoners are saved.

Postscript: a quick note about my assumptions. I assumed that when the prisoner chooses the jar at the end of his turn, the warden compares that jar with his number at that point in time to see if it is correct. If, instead, the prisoner gets to choose the jar where he thinks his number will end up, then they should all choose their own numbered jar, because they will all be correctly sorted at the end (and everyone will live).

[bushindo]

Some clarification to the original post.

Each prisoner, in turn, is allowed to open and shuffle the contents of 50 jars. At the end of each prisoner's turn, he identifies one jar as the one containing his name. The jar is not removed from play, but the warden determines whether the choice is correct or not at the end of every turn, and consequently, whether that prisoner will live or die.

[CaptainEd]

P1 sorts the first 50 jars, and looks at another one if he wasn't there. P(Survival) 0.51.

P2 sorts the second 50 jars alphabetically, looks at another if necessary. P(S)= 0.51

All other prisoners can use two binary searches, one on the first 50, and one on the second 50. In 6 comparisons, his/her name can be found in 50, so it might take 12 comparisons if it's in the other 50. At any rate, these prisoners find their names for sure P(S)=1.0.

So, 48 prisoners are certainly saved, 2 are saved with probability 0.51

[CaptainEd]

I responded to Doug, but HoustonHokie typed faster and thought deeper than I did. I think I understand it. Good job again!

Edited May 12, 2009 by CaptainEd

[bushindo]

HoustonHokie's approach is one that I didn't consider. Very nice. However, I think the expected number for his approach will be a tiny wee bit smaller, though. My approach is along the line of CaptainEd's, though with a slight difference.

We can modify's CaptainEd's approach a bit. Let the first guy sort the first 50. Let the second prisoner spend 6 searches on the first sorted 50 to find his name. He then can spend the remaining searches to sort jar 51-94. That way, we can bump his chance of living to about 94%. The 3rd guy will need to do a binary search on jar 1-50, another on 51-94, and a simple search on the last 6, with guaranteed 100% survival. So the expected number of prisoners saved is (.51 + .94 + 98 ) = 99.45

Edited May 12, 2009 by bushindo

[Guest]

with one night to prepare each takes a slip of paper and writes his name on it. He opens 50 Jars comes back for his final opening and swaps the paper inside with his. Everyone finds their name.

[HoustonHokie]

HoustonHokie's approach is one that I didn't consider. Very nice. However, I think the expected number for his approach will be a tiny wee bit smaller, though. My approach is along the line of CaptainEd's, though with a slight difference.

We can modify's CaptainEd's approach a bit. Let the first guy sort the first 50. Let the second prisoner spend 6 searches on the first sorted 50 to find his name. He then can spend the remaining searches to sort jar 51-94. That way, we can bump his chance of living to about 94%. The 3rd guy will need to do a binary search on jar 1-50, another on 51-94, and a simple search on the last 6, with guaranteed 100% survival. So the expected number of prisoners saved is (.51 + .94 + 98 ) = 99.45

But we can do better...

First, I want to revise the probability that prisoner 1 will live. He gets to open and shuffle 50 jars and he might find his name in those 50. But, even if he doesn't, he still has to tell the warden which jar his name is in at the end of his sorting. He picks a 51st jar at random, and could be right. So his chance is actually 51%.

[i realize that in my first post I was talking about numbers instead of names, but it is easier to deal with numbers and I assume that prisoners with perfect memory would also know everyone else's name and order alphabetically, which they could translate into numbers for purposes of sorting. An interesting twist on this problem would be if the prisoners did not know each others' names, but I won't go there now.]

Second, I wanted to clarify my assertion that prisoners 2-100 will live. The simple beauty of this solution is that prisoner 1 will put 49 slips of paper into their correct jars (the 50th slip of paper will be put into whatever jar is empty at the time, and is likely to be incorrect). The worst case situation for prisoner #2 is this: first, he finds that his name is not in jar #2 (51/100 chance). Second, following the search pattern I described before, he opens 49 more jars and does not find his name in those, which is possible, but not very likely (1/51 chance). Third, he then gets a chance to guess at one of the jars that he did not open and does not find his name there (49/50 chance). So prisoner #2's probability of finding his own name in jar #2 is (49/100) based on what prisoner #1 did. His probability of finding his name in a jar other than #2 is (50/51). And the probabilty of him guessing the right jar if he does not find his own name in all of that is (1/50). So prisoner #2's chances of living are (49/100)*1 + (51/100)*(50/51) + (1/100)*(1/50) = 0.9902.

If prisoner #2 does not find his own name, he will not have opened a jar that prisoner #1 also opened, except that he might open jar #1. This is because each slip of paper that prisoner #2 finds will not be in order, leading him to the next jar. But every name that prisoner #1 found got put into the proper jar, except the last name, which was put in jar #1, and prisoner #2 might find prisoner #1's name. Likewise, every name that prisoner #2 found got put into the proper jar, except the last name, which was put in jar #2. So, if prisoners 1 & 2 are executed, 98 of the names are properly sorted in the process. It is still possible (very unlikely, but possible), that prisoner #3 would come in after 1 & 2 are dead, and find that his name is not in jar #3. But, with 98 names properly sorted, he will be guaranteed to find his own name, as will every other prisoner thereafter.

The analysis begs the question, can there be fewer than 98 names sorted after prisoner #2 is done, because that might lead to a situation where a future prisoner is in danger? Of course, but only if the prisoners find their own names. Say, for example, that prisoner #1 manages to sort names 1-49 into jars 1-49 during his turn. Then prisoner #2 would open jars 2-49, find the proper names there, and only be able to sort 1 or 2 more names. But you can see what's happening here - the early prisoners are living and sorting the later prisoner's names. So the worse the earlier prisoners fare, the better off the later prisoners are. And prisoners 3-100 are guaranteed to live, as noted above.

So, the total number of prisoners expected to live is:

prisoner 1: 51% chance

prisoner 2: 99.02% chance

prisoner 3-100: 100% chance

total = 99.5002 prisoners live (slightly better than I calculated before)

[CaptainEd]

Bushindo, that is an improvement, and I agree that HH's solution offers a slightly smaller expectation that 0.95 (I doubt it is as small as 0.9945, but I can't do the math to be sure). The worst case: the first prisoner goes through 50 jars without finding his number, then he is only able to correct 49 jars (he'll wind up putting some garbage number in his own jar). That means it is possible for the second prisoner to have the bad luck of chasing another chain of 50 jars without success. For this to happen, the remaining 50 have to form a chain, with P2's number at the end AND it is the number written on the slip that P1 had to put into his own jar.

The probabilities, as we've seen before, are low: what is the probability of there being two permutation chains of length 50? That's why I think the expected value is still only a tiny bit less than 0.95.

Of course, BellaxPallus offers a marvelous option as well!

edit: once again, HH has typed quicker and thought deeper than I. Once again, I buy his argument. In fact, his probabilities are computed only for the worst case, and are not adjusted by the probability of that case coming to pass (ie, there are two chains of length 50 or one chain of length 100), so I think the actual expectation is a tad higher still.

Edited May 13, 2009 by CaptainEd

[CaptainEd]

Tedious detail: actually, the only way P2 can have a problem is for there to be an initial chain of 100 jars.

I said the only way P2 can fail is if there are two chains of 50 or one chain of 100. I think that's false.

Suppose there are two chains of 50. For simplicity, suppose J1 contains "2", J2 contains "3", and so on up to jar 50 containing "1". P1 wins, and P2 wins similarly.

So two chains of 50 permit everyone to survive.

Suppose one chain of 51 and one of 49. Once again J1=2, J2=3...J50=51, J51=1. Now P1 corrects J2-J50, and puts "51" in J1. Now comes P2, whose number happens to be 100, and suppose J52=53, J53=54...j99=100, j100=52. He starts with j100, and has to run through 49 jars, starting with 52. OK, he gets there on his 49th seek.

So chains of 51,49 permit all but P1 to survive.

The ONLY case where P2 can fail is if there's a chain of 100. Imagine j1=2, j2=3,...j99=100, j100=1.

Now P1 opens J1-j50, and corrects j2-j50, leaving j1=51. Now comes P2 (whose number is 100). He opens 100, sees "1"; opens 1, sees "51", opens 51, sees "52", and so on. So he opens jar (50 + I) on his (I+2) look. So, on his 50th look, he's looking at 98. He, too fails, having corrected the rest of the deck, except for 99 and 100, which now point to each other.

Note, a chain of 99 is not a problem for P2, because that leaves a chain of 1 which he'll skip over without looking at. (In the case above, if j99=99 to begin with, then j98=100, and he succeeds.)

[HoustonHokie]

Bushindo, that is an improvement, and I agree that HH's solution offers a slightly smaller expectation that 0.95 (I doubt it is as small as 0.9945, but I can't do the math to be sure). The worst case: the first prisoner goes through 50 jars without finding his number, then he is only able to correct 49 jars (he'll wind up putting some garbage number in his own jar). That means it is possible for the second prisoner to have the bad luck of chasing another chain of 50 jars without success. For this to happen, the remaining 50 have to form a chain, with P2's number at the end AND it is the number written on the slip that P1 had to put into his own jar.

The probabilities, as we've seen before, are low: what is the probability of there being two permutation chains of length 50? That's why I think the expected value is still only a tiny bit less than 0.95.

Of course, BellaxPallus offers a marvelous option as well!

edit: once again, HH has typed quicker and thought deeper than I. Once again, I buy his argument. In fact, his probabilities are computed only for the worst case, and are not adjusted by the probability of that case coming to pass (ie, there are two chains of length 50 or one chain of length 100), so I think the actual expectation is a tad higher still.

I think you're right about the expectation being slightly higher. I've made the simplistic assumption that all chain lengths have equal probabilities of occuring (i.e., 1, 10, & 100 jar chains each occur 1/100 times, etc.), but I doubt that's the case. I would expect that chains at the high end of the spectrum (80-100 jars, for example), are relatively rare, and chains at the lower end of the spectrum are the most common.

And, really, you're looking at two coincidental probabilities: first, that such a chain exists at all in the random ordering of jars; second, that the specific number you're looking for is part of that chain. Combining the two gives the probability that the slip you want is in a particular length chain. And, while long chains are rare, the probability of being in a long chain, given the existence of a long chain, is relatively high. Conversely, while short chains are common, the probability of being in a particular short chain is relatively low.

There are way too many combinations of additive factors of 100 for me to compute how probable a 100-jar chain is. I'll leave that to the statistical geniuses out there (you know who you are). But I'll say this: the probability of a 100-jar chain is very close to 0. And the probability of prisoner #2 being in the latter half of a 100-jar chain is 50% of very close to 0. So, the probability of prisoner #2 living is halfway between very close to 1 and 1.

Going back to prisoner #1, he lives unless there's a chain longer than 50 and his number is in it. Like I said above, I'm not going to compute the additive factors for 100, but I did for 10. And if I counted right, chains longer than 5 occurred only in only 12 of 37 possibilities, or about 32% of the time. So, if there were 10 prisoners and they got to look in 5 jars, prisoner #1 is saved 68% of the time right off the bat because there's no chain longer than 5 jars for his name to be in. The other 32% is further reduced when you consider that, even if a chain longer than 5 exists, prisoner #1 might not be in it. I get that, in the case of only 10 prisoners, prisoner #1 has a chance of surviving that is almost 75%. Prisoner #2 has an expected survival rate of 98.6%. Those numbers should improve substantially as the number of prisoners increases.

[CaptainEd]

Here's what I learned about the probability of a 100-chain:

Spoiler for from http://www.inference.phy.cam.ac.uk/mackay/...ycles.pdf":

Prob is 1/N that the N jars contain a chain ("cycle" is the right word, apparently) of length N. So, that's not real close to 0, but is certainly just a small fraction of the total number of permutations.

Hey, correct me if I'm wrong, P2 is safe even in a 100-cycle. Given the situation in my post #11, he has looked at his 50 jars: 100, 1, 51-98. He put the contents of 98 (which contains "99") into 100. He didn't find his number (because it's sitting in 99). So, when the warden says, "Where's your nametag?", P2 says, with certainty, "It's in jar 99".

So, the only prisoner who has a chance of death, given HH's proposal, is P1. Regardless of whether P1 finds his number, all other prisoners are safe.

Edited May 13, 2009 by CaptainEd

[bushindo]

I realize that in my first post I was talking about numbers instead of names, but it is easier to deal with numbers and I assume that prisoners with perfect memory would also know everyone else's name and order alphabetically, which they could translate into numbers for purposes of sorting. An interesting twist on this problem would be if the prisoners did not know each others' names, but I won't go there now.

Interestingly, I think CaptainEd's sort and search approach is the optimal solution for the case where the prisoners don't know each others' names. The reason HoustonHokie's strategy gives superior performance is because we are taking advantage of extra information- the fact that each prisoner knows the other 99's names. The sort-and-search approach makes does not use of that piece of information, and thus equivalent to the strategy where the prisoners don't know each other's name.

Some interesting extension. Suppose that each prisoner has limited memory and can only remember the names of 49 other people. Let's say that the night before the game, the prisoners randomly divide into two groups, each with 50 members. Each prisoner then memorizes the names of all members of his group. What is the optimal strategy for this situation and what is the expected number of prisoners saved. I expect it to be bigger than 99.45 ( no one knows each others' names) but less than 99.5 ( each prisoner knows all others' names ).

Edited May 14, 2009 by bushindo

[Guest]

Well, this isn't exactly logic, but i thought id take the direct approach

The prisoners take the 100 jars and throw them at the warden and guards, killing them

[CaptainEd]

Interestingly, I think CaptainEd's sort and search approach is the optimal solution for the case where the prisoners don't know each others' names. The reason HoustonHokie's strategy gives superior performance is because we are taking advantage of extra information- the fact that each prisoner knows the other 99's names. The sort-and-search approach makes does not use of that piece of information, and thus equivalent to the strategy where the prisoners don't know each other's name.

Some interesting extension. Suppose that each prisoner has limited memory and can only remember the names of 49 other people. Let's say that the night before the game, the prisoners randomly divide into two groups, each with 50 members. Each prisoner then memorizes the names of all members of his group. What is the optimal strategy for this situation and what is the expected number of prisoners saved. I expect it to be bigger than 99.45 ( no one knows each others' names) but less than 99.5 ( each prisoner knows all others' names ).

Bushindo, as long as the prisoners are together the previous night, why don't they alphabetize all 100 of them, each learn his/her ordinal number, and THEN divide into two groups. As you say, have each prisoner memorize the names AND ORDINALS of the 50 people in his/her group. (I haven't considered how they should proceed on the day of the big test, but it feels like a more valuable bit of information...)

[HoustonHokie]

Bushindo, as long as the prisoners are together the previous night, why don't they alphabetize all 100 of them, each learn his/her ordinal number, and THEN divide into two groups. As you say, have each prisoner memorize the names AND ORDINALS of the 50 people in his/her group. (I haven't considered how they should proceed on the day of the big test, but it feels like a more valuable bit of information...)

Looks like bushindo was saying the prisoners were limited to 49 bits of information. A name and an ordinal would be one bit each. I agree that it makes sense for them to alphabetize themselves prior to dividing, but I'm not sure how to divide or how beneficial it would be to only know part of the equation. The prisoners could only memorize their own ordinal plus the names and ordinals of 24 others. So, when they got to the jar room, how do they open the jars? Do they go 1-50, but if they come across a name they know that's higher than 50, they open 1-49 plus that jar? Or do they open all the jars matching ordinals they memorized, plus the first 25 others in line? I have no idea how to calculate the odds that names would get put where they belong. Say they know 3 and 6 from memory, and happen to come across 4 & 5 in the initial 50 jars. They could sort 3-6 properly in that case. But if they only came across 4, where would you put it? Presumably you'd want it in 4 or 5 (because it's between 3 & 6), but which? And what do you put in the other jar (4 or 5)? It would have to be something out of order, and that would be a big problem. It almost seems like the extra information is enough to confuse, but not to help. The more I think about it, the more I think you're limited to a sort and search procedure unless you know every name.

Edited May 15, 2009 by HoustonHokie

[Guest]

Lets take another approach.

1. Let us first assign an unique number from 1 to 100 to each of the prisoners and let them stand side by side in a line.

2. Also write the same number in front of them on the floor.

3. Each prisoner will then take a turn to go to the other room and open only one jar of it number. For example 1st prisoner would open only the 1st jar, 2nd prosoner would do the same on 2nd jar and so on.

4. Comes back to the room and stands in front of the prisoner whose name he just found from the jar.

5. At the end they each know which jar has their names.

For example if prisoner 10 is now standing on location 31 then the jar 10 has the name of prisoner#31.