[Guest]

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. After they look inside a jar, they have to put the slip back and look in another jar. Each prisoner will do this alone, and the ones who have finished will not be able to communicate with anyone who is in the process of looking or is waiting to look. After they have each looked in 50 jars, they must attempt to locate their own name. They will be given one chance to do this. If a single person can't find their name, they will all be executed. If they all manage to find their names, then they will be spared. They have been given one night to prepare for the event. Given that they all have perfect memories, find a way to save them all with over a 30% success rate (yes, 30%!). Good luck!

[bonanova]

Each prisoner, acting alone, has a 50% chance of finding his name in a jar.

The other 50% of the time, he has a 2% chance; thus an overall 51% chance of finding his name.

To the 100th power, they get a 5.715018095x10^-30 collective probability of survival.

Which is slightly less than 30%.

Working backward from 30%, the 100th root of .3 is about 0.9880324595.

So if the prisoners work independently, they need to find their names individually with a likelihood of 98.8%.

A daunting task.

Either

1. They can cooperate somehow, or
   
2. They can vastly improve on an individual 51% success rate.
   

I would interpret as forbidden communication the act of placing the 50 inspected jars into alphabetical order by names to guide the choice for the next prisoner of jars to open.

[Guest]

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. After they look inside a jar, they have to put the slip back and look in another jar. Each prisoner will do this alone, and the ones who have finished will not be able to communicate with anyone who is in the process of looking or is waiting to look. After they have each looked in 50 jars, they must attempt to locate their own name. They will be given one chance to do this. If a single person can't find their name, they will all be executed. If they all manage to find their names, then they will be spared. They have been given one night to prepare for the event. Given that they all have perfect memories, find a way to save them all with over a 30% success rate (yes, 30%!). Good luck!

each prisoner looks and then when they see the number, put the lid on upside down then right side up, then upside down etc. until they hit the number in the jar. then each person has a guaranteed chance at survival.

[Guest]

Can prisoners who have already looked in jars talk to each other? If so the chance of success could be 100% every time. If they have perfect memories and can look in 50 jars, by planning ahead two prisoners could know the locations of every name. The best strategy would be to tell each prisoner to look in jars on different sides of the room only or to look in a specific areas. 50% would find their names and the other 50 could just ask the other prisoners. However they must first agree to promise to reveal the correct jar number, though i am sure there would be some betrayal.

Edited May 11, 2009 by Chriswa84

[Guest]

Can prisoners who have already looked in jars talk to each other? If so the chance of success could be 100% every time. If they have perfect memories and can look in 50 jars, by planning ahead two prisoners could know the locations of every name. The best strategy would be to tell each prisoner to look in jars on different sides of the room only or to look in a specific areas. 50% would find their names and the other 50 could just ask the other prisoners. However they must first agree to promise to reveal the correct jar number, though i am sure there would be some betrayal.

http://brainden.com/forum/style_emoticons/default/smile.gif

there probably would be but keep in mind if one gets it wrong they all die so at least in this case honesty would prob be best

[Guest]

1. Would any manipulation of the jars/lids be tolerated by the warden?

2. While it states that the finished prisoners cannot communicate with the others, it does not state that the finished ones cannot communicate amongst themselves. (but that would make this an overly simple problem, so I assume this is not the case, am I correct?)

3. Is there any elimination? In other words, if the first picks properly, will the jar be eliminated from the possibilities for the next prisoner's pick?

[bonanova]

Can prisoners who have already looked in jars talk to each other? If so the chance of success could be 100% every time. If they have perfect memories and can look in 50 jars, by planning ahead two prisoners could know the locations of every name. The best strategy would be to tell each prisoner to look in jars on different sides of the room only or to look in a specific areas. 50% would find their names and the other 50 could just ask the other prisoners. However they must first agree to promise to reveal the correct jar number, though i am sure there would be some betrayal.

It seems the answer is No. The OP says:

the ones who have finished will not be able to communicate with anyone who is in the process of looking or is waiting to look.

But this might be a cleverly worded prohibition that applies [only] for person-to-person communication.

If so, my spoiler suggests a way for subsequent prisoners to have a higher than 51% chance, and there are probably even better strategies.

[Guest]

It seems the answer is No. The OP says:

the ones who have finished will not be able to communicate with anyone who is in the process of looking or is waiting to look.

But this might be a cleverly worded prohibition that applies [only] for person-to-person communication.

If so, my spoiler suggests a way for subsequent prisoners to have a higher than 51% chance, and there are probably even better strategies.

It says they cannot communicate with anyone who has looked but does not say they cannot communicate AFTER they have looked.

[Guest]

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. After they look inside a jar, they have to put the slip back and look in another jar. Each prisoner will do this alone, and the ones who have finished will not be able to communicate with anyone who is in the process of looking or is waiting to look. After they have each looked in 50 jars, they must attempt to locate their own name. They will be given one chance to do this. If a single person can't find their name, they will all be executed. If they all manage to find their names, then they will be spared. They have been given one night to prepare for the event. Given that they all have perfect memories, find a way to save them all with over a 30% success rate (yes, 30%!). Good luck!

it says nowhere in the riddle that you cant move the jars. y not look into the jar place it on the floor after you look into it, in the order that the everyone is lined up. (the first man would be the first jar on the left) so when they get done looking in the jar they get back in the same order they were lined up in to begin with (this assuming they agreed to line up the night before and in what order) then each person has a 100% chance to live.

[Guest]

it says nowhere in the riddle that you cant move the jars. y not look into the jar place it on the floor after you look into it, in the order that the everyone is lined up. (the first man would be the first jar on the left) so when they get done looking in the jar they get back in the same order they were lined up in to begin with (this assuming they agreed to line up the night before and in what order) then each person has a 100% chance to live.

this way there is no communication period and its still accomplished with 100%

[bonanova]

it says nowhere in the riddle that you cant move the jars. y not look into the jar place it on the floor after you look into it, in the order that the everyone is lined up. (the first man would be the first jar on the left) so when they get done looking in the jar they get back in the same order they were lined up in to begin with (this assuming they agreed to line up the night before and in what order) then each person has a 100% chance to live.

The OP [seems to] say the prisoners can't communicate.

If this applies only to speech, then yes, there are nonverbal communicative strategies.

However, your analysis seems wrong.

For example, you have not explained how, if each only looks into 50 jars, the ordering could be complete.

I don't think the OP has clearly stated whether the first prisoner looks into his 51st jar before or after all the prisoners have looked into 50 jars.

The OP says each, which implies to me before.

Although if that's the case, the puzzle seems impossible.

Also, the OP suggests the best collective result is about 30%

[bonanova]

It says they cannot communicate with anyone who has looked but does not say they cannot communicate AFTER they have looked.

You're right. Good point.

[Guest]

Give each prisoner a number 1-100. Now the first prisoner looks in jar number 1, and sees the name, then he goes to the jar that corresponds with the guys name in jar #1. Now the prisoner knows his name is in jar #1. Then he looks in the next jar that corresponds with the name in that jar. If he happens to find his name in a jar that was assigned to another person then everyone bumps down 1 number with the prisoner assigned #1 moving to the highest number left of available jars. Of course the first prisoner would need to find his name in order to continue, but if he does then eventually every name should be revealed by at least the 50th prisoner. With perfect memories it should be easy to keep track of all the shifting numbers and who should be what number and all that. Also if a prisoner is due next and he already knows the jar that has his name, he can reveal 24 other names by opening 48 other jars before picking his jar.

for example "John" goes first and opens jar #1 with "Jakes" name in it. Well the night before Jake was assigned #29, so now John looks in jar #29 to let Jake know he is jar #1. Now whoever is in jar #29 John opens the jar that goes with that name and so on.

Not sure about all that, but I'd give that a good chance at working. But then again I may be overlooking something idk, I hav'nt had my redbull yet.

[Guest]

I believe the prisoners are able to communicate the night before, thats why the warden gives them 1 night to prepare. This is like the black hat white hat prisoner riddle.

[Guest]

Not sure about all that, but I'd give that a good chance at working. But then again I may be overlooking something idk, I hav'nt had my redbull yet.

Give each prisoner a number 1-100. Now the first prisoner looks in jar number 1, and sees the name, then he goes to the jar that corresponds with the guys name in jar #1. Now the prisoner knows his name is in jar #1. Then he looks in the next jar that corresponds with the name in that jar. If he happens to find his name in a jar that was assigned to another person then everyone bumps down 1 number with the prisoner assigned #1 moving to the highest number left of available jars. Of course the first prisoner would need to find his name in order to continue, but if he does then eventually every name should be revealed by at least the 50th prisoner. With perfect memories it should be easy to keep track of all the shifting numbers and who should be what number and all that. Also if a prisoner is due next and he already knows the jar that has his name, he can reveal 24 other names by opening 48 other jars before picking his jar.

for example "John" goes first and opens jar #1 with "Jakes" name in it. Well the night before Jake was assigned #29, so now John looks in jar #29 to let Jake know he is jar #1. Now whoever is in jar #29 John opens the jar that goes with that name and so on.

Quoting the OP: "Each prisoner does this alone" (looking into the 50 jars) ie. the others cannot see him look into the jars, so it would seem your system would fail unless they could communicate the same info in some other non-direct way.

[Guest]

Quoting the OP: "Each prisoner does this alone" (looking into the 50 jars) ie. the others cannot see him look into the jars, so it would seem your system would fail unless they could communicate the same info in some other non-direct way.

The way it was written he said they could'nt communicate with the prisoner who is looking, which to me meant that they would have been able to if they wanted to, and thats what made me think they were in view of the prisoner currently looking, otherwise he should have just said they are in separate rooms or something.

[Guest]

Without any communication in any form (except during the night of preparation), the prisoners have a way to correlate their choices, thus obtain an overall chance much larger than the 100th power of the individual chance.

By no communication in any form, I mean that the room with the jar is put by the warden to its initial state between each prisoner's turn. Also the waiting room, the jar's room, and the room after they opened the jars are 3 independent rooms.

And no cellphone...

To simplify, let's say the prisoners names are P1, P2, ... P100 (this is equivalent to the original problem, because they can memorize their number during the night of preparation). And the jars are numeroted J1, J2,... J100.

The strategy is the following: prisonner P1 open the jar J1 and finds the name of P57. Then he opens the jar J57 and finds the name P23. Then he opens the jar J23, etc... The process is repeated the 51th allowed times, or when he finds is name. If he found his name, it's ok for him. If not, everybody dies.

Prisonner P2 do exactly the same thing, starting with the jar J2.

Why is it much better than randomly picking 51 jars ?

Let's make a reasoning with 6 prisoners, 6 jars and 4 (6/2+1 as an analogy to 100/2+1=51) allowed openings. When the names are distributed randomly in the jars, some structure appears. For example if the distribution is : J1-P4 ; J2-P6 ; J3-P5 ; J4-P2 ; J5-P3 ; J6-P1, then you observe two cycles:

1->4->2->6->1 (cycle with 4 elements)

and

3->5->3 (cycle with 2 elements)

In this case the prisoners P1, P2, P4 and P6 will all find their names after 4 openings. The prisoners P3 and P5 will find their names after 2 openings.

In this example, the prisoners are spared.

But if the distribution was J1-P5 ; J2-P6 ; J3-P3 ; J4-P1 ; J5-P2 ; J6-P4, then there are two cycles :

1->5->2->6->4->1 (cycle with 5 elements)

and

3->3 (cycle with 1 element)

In this case, the prisoner P3 will be the only one to find his name. All the others would have require 5 opening to find theirs.

So, back to our 100 prisonners, with this strategy, the probability of everybody to be spared is the same as the probability of not having a cycle with more than 51 elements in the distribution. This I don't see how to calculate, but I wouldn't be surprised if it was around 30%...

Edited May 11, 2009 by Findus

[Guest]

Without any communication in any form (except during the night of preparation), the prisoners have a way to correlate their choices, thus obtain an overall chance much larger than the 100th power of the individual chance.

By no communication in any form, I mean that the room with the jar is put by the warden to its initial state between each prisoner's turn.

To simplify, let's say the prisoners names are P1, P2, ... P100 (this is equivalent to the original problem, because they can memorize their number during the night of preparation). And the jars are numeroted J1, J2,... J100.

The strategy is the following: prisonner P1 open the jar J1 and finds the name of P57. Then he opens the jar J57 and finds the name P23. Then he opens the jar J23, etc... The process is repeated the 51th allowed times, or when he finds is name. If he found his name, it's ok for him. If not, everybody dies.

Prisonner P2 do exactly the same thing, starting with the jar J2.

Why is it much better than randomly picking 51 jars ?

Let's make a reasoning with 6 prisoners, 6 jars and 4 (6/2+1 as an analogy to 100/2+1=51) allowed openings. When the names are distributed randomly in the jars, some structure appears. For example if the distribution is : J1-N4 ; J2-N6 ; J3-N5 ; J4-N2 ; J5-N3 ; J6-N1, then you observe two cycles:

1->4->2->6->1 (cycle with 4 elements)

and

3->5->3 (cycle with 2 elements)

In this case the prisoners P1, P2, P4 and P6 will all find their names after 4 openings. The prisoners P3 and P5 will find their names after 2 openings.

In this example, the prisoners are spared.

But if the distribution was J1-N5 ; J2-N6 ; J3-N3 ; J4-N1 ; J5-N2 ; J6-N4, then there are two cycles :

1->5->2->6->4->1 (cycle with 5 elements)

and

3->3 (cycle with 1 element)

In this case, the prisoner P3 will be the only one to find his name. All the others would have require 5 opening to find theirs.

So, back to our 100 prisonners, with this strategy, the probability of everybody to be spared is the same as the probability of not having a cycle with more than 51 elements in the distribution. This I don't see how to calculate, but I wouldn't be surprised if it was around 30%...

I agree, thats how I was trying to put it. You seem to be more Mathematically ligual than me

[bonanova]

Without any communication in any form (except during the night of preparation), the prisoners have a way to correlate their choices, thus obtain an overall chance much larger than the 100th power of the individual chance.

By no communication in any form, I mean that the room with the jar is put by the warden to its initial state between each prisoner's turn. Also the waiting room, the jar's room, and the room after they opened the jars are 3 independent rooms.

And no cellphone...

To simplify, let's say the prisoners names are P1, P2, ... P100 (this is equivalent to the original problem, because they can memorize their number during the night of preparation). And the jars are numeroted J1, J2,... J100.

The strategy is the following: prisonner P1 open the jar J1 and finds the name of P57. Then he opens the jar J57 and finds the name P23. Then he opens the jar J23, etc... The process is repeated the 51th allowed times, or when he finds is name. If he found his name, it's ok for him. If not, everybody dies.

Prisonner P2 do exactly the same thing, starting with the jar J2.

Why is it much better than randomly picking 51 jars ?

Let's make a reasoning with 6 prisoners, 6 jars and 4 (6/2+1 as an analogy to 100/2+1=51) allowed openings. When the names are distributed randomly in the jars, some structure appears. For example if the distribution is : J1-P4 ; J2-P6 ; J3-P5 ; J4-P2 ; J5-P3 ; J6-P1, then you observe two cycles:

1->4->2->6->1 (cycle with 4 elements)

and

3->5->3 (cycle with 2 elements)

In this case the prisoners P1, P2, P4 and P6 will all find their names after 4 openings. The prisoners P3 and P5 will find their names after 2 openings.

In this example, the prisoners are spared.

But if the distribution was J1-P5 ; J2-P6 ; J3-P3 ; J4-P1 ; J5-P2 ; J6-P4, then there are two cycles :

1->5->2->6->4->1 (cycle with 5 elements)

and

3->3 (cycle with 1 element)

In this case, the prisoner P3 will be the only one to find his name. All the others would have require 5 opening to find theirs.

So, back to our 100 prisonners, with this strategy, the probability of everybody to be spared is the same as the probability of not having a cycle with more than 51 elements in the distribution. This I don't see how to calculate, but I wouldn't be surprised if it was around 30%...

I believe that's it.

Someone will come up with a calculation of the cycle probability.

Nice.

[Guest]

Easy. They all put their slips of paper in a single jar. They open one jar and replace their slip of paper in another jar. They all replace their slips of paper in the same jar.

[soop]

Easy. They all put their slips of paper in a single jar. They open one jar and replace their slip of paper in another jar. They all replace their slips of paper in the same jar.

I like it!

If a prisoner finds his name, he turns the jar upside down and remembers the number. THen the choice is whittled down for the rest. This should give a greater than 30% probability. Then, when 50 of the jars are gone, the jars are arranged in alphabetical order for anyone who didn't get theirs.

[bonanova]

I like it!

If a prisoner finds his name, he turns the jar upside down and remembers the number. THen the choice is whittled down for the rest. This should give a greater than 30% probability. Then, when 50 of the jars are gone, the jars are arranged in alphabetical order for anyone who didn't get theirs.

The first has 51% chance. The second has about the same.

That puts them collectively below 30% even if the last 18 are certain [they're not].

[plasmid]

I have some silly questions about using chains of permutations to solve the puzzle. The prisoners have their names (instead of prisoner numbers) written on a piece of paper, right? So are you arranging all the prisoners in alphabetical order and assigning each of them a number from 1 to 100, then treating that alphabetical ordering like a prisoner number? Sounds reasonable. But what if you ordered the prisoners not alphabetically but by age? Their numbers might be different. Would the strategy work just as effectively? Presumably so; neither method of ordering the prisoners seems inherently superior. How about if you ordered the prisoners randomly to assign a prisoner number? Equally effective I would think.

Now, suppose you've randomly assigned each prisoner his number. Prisoner #1 goes out and opens jar #1 and sees a slip of paper. If prisoner #1 doesn't find his own name but finds the name "Joe Brown", he would still have an equal probability of opening each of the remaining jars because Joe Brown would be just as likely to have been assigned to prisoner #8 as prisoner #61.

So, are we really sure that this is better than opening jars randomly?

[CaptainEd]

Yes, look at Post 18 by James8421. If you use the name/number tag as a pointer to another jar, you are tracing the permutation cycle that your jar is in. As long as your cycle length <= 50, you're good. Furthermore, everybody in that cycle is also good. And if all cycles are shorter than 51, you're all good.

Whereas, if you looked at 50 random jars, you might succeed and yet another person might choose a different 50, and not find theirs. This is an elaborate form of the automobile dilemma: it doesn't matter which side of the road you drive on, right or left, but if everybody chooses at random, somebody will probably get hurt. But if everybody obeys the same convention (whichever it happens to be), they won't get hurt.

As Bonanova says, we just need the calculation of fraction of permutations of N that have a cycle longer than 50.

Oh, I found that.

Spoiler for Pointer to calculation of probability of a cycle longer than

50.:

http://www.inference.phy.cam.ac.uk/mackay/itila/cycles.pdf

He calculates it, for a set of 100 jars at 0.69. So probability that everybody finds their jar is 0.31. Presumably the OP has read this article (or written it...)

Edited May 13, 2009 by CaptainEd

[Guest]

Another solution:

First, The prisoners decide the order in which they will look into the jars.

Second, they divide the room of jars into 4 quadrants (see picture attached). The prisoner who sees the jars stands in the quadrant of the room depending on which 50 jars he looks into (1 to 50 or 51 to 100) and whether he finds the name of the next prisoner in those jars.

Explanation:

Bottom left means he saw the 1 to 50 numbered jars and did not find the name of the next prisoner

Bottom right means he saw the 1 to 50 numbered jars and found the name of the next prisoner

Top left means he saw the 51 to 100 numbered jars and did not find the name of the next prisoner

Top right means he saw the 51 to 100 numbered jars and found the name of the next prisoner

Third, the next prisoner (N+1) who comes sees where the previous prisoner (N) is standing and looks in the jars correspondingly. For example, he sees the N standing in the bottom left of the room means N saw jars 1 to 50 and did not find N+1's name. So, N+1 looks into jars 51 to 100 and is sure to find his name.

This way all but the first prisoner would be sure to find their names in the jars. The first prisoner would have a 50% probability of finding his name. So the overall probability of escaping would be 50%.

Edited May 14, 2009 by DeeGee

[Guest]

The prisoners decide to memorize the order of their names alphabetically (since they have perfect memories)

The first prisoner has the most important job:

- He marks 100 spaces on the floor/table/ etc.

- He looks into the first 50 jars and places the names in their appropriate space(s)

-He's the only prisoner that may not have found his name

The second prisoner looks into the remaining jars from the 50-100 section and places the rest of the names in their appropriate space, also showing which is his name. The remaining 98 prisoners simply grab the jar in the appropriate space and pull their name out.

50% probability...