[bushindo]

40 prisoners are on the deathrow. The warden gives them a chance to live. He puts 100 empty jars into room A and randomly puts 25 balls under the 100 jars. Each jar is either empty or contains 1 ball. In the other room, call it room B, the warden puts 100 empty jars, and a stack of 25 balls.

The warden then divides the group of 40 into two groups of 39 and 1. The group of 39 he puts into room A. The last prisoner goes into room B.

Each prisoner from room A will take turn looking under the entire 100 jars, but can not move or rearrange the contents. He then can go to room B and say one of four possible words to the prisoner. The 4 possible words are Brain, Teasers, Forum, Rules. Assume he can not convey any other information besides that word (so no facial expression, tone, body language, hand gestures, etc. ). The prisoner in room B will then have to reconstruct the permutation of the balls in room A.

If the prisoner in room B can successfully reconstruct the permutation in room A after the 39 turns, all 40 will live. Otherwise they will die.

The night before, the warden tells the prisoners this scheme, so the prisoners know that there will be exactly 25 balls under the 100 jars. They have 1 night to discuss a strategy.

1) Is there a guaranteed strategy for survival? If so, describe it.

Edited May 23, 2009 by bushindo

[Guest]

i think i have it.

they can choose to not say any of the 4 words. otherwise, this wont work.

3 of the words describe 2 cups at a time, and the 4th word and silence describe 3 cups at a time.

brain = ball - no ball

teaser = no ball - ball

forum = ball - ball

rules = no ball - no ball - ball

silence = no ball - no ball - no ball

depends where the balls are distributed on how many it will take but 39 is more than enough no matter how you slice it.

[Guest]

im wrong heres how.

if 1 out of each 5 cups has 1 ball for the first 90 cups that would leave you with 3 prisoners and 10 cups containing 7 balls. not enough prisoners to deduce which ones do and dont have a ball.

[Guest]

It was much easier before he edited it. He had 50 prisoners in room A. So all they would have to do is take 2 jars at a time and you get 4 possible combinations, then just attach one of the 4 words to each of the 4 combos. But it makes it much harder now with only 39 prisoners. So far the smallest number of jars per prisoners I have found is, 34 take 2 jars each for the first 68 jars, 1 takes 8 jars for76 jars, then 4 take 6 jars each for 100 jars. For the first 68 jars you could easily incorperate the 4 words, but after that, the combinations increase, and therefore more words would be needed. And thats where I'm stuck! However perhaps the four that take the 6 jars could say the words in a specific order to the 1 prisoner in room B, and have it represent the four groups of 6 jars.

But the 1 with 8 jars would be in a pickle. I'm curious to see the answer.

[Guest]

i tried bitwise and dont think it can work (each bit represents a jar)

each guy would have to represent 3 jars with 5 words he can only represent 5 combinations when there is 9 combos

if you combine two to try and-ing or-ing adding, not-ing or anything even if you give them different numbers (infinite intelligence they can remember) you can only represent 25 combinations of jars when you have to represent a little more then five jars or32 combos

if you try the same thing with 3 people you can represent 125 combos but have to be able to represent 8 jars and do something even bigger and it gets worse from there

so thats where i am

im goin with no until another idea happens

[Guest]

It is Possible if you can vary the speed of the word being said, or change the word to past tense etc

But if each word has to be conveyed in a monotone voice at a set speed then i don't think it is possible.

Then again I have been known to be wrong ... alot hahaha.

... just quickly how do I do the spoiler thing? my browser doesn't like the "insert spoiler" button.

Edited May 23, 2009 by Kyiela Castillo

[Guest]

CaptainEd will probably think of a way.....Till then I say you could'nt gaurantee there lives will be spared.

Edited May 23, 2009 by James8421

[plainglazed]

Oops, already see the error of my method. Still thinking.

Edited May 23, 2009 by plainglazed

[Guest]

It is Possible if you can vary the speed of the word being said, or change the word to past tense etc

But if each word has to be conveyed in a monotone voice at a set speed then i don't think it is possible.

Then again I have been known to be wrong ... alot hahaha.

... just quickly how do I do the spoiler thing? my browser doesn't like the "insert spoiler" button.

Your not allowed to alter your voice or try to multiply the four words by trying different ways of saying each word.

not sure why it don't work

.

[plainglazed]

Oops, already see the error of my method. Still thinking.

Perfect memory was not stated nor what is the least number of prisoners that can define all 100 jars in room B so to keep it simple: Yes, two prisoners can describe 16 scenerios or the definition of what is under 8 jars using four words (actually 25 scenarios if silence is an option). Am thinking I'm probably missing something yet in the outline of the puzzle tho.

[Guest]

Perfect memory was not stated nor what is the least number of prisoners that can define all 100 jars in room B so to keep it simple: Yes, two prisoners can describe 16 scenerios or the definition of what is under 8 jars using four words (actually 25 scenarios if silence is an option). Am thinking I'm probably missing something yet in the outline of the puzzle tho.

only 1 prisoner is in room B, and he has to replicate the permutation of the 100 jars in room A. I never thought of silence as an option, but I believe you'd run outta prisoners(only 39 can speak)

Edited May 23, 2009 by James8421

[Guest]

It can be done with only 34 of the 39 from room A.

Each prisoner will be required to remember to contents of only 3 consecutive jars. Starting from the first in line (and supposedly first to report his findings), he must remember the contents of jars 1-3. Sencond in line remembers 4-6, and so on. 33 prisoners will remember he contents of 99 jars, the 34th, only one jar.

In room B, they report heir finding by the corresponding code word:

Brain = Empty, Empty, Empty

Teaser = Ball, Empty, Empty

Forum = Empty, Ball, Empty

Rule = Empty, Empty, Ball

The prisoner in room B can reconstruct as they come in.

[Guest]

It can be done with only 34 of the 39 from room A.

Each prisoner will be required to remember to contents of only 3 consecutive jars. Starting from the first in line (and supposedly first to report his findings), he must remember the contents of jars 1-3. Sencond in line remembers 4-6, and so on. 33 prisoners will remember he contents of 99 jars, the 34th, only one jar.

In room B, they report heir finding by the corresponding code word:

Brain = Empty, Empty, Empty

Teaser = Ball, Empty, Empty

Forum = Empty, Ball, Empty

Rule = Empty, Empty, Ball

The prisoner in room B can reconstruct as they come in.

What would you say if it is Ball, Ball, Empty or Ball, Ball, Ball or Ball, Empty, Ball or Empty, Ball, Ball?

[Guest]

What if there are two or three balls in a row? How does it work then? Why not Brain, 1st cup with ball and the next prisoner goes from there and then Teaser one skip and second cup has ball, next goes from there, Forum two skips, and Rule all three skips. So each prisoner just goes from one ball to the next.

[Guest]

you could increase the amount of options for words simply by delaying the answer ... as in *WALK INTO ROOM B wait a few seconds then answer, that would give you 2 versions of each word (walk in and say it straight away, and walk in and wait a few seconds) There is nothing in the OP saying the prisoner had to answer as soon as the door opened ...

Sorry I prefer work arounds rather then the solution.

[Guest]

First post, forgive me but I don't know how to hide the solution.

Solution(or one possible solution): There are 75 empty jars (far outweighing the full jars) so most combinations of jars will be predominately empty. The prisoners from room A have five options to transfer information- silence, brain, teasers, forum, rules. These five options should represent the number of consecutive empty jars 0-4.

prisoner 1 looks at the first jar: if there is a ball he moves to room B and is silent. If it is empty he looks at jar 2. If jar 2 has a ball he goes into room B and says Brain. If empty he looks at jar three, etc.

If at any point there are consecutive balls the next prisoner in line will simply come in and say nothing. if there is 3 consecutive balls the the next prisoner will be silent as well, etc

There are certainly permutations that will exhaust the number of prisoners before the 100 jars have been defined, but in each such permutation all 25 balls have been used early and the 40th prisoner (in room B) can deduct that the remaining jars are empty (the balls are gone anyway).

~Brad

[Guest]

I haven't proved this logically, but I think that this strategy will guarantee safety, if the prisoners know beforehand the configuration of the cups and can therefore assign a serial number to each one......

If we use pairs of prisoners to give numerical values to the gaps between balls, it can be done easily, I think. For example,

BB = no gap

BT = 1 gap

BF = 2 gaps

BR = 3 gaps

and so on until..

RF = 14 gaps

RR = 15 or more gaps.

For all except the last message, the prisoner counts the gaps and places a ball under the next cup. For the last message, he counts the gap of 15, but doesn't place a ball.

The 39th prisoner's message won't be needed. 19 message pairs should be more than adequate to cover the 75 gaps.

:huh:

[Guest]

Spoiler for last chance before my brain explodes..:

I''l try to explain it the best way I can(bear with me)

If they do it in groups of 3 jars, there is 8 combinations. Number each combo 1-8. Now assign each word with two numbers each:

Brain=combo1 and combo5

Teaser=2 6

Forum=3 7

Rule=4 8

Assign 16 men to represent the low combo for each word, and 16 to represent the high.Take 5 of the remaing prisoners to be "switchers".In case you run out of the low/high guys,which could only happen after 16 guys, then have a switcher jump in and assign him a word that signals a switch in how the next prisoners are going to be represented, keep that way until another switcher pops in. I believe out of 5 switchers you will be able to establish 96 jars to prisoner B. Now the night before you assign 2 prisoners to take care of the last 4 jars=2 jars each=4 combos, assign the words accordingly. And hey it might be possible.

There is one part i'm not 100% about. But I think that could work. It seems confusing but thats just the way I put it. If someone knows of a formula or an easier way of putting it, feel free.

Edited May 23, 2009 by James8421

[plainglazed]

I haven't proved this logically, but I think that this strategy will guarantee safety, if the prisoners know beforehand the configuration of the cups and can therefore assign a serial number to each one......

If we use pairs of prisoners to give numerical values to the gaps between balls, it can be done easily, I think. For example,

BB = no gap

BT = 1 gap

BF = 2 gaps

BR = 3 gaps

and so on until..

RF = 14 gaps

RR = 15 or more gaps.

For all except the last message, the prisoner counts the gaps and places a ball under the next cup. For the last message, he counts the gap of 15, but doesn't place a ball.

The 39th prisoner's message won't be needed. 19 message pairs should be more than adequate to cover the 75 gaps.

:huh:

Started off this post in support of your answer

what if the least efficient scenario existed where the first 23 jars had balls and so did the last 2 jars.The first 19 pairs would have placed balls under the first 19 jars and the last guy would have to define where six balls were among the remaining 81 jars.

Edited May 23, 2009 by plainglazed

[Guest]

I haven't proved this logically, but I think that this strategy will guarantee safety, if the prisoners know beforehand the configuration of the cups and can therefore assign a serial number to each one......

If we use pairs of prisoners to give numerical values to the gaps between balls, it can be done easily, I think. For example,

BB = no gap

BT = 1 gap

BF = 2 gaps

BR = 3 gaps

and so on until..

RF = 14 gaps

RR = 15 or more gaps.

For all except the last message, the prisoner counts the gaps and places a ball under the next cup. For the last message, he counts the gap of 15, but doesn't place a ball.

The 39th prisoner's message won't be needed. 19 message pairs should be more than adequate to cover the 75 gaps.

I see what your getting at here, but what if you get 15 balls in a row? It would take 30 prisoners to tell Prisoner B that there are no gaps. It seems the more gaps you have in between, you cover more ground, but you could have 10 balls and 2 gaps 10 more balls and 3 gaps and 5 balls.Say for example that is how it starts out, it would take 20 prisoners(P) to say there is no gaps within 10 balls, 2P to say there are 2 gaps then a ball, 18P to say there are no gaps between 9 balls, 2P to say there are 3 gaps then a ball, and 8P to say there are no gaps between 4 balls.=50P and only jars 1-30. Or am I missing your concept?

[Guest]

Whoops, I just realised that my earlier solution won't work. It won't find all 25 balls.

Here's another try, with a similar idea.

If we code the pairs of replies to configure the next 4 cups, that give 18 pairs if replies covering 72 cups.

For example,

BT = ball xxx

BF = x ball xx

BR = xx ball x .......

There are only 16 permutations for the 4 holes. The last messenger's message will be different, depending on the number of balls left. It's quite easy to code it, but a bit tedious to write. This should work.

:) :)

[plainglazed]

If they work in sets of three with the first prisoner stating if there are 0, 1, >1, or 15 balls in the next 15 cups. If they says "0" or "15", those 15 jars are defined and the next prisoner comes in and answers similarly. Otherwise the next pair of prisoners indicate the gap before the next ball. Am working on proving this always works but think some kind of combination of indicating both the number of balls and gaps in between balls can yield a solution.

[Guest]

Suppose the prisoners come up with a code. Using the four words to represent the numbers 1, 2, 3, 4. Using this simple code plus the option of silence (itself a code), each prisoner will report the existence of a ball in a jar or no ball in four jars thus accounting for as many as four empty jars (silence) or the presence of one ball in one of the four jars he examined, coded numbers 1 or 2 or 3 or 4. Lets look at an example. First prisoner finds no balls in jars 1 - 4. He reports nothing but his silence. Code means first four jars are empty. If he found a ball in the first jar, he'd report a one. The next prisoner would understand that the one was reported and would know his responsibility was the next four jars. And so on. First prisoner's work is done. Second prisoner also knows the strategy. He examines the first four jars, understands what the first prisoner has reported and knows that he now has to report on the next four jars. He finds a ball in the third jar and the fourth jar. He will report the number 3. He knows that the next fellow will understand that he reported the three and will in turn report the next jar as a 1. When there are four empty jars they will be reported as a null, or silence. So, with five reporting options you can proceed through the jars until you've identified all twenty-five balls. It is up to the fortieth prisoner to keep track of the numbering strategy. Remember, for example, that for three balls in consecutive jars, the last two would be reported as ones.

[Guest]

this is a hack but a fairly easy way would be each prisoner remembers the location of one ball then takes 1 step for first jar, 2 for second etc until he reaches his remembered location, then say the word brains in a zombie fashion because its cooler that way. after the first 25 the person should know the location of all balls in the permutation.

trying to do it the real way although i havent come up with a solution yet

perhaps trying to work at it from both sides at the same time?

so the even numbered prisoners start from the begining of the permutation and the odds form the end.

I'm thinking that might help avoid the issue of 19 balls followed by a massive gap. something like

each word means either

ball

skip 1

skip 2

skip 4

skip 8

and by working from each side you can limit (I think) the effectiveness of clustering balls then huge gap then a few balls interspersed but i could be wrong.

[Guest]

each prisoner goes in and looks under 5 of the 100 jars that are right next to eachother. the next prisoner will open five but the first two will b two that the previous prisoner just opened. each prisoner wil eather say a word that means:

1 ball

2 balls

3 balls

4 balls

or he won't say anything, meaning there is either 5 balls or 0. if the prisoner said nothing, the next prisoner will easily know if it was 5 or 0 because the 1st two he picks up will eather have 2 or 0.

if they do this and i think they will be able to figure out were alll the balls are. and they will have 7 prisoners left over to check any mistakes.

[Guest]

There is one part i'm not 100% about. But I think that could work. It seems confusing but thats just the way I put it. If someone knows of a formula or an easier way of putting it, feel free.

I''l try to explain it the best way I can(bear with me)

If they do it in groups of 3 jars, there is 8 combinations. Number each combo 1-8. Now assign each word with two numbers each:

Brain=combo1 and combo5

Teaser=2 6

Forum=3 7

Rule=4 8

Assign 16 men to represent the low combo for each word, and 16 to represent the high.(e.g. say Ted is a low number guy, if he says Forum, Prisoner B knows the three jar combo is the combo #3 and arranges accordingly).Take 5 of the remaing prisoners to be "switchers".In case you run out of the low/high guys,which could only happen after 16 guys, then have a switcher jump in and assign him any predetermined word that signals a switch in how the next prisoners are going to be represented, keep that way until another switcher pops in. I believe out of 5 switchers you will be able to establish 96 jars to prisoner B( I wrote this trying to satisfy any number of balls placed randomly in 100 jars, then later realized theres only 25, so it makes it even easier, you may not need the switcher guys at all). Now the night before you assign 2 prisoners to take care of the last 4 jars=2 jars each=4 combos, assign the 4 combos to the 4 words. And hey it might be possible.

This is an edited version with a couple examples, and hopefully better to understand what I'm trying to say. Also when I say Prisoner B, I mean the prisoner in room B.