[bushindo]

55 prisoners are on the deathrow. The warden gives them a chance to live. He puts 100 empty jars into room A and randomly puts 10 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 10 balls.

The warden then divides the group of 55 into two groups of 54 and 1. The group of 54 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 must say one of two possible words to the prisoner there. The 2 possible words are Lakers and Rule. Assume he can not convey any other information besides that word (so no facial expression, tone, body language, hand gestures, etc. ). Any attempt to convey extra information like remaining silent, concatenating words, or walking a certain number of paces before stopping in room B will get all prisoners killed immediately. 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 54 turns, all 55 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 10 balls under the 100 jars. They have 1 night to discuss a strategy. They are not allowed to bring any mechanical computational aid to the game (yes, abacus are out too). Assume that each prisoner has the mental computational skills of a reasonable average person.

1) What strategy would give the prisoners the best chance to live? Describe the strategy.

[soop]

Personally, I'd probably try to escape beforehand.

[Guest]

I think i have got this one....

Sorry for putting in attachment as my spoiler is not working...

PDR6.txt

[Guest]

The prisoner goes and stands by jar 1.

(A) When he hears the word Lakers he moves 8 jars forward (to 9 in the first case)

(B) If he hears the word Rule he stays where he is and waits for the next 3 words.

depending on these 3 words the next ball is:

Lakers Lakers Lakers: where he stands: position 0

Lakers Lakers Rule: next: position 1

Lakers Rule Lakers: position 2

Lakers Rule Rule: Position 3

Rule Lakers Lakers: position 4

Rule Lakers Rule: position 5

Rule Rule Lakers: position 6

Rule Rule Rule: position 7

After this he moves to the jar after the one he just identified and starts over at (A).

Extreme case, 9 balls are in the first 9 jars the last one is in the last jar:

to find the first 9 balls he needs to hear 4*9 words = 36 words

He is then standing on position 10. He moves to 18, 26, 34, 42, 50, 58, 66, 74, 82, 90, 98 = 11 words

He then needs 4 more words to identify the last jar = 4 words (3 would be enough, but to prevent confusion for the prisoner we are sticking to the same setup)

36 + 11 + 4 = 52 words which is less then the 54 words available.

[Guest]

@devil's own

Your solution seems to break down when there is more than 1 ball in a group of 3.

[Guest]

Suppose there is more than one ball in one group

that means there are only 9 groups which have balls and hence 24 people will say "Lackers"

hence, we have saved 2 person from that empty bottle group (otherwise that group had to use three persons to reveal its position)

These two persons can be used to reveal situtation about the third bottle... (Remember, we have identified the persons who will disclose about next three bottles.. if some other person comes, that means he is giving information about the third bottle and not about the next group...)

Hope i could make it clear...

[Guest]

if this is the same idea as the last puzzle like this no one can hear the words but the guy who saying them and the guy in rooom b

also i just took a quick glance devil but i think you process is dependent on them getting the information of what 3's have balls when they wouldnt know that at all, only the b room guy would... so you have to get enough information and give it to guy b without any input after the day of planning

i think

[Guest]

@devil's own

Your solution seems to break down when there is more than 1 ball in a group of 3.

Suppose there is more than one ball in one group

that means there are only 9 groups which have balls and hence 24 people will say "Lackers"

hence, we have saved 2 person from that empty bottle group (otherwise that group had to use three persons to reveal its position)

These two persons can be used to reveal situtation about the third bottle... (Remember, we have identified the persons who will disclose about next three bottles.. if some other person comes, that means he is giving information about the third bottle and not about the next group...)

Hope i could make it clear...

[Guest]

You are trying to convey more information than the 2 words.

if some other person comes, that means he is giving information about the third bottle and not about the next group

Any attempt to convey extra information like remaining silent, concatenating words, or walking a certain number of paces before stopping in room B will get all prisoners killed immediately.

Changing the order in which the prisoners enter the room would also fall in the "get all prisoners killed immediately" catagory.

[Guest]

there are only 10 balls for which there is a posiblity for all 10 to be next to each orther in such a case, you would need the extra 4 people, However I'll cover that unlikely solution later. so we will start with the first 50 prisoners. Each take responsablity for 2 of the jars. this would be ordered as such prisoner A would be an indicator for jar 1/2 and so on. However, the order which the prisoners come out does not have to be A,B,C. the order of the prisoners comming out would first be the prisoner who is in charge of the first set in sequence that has a ball in it. if that ball is in an odd numbered cup the prisoner would say rules, and if it is even then the prisoner would say lakers. in this way the first 10 prisoners who come out would be the indicators to where the balls are and the next 44 would be meaning less.

However, as I initaly indicated this dosen't account for more then one ball in a sequence of 2. This is where the extra 44 and to be more accurate the extra 4. If there were 2 balls in a section of 2 jars. the person assinged to that section would first come out and anounce Rule. Then one of the unassinged 4 people who dont already have a set of 2 assigned to them would come out and say lakers. in this way even if balls are next to each orther the position of the balls could be determined.

In the very unlikely case of 5 sets of 2 balls next to each orther starting from odd to even. The same strat of above would work up to the 9th ball. then someone whos numbers had already been passed over would come out and indicate lakers. In this way the prisoner would know that the sequence was 5 sets of 2 from odd to even.

In the least unlikly case of the first 10 jars all haveing a ball under them, then the first 9 balls would be discovered as above, however this time no free person would be in the sequence to show that he is out of the origanal order. in this case person governing jar 99/100 would come out and indicate lakers. then, to take into account the posiblity of the first 9 then the last 1 being the balls. the person governing the 97/98 or the 11/12 bottle would appear. if the 11/12 prisoner appeared then his presence would indicate that the last person comeing out is infact true and in sequence. if the 97/98 prisoner comes out it would indicate that the 99/100th prisoner was indicateing the 10th bottle and not the 100th.

[Guest]

Hi Merrick,

Your solution wont work in some cases. Take the following scenario.

The balls are in jars 1,2, 4,5, 7,8, 10,11, 13 and 100

Then to know about the first jar, he needs 4 words and similarly for 2nd jar and to know that ball is not present in jar no. 3, he needs 1 word... in total 9 words.

This pattern repeats for 4 times (so 4 * 9 = 36 words) and he will be at jar no. 13 at this point. 4 more words are needed to know about the ball in jar no.13. So 36 + 4 = 40 words.

Now he moves to 21, 29, 37, 45, 53, 61, 69, 77, 85, 93 (in total 10 words). SO totally 40 + 10 = 50 words. So what about the 100th one. How will he determine this?

May be i need to be little more clear

Look at the below spoiler...

I think the solution mentioned by devil's own will work with little bit modification (May be with bit more explanation).

- Divide the bottles into groups with each group having 3 bottles in it. So in total 33 groups + 1 bottle.

So 33 persons are used to know whether there is any ball in the particular group or not. (say persons numbering from 1 -33, and if they say Rules means ball is present, lakers means not present). And the 34th persons will be used to know whether there is any ball in the 100th jar or not (say Rules means ball is present in 100th jar, lakers means not present in 100th jar). So far, we have used 34 persons.

Consider all the balls are in different groups, then we can determine these by using 20 persons (person no.s 35 and 36 are used for first group where the ball is present and 37,38 for the second group where the ball is present and so on). In total 34 + 20 = 54 persons. First person will say rules if the ball is present in 1st position, lakers if it is not present at 1st position. Second person will say rules if the ball is present in 2nd position, lakers if it is not present at 2nd position. If both of them say lakers means the ball is present in 3rd position.

Consider we have two balls in 1 group. Then we will have only 9 groups containing the balls.(which is known to the person in room B). So we just need 34 + 18 = 52 to know about the 9 balls. Say the issue is if the balls are present 1/2 and at 3rd position in a group. If they are present in 1,2 positions in a group then there is no issue. So we still have persons 53 and 54 persons availabe with us. Say we have the balls at 1st and 3rd positions in group3. Then as the 39, 40 th persons are used to determine the ball at 1st position in group 3. immediately after these persons, 53 rd person can come and say rules if the ball is also present in 3rd position of group3. So we used up only 53 persons. As we get more than 1 ball in more number of groups, we can use less number of people than 54 ( As we are saving 2 persons for group and using 1 person to determine whether the ball is at 3rd position or not).

Even if we have 3 balls in a group above method should work.

[Guest]

YES it can be done, even if there were only 45 prisoners

100 jars and 10 balls... combinations in which the balls can be placed are 100C10 = 17,310,309,456,440

Strategy:

Before: Every permutation possible is numbered and memorized (all 17,310,309,456,440 of them).

During: Using a binary code the 'number' of the permutation in room A is relayed.

*54 prisoners can using a binary code can carry the information about any number < 2^54, i.e 1.8e16.

Note: this can be done with only 45 prisoners also.. 2^44 = 17,592,186,044,416

Edited May 26, 2009 by adiace

[Guest]

* Requires the prisoners to be able to decide which order they can go in.

The prisoners know each other, so they can set aside 10 ppl in the group. These 10 ppl will represent balls.

So now they send the 1st prisoner to roomB, if that prisoner is one of the ppl set aside then there is a ball in the 1st jar.

If its anyother prisoner, if he says Lakers then there is at least one gap between the last ball and the next. If he says Rules then 2 gaps.

so say..

010001010010011100001000001100

lets call the 10 ball representing ppl Qs. Lakers = L, Rules = R

LQRLQLQRQRQQQRRQRRLQQ

[Guest]

Actually the solution seems to be quite simple if you take into account that using the restricted words multiple times is not eliminated as a possibility. It says that only those two words may be used but it does not directly say that a or both words may not be spoken multiple times.

To put it quite simply, each prisoner can in turn recite multiple Boolean values.

Lakers = false

Rule = true

i.e. Prisoner 1 is responsible for conveying jars numbered 1 & 2 so if both contain a ball he says "Rule Rule". Prisoner number 2 is responsible for jars numbered 3 & 4, and so on through 100.

This would actually work with any number of prisoners since the number of times a word is said is not restricted specifically by the wording of the riddle.

[Guest]

Hi adiace,

Your solution will work according to theory but it is very hard to implement [].

I got one more solution, where the order of persons is not changed. I mean the persons can come in order... 1st person... 2nd person...etc.

This one is bit simpler than the previous one which i mentioned and also it consistently uses 54 persons always so that the person in room B will not get confused.

[spoiler=one more solution, pretty straight forward ]

Divide the balls into 25 groups each group having 4 balls in it.

- 25 persons are used to know whether the ball is present in particular group or not.

Now we use two persons to determine the position of first ball in a group and 1 person to decide whether to move to next group or not. (If he says rules means stay in same group and lakers means move to next group). Total 10 balls => 10 * 2 = 20 and 10 balls to determine => 9 persons to determine the position of next ball (whether in current group or next group). Total 25 + 20 + 9 = 54 persons.

For ex, look at the following cases.

- Consider balls are present in 10 different groups.

2 persons will be used to determine the ball poistion in first group and one person to move to the next group. (So in total 20 persons for position of balls and 9 to move to the next group). Total no. of persons used to determine ball positions are 20 + 9 = 54 persons.

TOTAL 25 + 29 = 54 persons

- Consider we have two balls in a group. (say group 2)

3 persons will be used to know ball position in 1st group and to move to the 2nd group. 3 more persons are used to determine ball position in 2nd group (Note the person says rules over here). So we need 3 more persons for determining second ball position in group 2. So far we used 3 + 3 + 3 = 9 persons to determine 3 ball positions (1 in 1st group and 2 in 2nd group). We will have only 7 more groups and we are currently in 3rd group. (As 2nd group have 2 balls). So we require 6 more persons to say "Move to next group" and 2 persons to know the ball position in each group. (6 + 2*7 = 20). Total 9 + 20 = 29.

- Consider we have three balls in a group. Total no. of groups will be 8.

2 persons to determine each ball position (2 *10 = 20) and 9 persons to determine whether the ball is present in same group or in the next group.

[Guest]

First of all they go 2 Jars at a time.

The night before, assign 10 men that represent Ball, Noball. Have them say Lakers

Assign 5 men to represent Ball, Ball. Have them say Lakers

Assign 10 men to represent Noball, Ball. Have them say Lakers

That leaves 29 men to represent the more likely of Noball, Noball. Have them say Lakers

Now anyone who says Rule, means it is No Ball, No Ball, In case the first 90 jars contain no balls.

Prisoner B just needs to remember what each guy represents as a 2 jar combo.

HOLD IT!!

DENVER RULES!!

[Guest]

* Requires the prisoners to be able to decide which order they can go in.

The prisoners know each other, so they can set aside 10 ppl in the group. These 10 ppl will represent balls.

So now they send the 1st prisoner to roomB, if that prisoner is one of the ppl set aside then there is a ball in the 1st jar.

If its anyother prisoner, if he says Lakers then there is at least one gap between the last ball and the next. If he says Rules then 2 gaps.

so say..

010001010010011100001000001100

lets call the 10 ball representing ppl Qs. Lakers = L, Rules = R

LQRLQLQRQRQQQRRQRRLQQ

Hi adiace,

Your solution will not work in some of the cases...

Consider the following case balls are present in 1,3,5,7,9,11,13,15,17 and 100 th jars.

Then you need 17 persons to get the positions of first 9 balls and you remain with only 37 persons. You still need to go through 82 jars (so that 17 + 82 =99). How can you do this with only 37 persons and using the login you mentioned??? (At max you can move to 74 positions after the 17th jar)

[Guest]

Actually the solution seems to be quite simple if you take into account that using the restricted words multiple times is not eliminated as a possibility. It says that only those two words may be used but it does not directly say that a or both words may not be spoken multiple times.

To put it quite simply, each prisoner can in turn recite multiple Boolean values.

Lakers = false

Rule = true

i.e. Prisoner 1 is responsible for conveying jars numbered 1 & 2 so if both contain a ball he says "Rule Rule". Prisoner number 2 is responsible for jars numbered 3 & 4, and so on through 100.

This would actually work with any number of prisoners since the number of times a word is said is not restricted specifically by the wording of the riddle.

Hi jakez,

We have the following condition in the question.

"Any attempt to convey extra information like remaining silent, concatenating words, or walking a certain number of paces before stopping in room B will get all prisoners killed immediately."

it has concatenating words, and i think you are doing this.

[bushindo]

Hi adiace,

Your solution will work according to theory but it is very hard to implement [].

I got one more solution, where the order of persons is not changed. I mean the persons can come in order... 1st person... 2nd person...etc.

This one is bit simpler than the previous one which i mentioned and also it consistently uses 54 persons always so that the person in room B will not get confused.

[spoiler=one more solution, pretty straight forward ]

Divide the balls into 25 groups each group having 4 balls in it.

- 25 persons are used to know whether the ball is present in particular group or not.

Now we use two persons to determine the position of first ball in a group and 1 person to decide whether to move to next group or not. (If he says rules means stay in same group and lakers means move to next group). Total 10 balls => 10 * 2 = 20 and 10 balls to determine => 9 persons to determine the position of next ball (whether in current group or next group). Total 25 + 20 + 9 = 54 persons.

For ex, look at the following cases.

- Consider balls are present in 10 different groups.

2 persons will be used to determine the ball poistion in first group and one person to move to the next group. (So in total 20 persons for position of balls and 9 to move to the next group). Total no. of persons used to determine ball positions are 20 + 9 = 54 persons.

TOTAL 25 + 29 = 54 persons

- Consider we have two balls in a group. (say group 2)

3 persons will be used to know ball position in 1st group and to move to the 2nd group. 3 more persons are used to determine ball position in 2nd group (Note the person says rules over here). So we need 3 more persons for determining second ball position in group 2. So far we used 3 + 3 + 3 = 9 persons to determine 3 ball positions (1 in 1st group and 2 in 2nd group). We will have only 7 more groups and we are currently in 3rd group. (As 2nd group have 2 balls). So we require 6 more persons to say "Move to next group" and 2 persons to know the ball position in each group. (6 + 2*7 = 20). Total 9 + 20 = 29.

- Consider we have three balls in a group. Total no. of groups will be 8.

2 persons to determine each ball position (2 *10 = 20) and 9 persons to determine whether the ball is present in same group or in the next group.

I would like some detail filled

Suppose that a group of 4 has more than two balls. We use up 1 prisoner to indicate whether a ball is present. We use up another 2 to indicate where the first ball is, probably using a binary scheme. And then the next prisoner could indicate whether to move on or not. However, he, and possibly the prisoners after him, is also supposed to convey extra information about the possibility of more balls in the 4 jars, but that job function is impaired since one word is already reserved for indicating "move on".

So, to make it concrete, how would you communicate the following sequence in your method

(Ball, Empty, Empty, Empty)

(Ball, Empty, Empty, Ball )

[Guest]

Okay so then no loophole but a partial solution here -

So -

The first 25 prisoners are responsible for 4 jar blocks. They convey Boolean true or false as to whether each 4 jar block contains any balls.

This whittles the the possible blocks down to 10 blocks of 4 (40 jars). (25 prisoners for 100 jars)

The next 20 convey those 40 jars as blocks of 2 (i.e. 20 blocks of 2) as Booleans of true or false as to whether they contain any balls or not. (20 prisoners for 40 jars)

Now we have 20 possible jars and 9 prisoners... How to finish is escaping me right now.

And maybe it could be the number of blocks/jars/prisoners reporting per step in the sequence that needs to be tweaked.

Edited May 26, 2009 by jakez

[Guest]

never mind. Just saw that each prisoner can only say one word.

Edited May 26, 2009 by dimrock

[Guest]

Okay so then no loophole but a partial solution here -

So -

The first 25 prisoners are responsible for 4 jar blocks. They convey Boolean true or false as to whether each 4 jar block contains any balls.

This whittles the the possible blocks down to 10 blocks of 4 (40 jars). (25 prisoners for 100 jars)

The next 20 convey those 40 jars as blocks of 2 (i.e. 20 blocks of 2) as Booleans of true or false as to whether they contain any balls or not. (20 prisoners for 40 jars)

Now we have 20 possible jars and 9 prisoners... How to finish is escaping me right now.

And maybe it could be the number of blocks/jars/prisoners reporting per step in the sequence that needs to be tweaked.

Your solution will work because you don't need 25 for the first round only 24. Same with the 20, only 19. 10 more will give you the answer.

[Guest]

Your solution will work because you don't need 25 for the first round only 24. Same with the 20, only 19. 10 more will give you the answer.

That's not true. You will need to scan all 25, primarily because you can't extract enough information unless in the instance that all 10 groups have already been uncovered. But that's only in the best case scenario. We have to try to disprove it by working backwards with any assortment.

[Guest]

Hi Merrick,

Your solution wont work in some cases. Take the following scenario.

The balls are in jars 1,2, 4,5, 7,8, 10,11, 13 and 100

Then to know about the first jar, he needs 4 words and similarly for 2nd jar and to know that ball is not present in jar no. 3, he needs 1 word... in total 9 words.

This pattern repeats for 4 times (so 4 * 9 = 36 words) and he will be at jar no. 13 at this point. 4 more words are needed to know about the ball in jar no.13. So 36 + 4 = 40 words.

Now he moves to 21, 29, 37, 45, 53, 61, 69, 77, 85, 93 (in total 10 words). SO totally 40 + 10 = 50 words. So what about the 100th one. How will he determine this?

Hi brshravan,

In my solution he doesn't need to know that there is no ball present in jar no 3.

1: Rule Lakers Lakers Lakers (he is now standing by jar 2)

2: Rule Lakers Lakers Lakers (he is now standing by jar 3)

4: Rule Lakers Lakers Rule (5)

5: Rule Lakers Lakers Lakers (6)

7: Rule Lakers Lakers Rule (8)

8: Rule Lakers Lakers Lakers (9)

10: Rule Lakers Lakers Rule (11)

11: Rule Lakers Lakers Lakers (12)

13: Rule Lakers Lakers Rule (14) (words 36)

Standing by jar 14: Lakers 22, Lakers 30, Lakers 38, Lakers 46, Lakers 54, Lakers 62, Lakers 70, Lakers 78, Lakers 86, Lakers 94 (words 10)

100: Rule Rule Rule Lakers (words 4)

total words: 50

[Guest]

Lakers=1

Rules=0

This is the algorithm:

First step:

The first person will say 0 if in the first 4 bottles there are no balls and 1 if there is.

If the first person said 1 then the next two persons will tell him where the first ball is ( if 00 in the first, 01 if in the second, 10 in the third and 11 if in the fourth).

So the first part needs 1 or 3 persons depending on the configutarion of the balls. We then repeat this step with the next person starting with the next person and with the next bottle we know nothing about (the fifth one if the first person said 0 and on 2nd, 3rd, 4th of 5th if he said one).

For example, O represents empty bottle and X a bottle with a ball:

for

OOOO OX OX X

they would say

0 101 101 100

Now, for each ot the 10 balls we need 3 persons to describe its location when the time comes, and we have 24 persons left, they can discard 96 bottles, since there are only 90 empty bottles, this is enough.

[Guest]

Let's put the 54 people in exact order...let's say alphabetical. Each person represents 2 jars. Each person goes in and see a ball in their two jars, he'll report "Lakers" if ball is in jar 1 or "Rules if ball is in jar 2. If there's a ball in jar 1 (forcing him to say "Lakers") the next person's responsible jar will be Jar 2 and 3....and so on. If there's no ball in his jars, he'll move to the end of the line; in essence we'll skip him in order to indicate that his jars are empty. Since he's skipped, he'll move to the back of the line in the next order. If anyone needs example:

Senario 1 - Aaron goes in the see a ball in Jar 1 - he go to room B and say "Lakers". Abner goes in and see a ball in Jar 2 and he goes in and say "Lakers". Acton goes in and see a ball in jar 4, he say "Rules". Adonis goes in and see no ball in jar 5 or 6, so he count to the next possible place in line and keep note of what he'll say or if he'll say anything; but he doesn't report to room B...yet if at all. Aeon goes in and see a ball in jar 7, he'll say "Lakers"...and so on.

Let's say the worst case senario is that the balls are in the first 9 jars and the last ball is in the last jar. Then Aaron, Abner, Acton, Adonis, Aeon, Aflac, Again, Ahmed, and Aioke all have said Lakers. The next 90 jars are all empty so the remaining 45 prisoners can't report anything. Since no other prisoner reported, then the last ball must be in the last jar and thus the person in room B has recontructed the position of the balls.

Senario, the first 90 jars are empty so then Ulyssis would have said "Rules", and Van, Verron, Vick, William, Wong, Xena, Yoshida, Zohan, and Aaron all would've said "Rules" to complete the puzzle (skipping the other 45 prisoners ahead of them with Aaron wrapping around back to his turn).

I hope this is simple and logical.