[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.

[Guest]

Hi! i'm an idiot

Edited May 26, 2009 by birleis

[Guest]

Sorry, forgot to put spoiler and I can't seem to edit my last post.

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]

I hope this is simple and logical.

Perfection at it's best!!!

I was trying to figure out my partial solution with something similar... 33 prisoners report on 3 jars each leaving a ratio of 30 remaining jars (leaving one jar for the 55th prisoner to decide on) to 21 prisoners but that was as close to parity as I could get it.

Jake

[Guest]

For every Ball, the min number of prisons required to represent the gap between the last ball and this one in binary (where the last prisoner sent in the code is a pre-determined ball representative.. something like a stop-bit).

Note:

Gap:

0 to 1 <= 2^1 .... 1 special ball rep prisoner

2 to 3 <= 2^2 .... 1 regular prisoner and 1 special ball rep prisoner

4 to 7 <= 2^3 .... 2 regular prisoner and 1 special ball rep prisoner

8 to 15 <= 2^4 .... 3 regular prisoner and 1 special ball rep prisoner

16 to 31 <= 2^5 .... 4 regular prisoner and 1 special ball rep prisoner

32 to 62 <= 2^6 .... 5 regular prisoner and 1 special ball rep prisoner

64 to 128 <= 2^7 .... 6 regular prisoner and 1 special ball rep prisoner

[Guest]

Sorry, forgot to put spoiler and I can't seem to edit my last post.

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.

between "OOOO OXOO OXOO" and "OOOO OXOX"

wouldn't both be 0101?

[Guest]

For every Ball, the min number of prisons required to represent the gap between the last ball and this one in binary (where the last prisoner sent in the code is a pre-determined ball representative.. something like a stop-bit).

Note:

Gap:

0 to 1 <= 2^1 .... 1 special ball rep prisoner

2 to 3 <= 2^2 .... 1 regular prisoner and 1 special ball rep prisoner

4 to 7 <= 2^3 .... 2 regular prisoner and 1 special ball rep prisoner

8 to 15 <= 2^4 .... 3 regular prisoner and 1 special ball rep prisoner

16 to 31 <= 2^5 .... 4 regular prisoner and 1 special ball rep prisoner

32 to 62 <= 2^6 .... 5 regular prisoner and 1 special ball rep prisoner

64 to 128 <= 2^7 .... 6 regular prisoner and 1 special ball rep prisoner

Its worst case..

31 Noballs, BALL, 31Nballs, BALL, 15Noballs, BALL, 7Noballs, BALL, 3Noballs, BALL, 3Noball, BALL, 4BALLS

Breaking it down we need to represent the numbers

32 32 16 8 4 4 1 1 1 1

we need this many prisoners

6 6 5 4 3 3 1 1 1 1 = 31

[Guest]

Way too simple that I overlooked it!!!

So... The 55th prisoner will pick out the following.

4 people he knows best. They will represent either-

lakers = ball - ball or

rule = no ball - no ball

He will then pick out 10 more people he can recognize and they will represent -

lakers = ball - no ball or

rule = no ball - ball

Everyone else now represents, no ball-no ball.

The 55th prisoner begins at jar 2 and starts counting up once the total count reaches 100 he ignores all other incoming prisoners. Once the count reaches 100 he ignores the remaining prisoners and determines the 1st jar by whether he has a ball left to place or not. (mind you the 100th jar can be either determined by an unknown prisoner or one of the 10 lesser known or even one of the better known if needed)

Throw any combination at it and it works!!

Edited May 26, 2009 by jakez

[bushindo]

Way too simple that I overlooked it!!!

So... The 55th prisoner will pick out the following.

4 people he knows best. They will represent either-

lakers = ball - ball or

rule = no ball - no ball

He will then pick out 10 more people he can recognize and they will represent -

lakers = ball - no ball or

rule = no ball - ball

Everyone else now represents, no ball-no ball.

The 55th prisoner begins at jar 2 and starts counting up once the total count reaches 100 he ignores all other incoming prisoners. Once the count reaches 100 he ignores the remaining prisoners and determines the 1st jar by whether he has a ball left to place or not. (mind you the 100th jar can be either determined by an unknown prisoner or one of the 10 lesser known or even one of the better known if needed)

Throw any combination at it and it works!!

I've seen some good answers, and some that are really inventive. The flurry of activity seems to be strong, so I'll leave it be for now. I've seen some solution introduce extra information by choosing the order in which the prisoners take their turn. The problem with that is each prisoner only gets to see the configuration once it is his turn. Those who have yet to take their turn don't know what the ball configuration is, and thus can't choose who to go next. Besides, introducing the new information makes this problem too easy.

For this problem, assume that at the beginning of every turn, the warden randomly chooses a prisoner to go up.

[Guest]

I've seen some good answers, and some that are really inventive. The flurry of activity seems to be strong, so I'll leave it be for now. I've seen some solution introduce extra information by choosing the order in which the prisoners take their turn. The problem with that is each prisoner only gets to see the configuration once it is his turn. Those who have yet to take their turn don't know what the ball configuration is, and thus can't choose who to go next. Besides, introducing the new information makes this problem too easy.

For this problem, assume that at the beginning of every turn, the warden randomly chooses a prisoner to go up.

Bushindo, you are now adding "extra information" which was not originally in the riddle. You never said the prisoners would go in random order or that they had to go in immediately after they looked. You also never said that they could not choose the order they looked at the jars and went into room B in.

You specifically say- "He then can go to room B".

So given that we choose the order but the prisoners must either go in or not go in immediately after they look. I would utilize the first prisoner as an initial throw away looker (who could choose not to go into room b right away if there was a ball under one of the first 2) he could then tell which type of prisoner needed to go and look next and they in turn could tell the next and so on... Bearing in mind that you also never said that the 54 prisoners could not communicate to each other in any way they chose to.

My solution answers your riddle completely even given that the prisoners now need to either go in or not go into room B immediately after they look.

I will now look for a solution to your new "factors".

Edited May 26, 2009 by jakez

[Guest]

The hardest part of making a riddle is crafting it in such a way as to allow only one possible solution (yours).

[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.

It will work for the one ball in each group case. You don't need to look in the last box because you will know by then if there is a ball or not so - no use looking and waisting a man. As for the multiball case - you will know because you will have less than 9 at the end and yes for eight or less you will have to scan all 25 but that won't matter because you will have fewer sets to scan-

[CaptainEd]

I've seen some good answers, and some that are really inventive. The flurry of activity seems to be strong, so I'll leave it be for now. I've seen some solution introduce extra information by choosing the order in which the prisoners take their turn. The problem with that is each prisoner only gets to see the configuration once it is his turn. Those who have yet to take their turn don't know what the ball configuration is, and thus can't choose who to go next. Besides, introducing the new information makes this problem too easy.

For this problem, assume that at the beginning of every turn, the warden randomly chooses a prisoner to go up.

What's wrong with Palascosas' answer? As I read it, the worst case only requires 52 lookers:

I'll rephrase it:

at the beginning, (or immediately after locating a ball)

L means 0000.

RLL means 1

RLR means 01

RRL means 001

RLL means 0001

Now, move past the ball (ie. the "1"), reset the new frame boundary and start again.

What is the most inconvenient location of the balls? One in which we only get to move over one space after every ball, in other words an RLL sequence.

Where do we have to spend the most space before the last ball? If the last ball is in jar 100.

So, assuming every ball is inconveniently right after the end of a frame, the worst place is if they're in the last 10 frames.

The search looks like this:

(empty jars, jar with ball)

13*L (1-52) (no ball yet)

RRL (53-54;55)

LRLL (56-59;60)

LRLL (61-64;65)

LRLL (66-69;70)

LRLL (71-74;75)

LRLL (76-79;80)

LRLL (81-84;85)

LRLL (86-89;90

LRLL (91-94;95)

LRLL (96-99;100)

16+36=52, we've got two lookers left to pour the champagne!

Edited May 26, 2009 by CaptainEd

[Guest]

between "OOOO OXOO OXOO" and "OOOO OXOX"

wouldn't both be 0101?

OOOO OXOO would be: 0 101

OOOO OX OX would be: 0 101 101

OOOO OX OOOX OO would be 0 101 111 0

In the first you need only 4 prisoners to get the first eight bottles but in the second case you need 7.

I put spaces so that its easier to see which prisoners represent what bottles.

[Guest]

Split the cups into rows and columns as such - 1 through 100 (8 x 12.5):

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^

Now beginning your way down each row, Lakers means "ball in row," Rule = "no balls left in row." So, for example, LRRLLRR would translate to 1 ball in row A, 0 in B, 2 in row C, 0 in row D, etc.

This combination utilizes at most 22 prisoners, so leaving us with at least 32 prisoners left and knowing how many balls exist in each row. Now to figure out what column they go into...

Using a binary system and working from top-left to bottom-right...

RRR = 1st column position

RRL = 2nd

RLR = 3

RLL = 4

LRR = 5

LRL = 6

LLR = 7

LLL = 8

With over 30 prisoners left and only 3 needed to find each of 10 successive balls, must rejoicing ensues.

[Guest]

I am modifying my original answer since it did not solve for one potential situation in the original riddle. If there where ten in a row from jars 2-11 or any other given 10 in a row where it would require 5 double "ball-ball" prisoners.

So... The 55th prisoner will pick out the following.

1 person to be the initial person to come in. That person would tell him to either start at jar 1 or jar 2 with a true/false.

4 people he knows best. They will represent either-

lakers = ball - ball or

rule = no ball - no ball

He will then pick out 10 more people he can recognize and they will represent -

lakers = ball - no ball or

rule = no ball - ball

Everyone else (39) now represents, no ball-no ball.

The 55th prisoner either begins at jar 1 or jar 2 depending on the first persons answer and starts counting up once the total count reaches 100 he ignores all other incoming prisoners. Once the count reaches 100 he ignores the remaining prisoners and determines the 1st jar if need be by whether he has a ball left to place or not. (mind you the 100th jar can be either determined by an unknown prisoner or one of the 10 lesser known or even one of the better known if needed)

----(the reasoning behind the initial prisoner setting an offset is that if there are 10 jars w/ balls in a row, depending on if the 1st of that series starts on an odd or even number the initial prisoner can offset the counting to allow for either the 1st jar to be left alone -if it is 1 through 10 - or to offset the jar to start counting from so the 10 in a row can be started by one of the 10 prisoners who would answer "no ball-ball" to start the jars w/balls in a row and ended by one of the 10 who would answer "ball-no ball")

Oh yeah and to the case that there are ten in a row somewhere in the middle, once all balls are used all other prisoners are ignored.

Throw any combination at it and it works!!

[Guest]

It will work for the one ball in each group case.

Hence my point when I say "that's only in the best case scenario." The point of these problems isn't to magically will the balls into the one scenario that holds true, but to come up with a solution that tests against every available outcome so it's watertight. Saying you never have to scan the last row in hopes that you'll get 10 pings works against any form of deduction in solving this riddle.

[Guest]

Hence my point when I say "that's only in the best case scenario." The point of these problems isn't to magically will the balls into the one scenario that holds true, but to come up with a solution that tests against every available outcome so it's watertight. Saying you never have to scan the last row in hopes that you'll get 10 pings works against any form of deduction in solving this riddle.

This is not the BEST CASE scenario. What row? This is a simple sort. Any programer worth his salt can tell you exactly how to do this. Nothing magical. Why would I search a bottle, there-by wasting a man, that I didn't have to? The same logic applies to any combimnation of bottles. If I told you that a 4 digit biniary number contained two 0 and two 1 and then I told you that the first digit was a 1 and the second and third was a 0 would I REALLY need to tell you what the last digit was or would you need to look?

[Guest]

Ok, let's take this back from step 1, and let me know if we're on the same page...

jakez says:

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.

then you replied with:

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.

So my point was extending to the fact that say you come across the case that 8 of the first 24 blocks return with a "true" value. How does this prove in every instance that you don't need to scan the 25th block?

Remember, it's a true/false value, not an automatic "1 ball in this block of 4 jars." So in that case, a 1 out of 4, or even 4 out of 4 returns a "true" value.

[bushindo]

Good try, everyone.

I haven't had time to read everyone's post, so I'll just comments on some of the ones that jumped at me

brshravan in post 17 and Palascosas in post 25 had answers that will surely save the prisoners.

This is a compression problem. Since the 100 jars with 10 balls is a low entropy situation, we can compress all the information in the jars (consider it a 100-digit binary string) with a much shorter binary string (see the topic Prisoners on a Death Row 5). The maximum any compression algorithm can do in this situation is to compress it to a 45-digits binary strings. Good encoding algorithm can come close to this limit. Less efficient codes will require more digits.

brshravan algorithm follow along the lines of entropy encoding, the main concept of which is to break the sequence into subsequence of 4 jars. There are then 16 possible configurations, but not all of them equally likely. All four empty jar is the most likely, followed 3 empty jars with 1 ball, followed by 2 empty and 2 balls, and so on. The key is to encode the most likely 4-jar configuration with the short string, and the most unlikely configuration with a longer string. This is one of the more efficient encoding method.

Palascosas in post 25 has a slightly different method, based on sliding window. It is slightly less efficient, but still comes in under the 54 prisoners limit.

Its worst case..

31 Noballs, BALL, 31Nballs, BALL, 15Noballs, BALL, 7Noballs, BALL, 3Noballs, BALL, 3Noball, BALL, 4BALLS

Breaking it down we need to represent the numbers

32 32 16 8 4 4 1 1 1 1

we need this many prisoners

6 6 5 4 3 3 1 1 1 1 = 31

Good try here, adiace, but there's a slight problem.

It is not possible to fully encode all permutation of 10 balls in 100 jars (100 choose 10 = 1.731031 * 10^13 ) with 31 prisoners ( 2^31 = 2.14*10^9). Your encoding method is call run-length encoding, and the problem with the calculations was that not only you have to encode the gaps, but you have to encode something called the stop bit as well, which in your example are the spaces in between your numbers.

[Guest]

Break up the array of bottles into groups of 8 so there are 12 groups of 8 (96 total) and 1 group of 4.

The (four digit) binary digits for 0 - 7 are given by 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 (note that none of these start with 1).

Let Lakers = 0

Let Rule = 1

To communicate the location of any ball (in a particular group of 8) will take 4 people...they just give the location by binary numbers 0 - 7. This will happen at most 10 times in the first 96 bottles so at most 40 people will be needed.

To request a shift to the next group of 8 a prisoner simply says "Rule". Since 0 - 7 do not start with 1, a "Rule" in the first position of four could not be mistaken for the start of a binary number since the one prisoner will be looking for groups of 4.

Two cases:

1. All balls are in first 96 bottles.

In this case 40 people will have been used and and 11 switches...hence 51 total. In this case, once the last ball is located the game stops.

2. There is at least one ball in the final four bottles.

Let n be the number of balls left. Then 40 - 4n prisoners have been used to locate the other balls and 12 people have been used for switches ending up at the last group of 4.

In this case, it will be clear that at least one of the remaining 4 bottles has a ball. For every ball there are 4 prisoners left and their location can easily be identified using the same 4 digit binary code.

[bushindo]

Break up the array of bottles into groups of 8 so there are 12 groups of 8 (96 total) and 1 group of 4.

The (four digit) binary digits for 0 - 7 are given by 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 (note that none of these start with 1).

Let Lakers = 0

Let Rule = 1

To communicate the location of any ball (in a particular group of 8) will take 4 people...they just give the location by binary numbers 0 - 7. This will happen at most 10 times in the first 96 bottles so at most 40 people will be needed.

To request a shift to the next group of 8 a prisoner simply says "Rule". Since 0 - 7 do not start with 1, a "Rule" in the first position of four could not be mistaken for the start of a binary number since the one prisoner will be looking for groups of 4.

Two cases:

1. All balls are in first 96 bottles.

In this case 40 people will have been used and and 11 switches...hence 51 total. In this case, once the last ball is located the game stops.

2. There is at least one ball in the final four bottles.

Let n be the number of balls left. Then 40 - 4n prisoners have been used to locate the other balls and 12 people have been used for switches ending up at the last group of 4.

In this case, it will be clear that at least one of the remaining 4 bottles has a ball. For every ball there are 4 prisoners left and their location can easily be identified using the same 4 digit binary code.

It works. Well done.

[Guest]

bushindo, I'd be interested to hear your analysis of my answer if you get a chance.

[Guest]

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 )

1st case: lakers, lakers (binary - 00) - ball at 1st position in group followed by lakers to indicate move to next group.

2nd case: lakers, lakers(binary 00 - first ball position) and rules to stay in same group followed by rules, rules (binary 11 - 2nd ball position) followed by lukers to indicate move to next group.

I hope i answered your question

Edited May 27, 2009 by brshravan

[bushindo]

Split the cups into rows and columns as such - 1 through 100 (8 x 12.5):

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^ ^ ^ ^ ^

^ ^ ^ ^

Now beginning your way down each row, Lakers means "ball in row," Rule = "no balls left in row." So, for example, LRRLLRR would translate to 1 ball in row A, 0 in B, 2 in row C, 0 in row D, etc.

This combination utilizes at most 22 prisoners, so leaving us with at least 32 prisoners left and knowing how many balls exist in each row. Now to figure out what column they go into...

Using a binary system and working from top-left to bottom-right...

RRR = 1st column position

RRL = 2nd

RLR = 3

RLL = 4

LRR = 5

LRL = 6

LLR = 7

LLL = 8

With over 30 prisoners left and only 3 needed to find each of 10 successive balls, must rejoicing ensues.

Yours work too. Well done

this method again is very similar to entropy encoding. basically, you break the sequence into sub-sequence of 8. You let the prisoner say Rule = "no balls left in row," which is equivalent to encoding a sequence of 8 empty jars by 1 single bit of information, giving you a huge amount of compression. Well done, I like the idea of breaking the cups into a matrix.

[Guest]

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

Yes Merrick, your solution works in the case i mentioned. I am sorry, i misunderstood your solution.