[bushindo]

This is a fairly easy one.

There are 20 prisoners on the death row. The warden implements a simple game. He divides the group into two groups of 10.

The first 10 he puts into a room (call it room A) with 100 jars. Each jar either is empty, or has a ball underneath. The other 10 prisoners are put into a different room (call it room B) with 100 empty jars, and a stack of balls.

Each prisoner from room A will take turn looking under 25 jars of his choice, away from the sight of his fellow prisoners. He then can go to room B and say 1 monosyllabic word to the prisoners there. Assume he can not convey any other information besides that word (so no facial expression, body language, hand gestures, etc. ). The 10 prisoners in room B will then have to reconstruct the permutation of the balls in room A.

If the prisoners in room B can successfully reconstruct the permutation in room A in less than 10 turns, all 20 will live. Otherwise they will die.

1) Describe a strategy to do it, taking less than 10 turns.

2) Assume that the prisoners have limited memory. Describe a strategy to do it that requires the minimum amount of information to be memorized by each prisoner. That is, describe one approach that minimizes the sum of information to be memorized over 20 prisoners.

Edited May 22, 2009 by bushindo

[Guest]

Are the stack of balls in room B equal to the amount of hidden balls in room A?

[Guest]

Do the prisoners in room A get to communicate with the other prisoners in room A

and the same with room B

either verbally or non verbally?

leaving jars tipped or moved to indicate the jars they are communicating

[bushindo]

Do the prisoners in room A get to communicate with the other prisoners in room A

and the same with room B

either verbally or non verbally?

leaving jars tipped or moved to indicate the jars they are communicating

Assume there are 100 balls in room B, but you don't have to use all of them to reconstruct room A's permutation.

Assume all 20 prisoners get 1 night to prepare.

Assume that prisoners from A can not communicate to his friend from the same room (ie. no modification of any kind to the jar's appearances, orientation, placement, etc.). Prisoners from room B can freely communicate with one another.

[Guest]

I don't have the answer...only a train of thought I can't seem to get to the train station:

I'm thinking something along the lines of enacting binary. e.g., Break the 100 jars into 10 groups of 10. This gives 1,024 combinations of balls under jars (2^10). Then each Room A prisoner somehow denotes the binary translated number (assuming a ball is a "1" and an empty jar is a "0").

Small example, incase I'm unclear: For 3 jars, say they are empty > red ball > red ball, respectively.

So in binary, this would be represented as 011. Translated to decimal, that would be 3.

The only problem is, I'm not sure how to convey all the numbers from 0 to 1,024 in distinct, monosyllabic words (do they have to be actual english words, or can they just be just a sound?)

[Guest]

It seems that the 10 prisoners get to hear a maximum of 10 words (1 from each of the 10 prisoners in room A). You wouldn't even need a strategy really. Just have the prisoners in room A arrange and put the jars with the ball under them in order as far as they can. Then say the following to room B: Ball in every jar but last __(# of jars empty), if its a number over 12(meaning more than 1 syllable), then you just say one number at a time. Now the prisoners in room B know every jar has a ball up to x number of jars left that will be empty. Example of what could be said: Ball in every jar but last two three.

Now I would think that 1 prisoner could easily do it by himself, and without using much memory, he just needs to remember each word as the prisoners in room A come to say it.

[Guest]

It seems that the 10 prisoners get to hear a maximum of 10 words (1 from each of the 10 prisoners in room A). You wouldn't even need a strategy really. Just have the prisoners in room A arrange and put the jars with the ball under them in order as far as they can. Then say the following to room B: Ball in every jar but last __(# of jars empty), if its a number over 12(meaning more than 1 syllable), then you just say one number at a time. Now the prisoners in room B know every jar has a ball up to x number of jars left that will be empty. Example of what could be said: Ball in every jar but last two three.

Now I would think that 1 prisoner could easily do it by himself, and without using much memory, he just needs to remember each word as the prisoners in room A come to say it.

I like the way you think since it does not say prisoners in room A cannot rearrange the balls. But since the prisoners in A cannot communicate with each other or see which jars they lift. the second prisoner has no idea which balls the first prisoner already moved etc.

[Guest]

I like the way you think since it does not say prisoners in room A cannot rearrange the balls. But since the prisoners in A cannot communicate with each other or see which jars they lift. the second prisoner has no idea which balls the first prisoner already moved etc.

I think you are right, I did'nt see post #4. But I think 10 prisoners opening 25 jars each could fgure out a way to arrange them that way, or a similar way.

[CaptainEd]

If so, as James observes, A1 could simply move all the balls he finds in the first 25 jars (10 or less) into the first n jars, reports back the English number (with "se'en" instead of "seven"). A2 would be responsible for the next 25, A3 for the next, and A4 for the last.

If not, we've got to think deeper...

Edited May 22, 2009 by CaptainEd

[bushindo]

If not, we've got to think deeper...

If so, as James observes, A1 could simply move all the balls he finds in the first 25 jars (10 or less) into the first n jars, reports back the English number (with "se'en" instead of "seven"). A2 would be responsible for the next 25, A3 for the next, and A4 for the last.

No moving of the balls allowed. Each prisoner is only allowed to look under 25 jars of his choice. The prisoners in room B are supposed to replicate the exact initial arrangement of the balls in room A.

Edited May 22, 2009 by bushindo

[Guest]

The night before they could figure out all the combinations that are possible under 25 jars of having a ball or no ball(e.g. ball, noball, no ball, ball, ball ect..) Now give each combo a one syllable word, and after the last prisoner has looked and spoke with room B, I say 1 prisoner could figure it out. This might be a bit much to remember tho, but its all I got for now.

[CaptainEd]

I offer the rails for Remnar's train of thought:

Per Remnar's notion, we'll have each A prisoner look at 10 jars, and translate the pattern of presence/absence into a 10-bit binary number.

Then, translate the number into a mixed-base number system

[2][11][5][10]

For example,

(decimal) 43 = 0043

(decimal) 95 = 0145 (that is, 1 x 50 + 4 x 10 + 5)

(decimal) 1000 = 1900 (that is, 1 x 550 + 9 x 50)

0 = 0000

Now, construct a word in the following rather constrained language (for the most part, pronounceable in English)

units digits:

0123456789

bdgklmnpst

tens digits:

01234

aeiou

hundreds digits:

012345678 9 A

bdfgjkptv ch th

thousands digits:

0,1

silent,s

So, the words above would be:

(decimal) 43 = 0043 = buk

(decimal) 95 = 0145 = dum

(decimal) 1000 = 1900 = schab

(decimal) 0 = 0000 = bab

All the prisoners have to remember these 4 strings for encoding and decoding.

Now, each A prisoner handles a batch of 10 jars, constructs the binary number, converts it to the mixed-based number system, translates the digits into a pronounceable monosyllabic word, and tells it to the B team. It takes 10 A prisoners to do the job.

The B prisoners simply take each A's word and immediately construct the combination for that batch of 10 jars, so they don't have to remember those results to construct the next batch.

Edited May 22, 2009 by CaptainEd

[bushindo]

I offer the rails for Remnar's train of thought:

Per Remnar's notion, we'll have each A prisoner look at 10 jars, and translate the pattern of presence/absence into a 10-bit binary number.

Then, translate the number into a mixed-base number system

[2][11][5][10]

For example,

(decimal) 43 = 0043

(decimal) 95 = 0145 (that is, 1 x 50 + 4 x 10 + 5)

(decimal) 1000 = 1900 (that is, 1 x 550 + 9 x 50)

0 = 0000

Now, construct a word in the following rather constrained language (for the most part, pronounceable in English)

units digits:

0123456789

bdgklmnpst

tens digits:

01234

aeiou

hundreds digits:

012345678 9 A

bdfgjkptv ch th

thousands digits:

0,1

silent,s

So, the words above would be:

(decimal) 43 = 0043 = buk

(decimal) 95 = 0145 = dum

(decimal) 1000 = 1900 = schab

(decimal) 0 = 0000 = bab

All the prisoners have to remember these 4 strings for encoding and decoding.

Now, each A prisoner handles a batch of 10 jars, constructs the binary number, converts it to the mixed-based number system, translates the digits into a pronounceable monosyllabic word, and tells it to the B team. It takes 10 A prisoners to do the job.

The B prisoners simply take each A's word and immediately construct the combination for that batch of 10 jars, so they don't have to remember those results to construct the next batch.

Bravo, CaptainEd and Remnar. I was thinking of letting each prisoner memorize a list of 1024 monosyllabic alphabetized words. Each spoken word can then encodes number corresponding to its position in the list. But CaptainEd's solution is deeper and more elegant.

[Guest]

The night before they could figure out all the combinations that are possible under 25 jars of having a ball or no ball(e.g. ball, noball, no ball, ball, ball ect..) Now give each combo a one syllable word, and after the last prisoner has looked and spoke with room B, I say 1 prisoner could figure it out. This might be a bit much to remember tho, but its all I got for now.

I think this would work just as good, and it seems simpler.

[bushindo]

I think this would work just as good, and it seems simpler.

Just a note, this approach requires the each of the first four prisoners to memorize 2²⁵ = 33,554,432 million combinations. There aren't 33 millions monosyllabic words in the english language, so the prisoners gotta figure something out there too.

[Guest]

Just a note, this approach requires the each of the first four prisoners to memorize 2²⁵ = 33,554,432 million combinations. There aren't 33 millions monosyllabic words in the english language, so the prisoners gotta figure something out there too.

With 16 pre-selected consonants and 4 vowels, one could construct 2^10 unique words, or more specifically, all combinations of 10 ball words. If each of 10 prisoners only looked at 10 balls, they could convey the whole sequence in Consonant-Vowel-Consonant words guaranteed to be pronouncable and monosyllabic.

[Guest]

Just a note, this approach requires the each of the first four prisoners to memorize 2²⁵ = 33,554,432 million combinations. There aren't 33 millions monosyllabic words in the english language, so the prisoners gotta figure something out there too.

So I should have said 10 prisoners, take 10 jars, and thats 1024.

[Guest]

With 16 pre-selected consonants and 4 vowels, one could construct 2^10 unique words, or more specifically, all combinations of 10 ball words. If each of 10 prisoners only looked at 10 balls, they could convey the whole sequence in Consonant-Vowel-Consonant words guaranteed to be pronouncable and monosyllabic.

It could easily be done with fewer than 10 prisoners without getting too complex. Since the words are spoken, it's the sound of the words that's most important, and there are 42 phonemes in spoken English vs only 26 letters, giving more room to play.

Let 0 = no ball.

Let 1 = ball.

000 Short A 100 Long A
001 Short E 101 Long E
010 Short I 110 Long I
011 Short O 111 Long O

Consonants:
0000 B
0001 CH
0010 D
0011 F
0100 G (hard)
0101 H
0110 J
0111 K
1000 L
1001 M
1010 N
1011 P
1100 R
1101 T
1110 V
1111 Z

Vowels:

I used CH for C (to distinguish from K or S)

I omitted Q because words like PIQuS would be difficult as monosyllabic.

I omitted W because it's too subtle at the end of words (ROW too much like ROH)

I omitted X because it was too close to KS.

I omitted all vowels and the letter Y

I omitted S because I want to use it for an additional code.

Given the above, one can construct a 4-bit + 3-bit + 4-bit word matching a Cons-Vowel-Cons pattern.

For example, if the prisoner's set of 11 balls is 10010110010, his word would be 1001 + 011 + 0010, translated to MOD. The sequence 00000000000 would translate to BAB. 10101010101 would be pronounced NEEH (N + long E + H).

So, 9 prisoners could easily convey 99 balls. If the 9th prisoner added an "S" to his word if the 100th jar held a ball or left it out if it didn't, that would encode all 100 Jars in 9 prisoners.