[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 hope i got the answer... can anyone crosscheck...

First Prisoner comes and says

Brain First Ten Bottles have Balls in a sequence

Teaser There is no ball in first 10 Bottles

Forum Ball in first bottle (this implies there is no sequence in which balls are put)

Rules Ball in second bottle (this implies there is no sequence in which balls are put)

Silence Ball not in sequence or in first or second bottle but is / are in first 10

IF BRAIN (i.e. sequence in first 10 balls)

Second Prisoner comes and says

Brain = sequence of 1 (all 10 bottles have a ball)

Teaser = sequence of 2 (every alternate bottle has a ball)

Forum = Sequence of 3 (every third bottle has a ball)

Rules = Sequence of 4 (every fourth bottle has a ball)

Silence = Sequence of 5 (every fifth bottle has a ball)

Third Prisoner comes and says from where the sequence starts

Brain = 1st Bottle

Teaser = 2nd Bottle

Forum = 3rd Bottle

Rules = 4th Bottle

Silence = 5th Bottle

Hence, 3 Persons clarify first 10 bottles and so on...

If TEASER then second prisoner will come and repeat the same as first one for next 10 balls

If there is no sequence / ball randomly in first 10 bottles,

If ball in first or second bottle, the second prisoner will reveal position of next ball from that bottle

Second Prisoner says

Brain = Ball in 1st from last bottle

Teaser = Ball in 2nd from last bottle

Forum = Ball in 3rd from last bottle

Rules = Ball in 4th from last bottle

Silence = Ball not in 1st to 4th from last bottle

and so on...

If ball not in first or second bottle, the persons will reveal for next 4 bottles until the ball is found

[Guest]

Interesting concept, but assume that you are forced to say one of the four words given. Silence was not supposed to be used as a fifth indicator to Prisoner B.

[bushindo]

I hope i got the answer... can anyone crosscheck...

First Prisoner comes and says

Brain First Ten Bottles have Balls in a sequence

Teaser There is no ball in first 10 Bottles

Forum Ball in first bottle (this implies there is no sequence in which balls are put)

Rules Ball in second bottle (this implies there is no sequence in which balls are put)

Silence Ball not in sequence or in first or second bottle but is / are in first 10

IF BRAIN (i.e. sequence in first 10 balls)

Second Prisoner comes and says

Brain = sequence of 1 (all 10 bottles have a ball)

Teaser = sequence of 2 (every alternate bottle has a ball)

Forum = Sequence of 3 (every third bottle has a ball)

Rules = Sequence of 4 (every fourth bottle has a ball)

Silence = Sequence of 5 (every fifth bottle has a ball)

Third Prisoner comes and says from where the sequence starts

Brain = 1st Bottle

Teaser = 2nd Bottle

Forum = 3rd Bottle

Rules = 4th Bottle

Silence = 5th Bottle

Hence, 3 Persons clarify first 10 bottles and so on...

If TEASER then second prisoner will come and repeat the same as first one for next 10 balls

If there is no sequence / ball randomly in first 10 bottles,

If ball in first or second bottle, the second prisoner will reveal position of next ball from that bottle

Second Prisoner says

Brain = Ball in 1st from last bottle

Teaser = Ball in 2nd from last bottle

Forum = Ball in 3rd from last bottle

Rules = Ball in 4th from last bottle

Silence = Ball not in 1st to 4th from last bottle

and so on...

If ball not in first or second bottle, the persons will reveal for next 4 bottles until the ball is found

Interesting concept. This may very well work, with some refining on the details. This is a reasonable compression scheme, and since having 39 prisoners transmitting 5 bits of information each is equivalent to having a 90-digit binary string (compared to a 100-digit binary string we are supposed to encode), this may work a a reasonable number of cases.

[Guest]

I hope i got the answer... can anyone crosscheck...

First Prisoner comes and says

Brain First Ten Bottles have Balls in a sequence

Teaser There is no ball in first 10 Bottles

Forum Ball in first bottle (this implies there is no sequence in which balls are put)

Rules Ball in second bottle (this implies there is no sequence in which balls are put)

Silence Ball not in sequence or in first or second bottle but is / are in first 10

IF BRAIN (i.e. sequence in first 10 balls)

Second Prisoner comes and says

Brain = sequence of 1 (all 10 bottles have a ball)

Teaser = sequence of 2 (every alternate bottle has a ball)

Forum = Sequence of 3 (every third bottle has a ball)

Rules = Sequence of 4 (every fourth bottle has a ball)

Silence = Sequence of 5 (every fifth bottle has a ball)

Third Prisoner comes and says from where the sequence starts

Brain = 1st Bottle

Teaser = 2nd Bottle

Forum = 3rd Bottle

Rules = 4th Bottle

Silence = 5th Bottle

Hence, 3 Persons clarify first 10 bottles and so on...

If TEASER then second prisoner will come and repeat the same as first one for next 10 balls

If there is no sequence / ball randomly in first 10 bottles,

If ball in first or second bottle, the second prisoner will reveal position of next ball from that bottle

Second Prisoner says

Brain = Ball in 1st from last bottle

Teaser = Ball in 2nd from last bottle

Forum = Ball in 3rd from last bottle

Rules = Ball in 4th from last bottle

Silence = Ball not in 1st to 4th from last bottle

and so on...

If ball not in first or second bottle, the persons will reveal for next 4 bottles until the ball is found

Can you give me an example? I'll give you the first ten jars, and you tell me what the 3 prisoners would say. That would help me see how your solution works.

B=ball N=noball

N,N,B,N,B,B,B,N,B,B

[Guest]

Can you give me an example? I'll give you the first ten jars, and you tell me what the 3 prisoners would say. That would help me see how your solution works.

B=ball N=noball

N,N,B,N,B,B,B,N,B,B

Following will be the reply for given sequence (it takes seven people for these 10 but it will reveal 6 balls that means there will be only 19 balls to be revealed by next ones...

1 Silence

2 Brain

3 Teaser

4 Brain

5 Brain

6 Teaser

7 Brain

Again, possible only if silence is an option...

[Guest]

Following will be the reply for given sequence (it takes seven people for these 10 but it will reveal 6 balls that means there will be only 19 balls to be revealed by next ones...

1 Silence

2 Brain

3 Teaser

4 Brain

5 Brain

6 Teaser

7 Brain

Again, possible only if silence is an option...

Ok thanks. I still got lost. Don't worry about me tho, I can be slow at times.

as for the silence part, in the original post, it was intented for the prisoners to only have 4 ways of conveying their information. However, bushindo posted later that, that was his intentions, but said figure it out either way. The problem I have for using silence is a). You get a 5th way of passing on information (which defeats the purpose of saying you only get 4 words), and b). If you use silence as an option, why not use both at the same time? e.g.: when a prisoner walks into room B, they could both start counting in their head, and after a certain number of seconds go by Prisoner A says a word, the number of seconds before the word can represent a certain combination of a specific number of jars(determined the night before). Then you would only need 1 word. 33 prisoners taking 3 jars each with 8 possible combinations, would mean they would only need to be silent for a maximum of 8 seconds before saying the word. Noone would need to come to prisoner B for the last jar, because he would know where all the balls are, if he used 24 then that means a ball goes in jar 100, if he used all 25, then obviously jar 100 would be empty.

Clever approach either way tho. I would hate to be prisoner B tho.

[Guest]

That is what came to my mind at first place. I thought of counting number of steps after entering to determine no of bottles empty before the one in which ball is. Then it won't matter what is spoken.... Just 25 persons will disclose the position...

But then, it would be too easy to be a puzzle...

[CaptainEd]

Thats where I was stuck in my original post on it, but all in all they would still need to communicate with each other (the way I showed)

So what would you say to the original question? Indeed your method works, but who , on death row, is going to calculate that? But I also suppose that it seems to be a gauranteed scenario. Assuming they all know how to calculate that, and have the means to do so, I'll buy into that method. For now. I hav'nt seen CaptnED take a swing at it yet tho....

CaptainEd is quietly reading and learning from you guys. I'm clueless. I didn't even understand plasmid's solution, until bushindo gave it his stamp of approval. I'll feel satisfied once I understand it thoroughly.