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

My second try is also flawed.... there are, of course, 100 cups not 75. I still think some way of combining 2 prisoners' or 3 prisoners' words (16 possibilities or 64) will give the required information.

Coding information if 3 prisoners' words are used will be complicated ......

Edited May 23, 2009 by donjar

[Guest]

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.

... but I can't seem to make this work to guarantee success.

Brain=1

Teasers=01

Forum=001

Rules=000

Silence=000000

Scenarios:

1. Balls in jars [1-24, 100].

That would cost 24 Brains, 9 Silences, 1 Forum, 1 Teasers, 1 Brain

2. Repeating "0001" 24 times, plus random placement of 1 ball in remainder:

(Rules + Brain) x 24 would use up 48 prisoners and we only had 39.

This is a tough nut, bushindo!

[superprismatic]

There is a sure way to do it, but it's pretty geeky!

There are 242,519,269,720,337,121,015,504 ways to place 25 balls under 100 jars. That 24-digit number can be written as a 78-bit binary number. So, you can give each combination of 25 balls under 100 urns a serial number which is 78 bits long. That's 2-bits for each of the 39 prisoners. So each prisoner can have 2 bits out of this 78 bit number. There are 4 possibilities for each 2 bit chunk -- 00, 01, 10, and 11. They must agree on which words represent which 2-bit chunks. So, now the 40th prisoner can reconstruct the 78-bit serial number and reconstruct the room A combination of balls under the urns in his room B. This proves that they *can* solve the problem and live. There might be a more elegent procedure, though!

[Guest]

There is a sure way to do it, but it's pretty geeky!

There are 242,519,269,720,337,121,015,504 ways to place 25 balls under 100 jars. That 24-digit number can be written as a 78-bit binary number. So, you can give each combination of 25 balls under 100 urns a serial number which is 78 bits long. That's 2-bits for each of the 39 prisoners. So each prisoner can have 2 bits out of this 78 bit number. There are 4 possibilities for each 2 bit chunk -- 00, 01, 10, and 11. They must agree on which words represent which 2-bit chunks. So, now the 40th prisoner can reconstruct the 78-bit serial number and reconstruct the room A combination of balls under the urns in his room B. This proves that they *can* solve the problem and live. There might be a more elegent procedure, though!

Nice proof! I'd hate to be the prisoner responsible for determining whether I correctly arranged the sequence matching combination # 163,447,025,868,423,990,237,116 ... but it's encouraging to know that a theoretical solution exists.

[plasmid]

There is a sure way to do it, but it's pretty geeky!

There are 242,519,269,720,337,121,015,504 ways to place 25 balls under 100 jars. That 24-digit number can be written as a 78-bit binary number. So, you can give each combination of 25 balls under 100 urns a serial number which is 78 bits long. That's 2-bits for each of the 39 prisoners. So each prisoner can have 2 bits out of this 78 bit number. There are 4 possibilities for each 2 bit chunk -- 00, 01, 10, and 11. They must agree on which words represent which 2-bit chunks. So, now the 40th prisoner can reconstruct the 78-bit serial number and reconstruct the room A combination of balls under the urns in his room B. This proves that they *can* solve the problem and live. There might be a more elegent procedure, though!

I'll work with a set of 25 jars holding 5 balls so this can appear as a single row in the window (and because I'm too lazy to type a lot) but this can be expanded to 100 jars with 25 balls.

The configuration where all balls are in the last 5 jars (like so) will be state 1.

OOOOOOOOOOOOOOOOOOOOXXXXX

State N+1 is reached by taking the first ball in the series and decreasing its position by 1, so state 2 would be

OOOOOOOOOOOOOOOOOOOXOXXXX

state 3 is

OOOOOOOOOOOOOOOOOOXOOXXXX

etc. until you reach state 21

XOOOOOOOOOOOOOOOOOOOOXXXX

If the first ball is in jar #1, then to reach state N+1: remove the first ball, move the second ball down one position, and place the first ball in the position immediately before the second. So state 22 would be

OOOOOOOOOOOOOOOOOOOXXOXXX

Then follow the preceding rule again (where the first ball is not in jar #1) so state 23 is

OOOOOOOOOOOOOOOOOOXOXOXXX

Once you reach the state with multiple balls in a row at the lowest jars like so

XXOOOOOOOOOOOOOOOOOOOOXXX

Then to reach state N+1: remove all consecutive balls from the lowest jars, move the lowest remaining ball down by one jar, and place the removed balls in the jars immediately before the one that was moved. So next would be

OOOOOOOOOOOOOOOOOOOXXXOXX

For the case of 25 balls in 100 jars, each of the 100C25 = 100! / (25! x 75!) = 242519269720337121015504 possible arrangements has a unique number. Now the 39 prisoners each calculate the number that represents the state, and calculate what that number is in base 4. (The number will be representable with a 39 digit number in base 4 because 4^39 = 302231454903657293676544). Assign the words: Brain = 0, Teasers = 1, Forum = 2, Rules = 3. Then have the Nth prisoner go to the other room and say the word corresponding to the Nth digit of the base 4 number representing the state. The 40th prisoner (the one in room B) then calculates which state that number represents and places the balls.

Of course the problem with this approach is that I don't know of any quick way of seeing an arrangement of the balls and transforming that into a state number: this might take a very long time to implement! If someone can think of a way to calculate the state number quickly, or a better way of numbering the states, the prisoners would much appreciate it.

BTW Bushindo, if you don't want people using "silence" as a fifth possible means of communication, you'd better tell everyone.

[Guest]

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

No

[bushindo]

BTW Bushindo, if you don't want people using "silence" as a fifth possible means of communication, you'd better tell everyone.

I'll work with a set of 25 jars holding 5 balls so this can appear as a single row in the window (and because I'm too lazy to type a lot) but this can be expanded to 100 jars with 25 balls.

The configuration where all balls are in the last 5 jars (like so) will be state 1.

OOOOOOOOOOOOOOOOOOOOXXXXX

State N+1 is reached by taking the first ball in the series and decreasing its position by 1, so state 2 would be

OOOOOOOOOOOOOOOOOOOXOXXXX

state 3 is

OOOOOOOOOOOOOOOOOOXOOXXXX

etc. until you reach state 21

XOOOOOOOOOOOOOOOOOOOOXXXX

If the first ball is in jar #1, then to reach state N+1: remove the first ball, move the second ball down one position, and place the first ball in the position immediately before the second. So state 22 would be

OOOOOOOOOOOOOOOOOOOXXOXXX

Then follow the preceding rule again (where the first ball is not in jar #1) so state 23 is

OOOOOOOOOOOOOOOOOOXOXOXXX

Once you reach the state with multiple balls in a row at the lowest jars like so

XXOOOOOOOOOOOOOOOOOOOOXXX

Then to reach state N+1: remove all consecutive balls from the lowest jars, move the lowest remaining ball down by one jar, and place the removed balls in the jars immediately before the one that was moved. So next would be

OOOOOOOOOOOOOOOOOOOXXXOXX

For the case of 25 balls in 100 jars, each of the 100C25 = 100! / (25! x 75!) = 242519269720337121015504 possible arrangements has a unique number. Now the 39 prisoners each calculate the number that represents the state, and calculate what that number is in base 4. (The number will be representable with a 39 digit number in base 4 because 4^39 = 302231454903657293676544). Assign the words: Brain = 0, Teasers = 1, Forum = 2, Rules = 3. Then have the Nth prisoner go to the other room and say the word corresponding to the Nth digit of the base 4 number representing the state. The 40th prisoner (the one in room B) then calculates which state that number represents and places the balls.

Of course the problem with this approach is that I don't know of any quick way of seeing an arrangement of the balls and transforming that into a state number: this might take a very long time to implement! If someone can think of a way to calculate the state number quickly, or a better way of numbering the states, the prisoners would much appreciate it.

You know, this forum has taught me that no matter how tightly you think you worded your problem, someone always manage to find a leak somewhere. It has already been shown that this problem is solvable with only 4 words (no silence allowed). Allowing silence will only make the problem easier. Solve whichever you like.

So far we know that there are about 2.4*10²³ possible permutation of 25 balls in 100 jars. If we think about converting the permutation into a binary number (let no ball = 0, let ball = 1, and then you'll have a 100-digit binary number), that would means that system would map to 2.4*10²³ unique different numbers ranging between 0 and 2¹⁰⁰ = 1.2*10³⁰.

What the prisoners can do is write down all 2.4*10²³ unique 100-digit binary numbers, and sort them. So, when a prisoner encounter any configuration of jar, convert that into a 100-digit binary number and look it up in the sorted list. Convert its index position in the list into a 39-digit number in base 4. Communicate that to the prisoner in room B, who reconstruct the index position and looks up the configuration in the sorted list.

This numbering system only works in theory. The sizes are simply too staggering to do in real situation. What I'm thinking is that this is a low entropy situation, meaning that it can be readily compressed. Previous approaches tend to ignore the information that there are only 25 balls, so the solutiosn inevitably run into problems. Having 25 balls in 100 means that there will be long stretches of 0's, and certain patterns are more likely than others. Phatfingers had the right idea before with representing certain patterns with numbers. That idea of compression, i'm sure, can offer a good balance between feasibility and effectiveness if refined.

[plasmid]

BTW Bushindo, if you don't want people using "silence" as a fifth possible means of communication, you'd better tell everyone.

I'll work with a set of 25 jars holding 5 balls so this can appear as a single row in the window (and because I'm too lazy to type a lot) but this can be expanded to 100 jars with 25 balls.

The configuration where all balls are in the last 5 jars (like so) will be state 1.

OOOOOOOOOOOOOOOOOOOOXXXXX

State N+1 is reached by taking the first ball in the series and decreasing its position by 1, so state 2 would be

OOOOOOOOOOOOOOOOOOOXOXXXX

state 3 is

OOOOOOOOOOOOOOOOOOXOOXXXX

etc. until you reach state 21

XOOOOOOOOOOOOOOOOOOOOXXXX

If the first ball is in jar #1, then to reach state N+1: remove the first ball, move the second ball down one position, and place the first ball in the position immediately before the second. So state 22 would be

OOOOOOOOOOOOOOOOOOOXXOXXX

Then follow the preceding rule again (where the first ball is not in jar #1) so state 23 is

OOOOOOOOOOOOOOOOOOXOXOXXX

Once you reach the state with multiple balls in a row at the lowest jars like so

XXOOOOOOOOOOOOOOOOOOOOXXX

Then to reach state N+1: remove all consecutive balls from the lowest jars, move the lowest remaining ball down by one jar, and place the removed balls in the jars immediately before the one that was moved. So next would be

OOOOOOOOOOOOOOOOOOOXXXOXX

For the case of 25 balls in 100 jars, each of the 100C25 = 100! / (25! x 75!) = 242519269720337121015504 possible arrangements has a unique number. Now the 39 prisoners each calculate the number that represents the state, and calculate what that number is in base 4. (The number will be representable with a 39 digit number in base 4 because 4^39 = 302231454903657293676544). Assign the words: Brain = 0, Teasers = 1, Forum = 2, Rules = 3. Then have the Nth prisoner go to the other room and say the word corresponding to the Nth digit of the base 4 number representing the state. The 40th prisoner (the one in room B) then calculates which state that number represents and places the balls.

Of course the problem with this approach is that I don't know of any quick way of seeing an arrangement of the balls and transforming that into a state number: this might take a very long time to implement! If someone can think of a way to calculate the state number quickly, or a better way of numbering the states, the prisoners would much appreciate it.

Here's a way of calculating numbers before the sun burns out.

On further consideration, here's a way it could be performed reasonably quickly (if they have access to a scientific calculator). I'm revising my numbering system so the state number starts at zero (for the state where all 25 balls are in jars #76-100) instead of starting at one.

The position of ball #25 (the one in the highest numbered jar) is pretty easy.

Suppose it's in jar #100. Then all of the 24 other balls can be arranged in the 99 other jars in 99C24 = 99! / (24! x 75!) = 60629817430084280253876 different possible ways, so if the state number is less than 60629817430084280253876 then the last ball is in jar #100.

Suppose ball #25 is in jar #99. We know the first state with ball #25 in jar #99 is state 99C24, and we know that there are 98C24 = 98! / (24! x 74!) ways to arrange the other 24 balls in the remaining 98 jars, so the state number must be greater than or equal to 99C24 but less than 99C24 + 98C24.

Continuing along these lines, find the largest n such that the state number is less than 99C24 + 98C24 + 97C24 + ... + nC24, and ball #25 will be in jar n+1.

Now for ball #24. Since we know which jar ball #25 is in and we know that all of the other balls must be in the preceding jars, I'll define j as the number of jars left to deal with after ball #25 has been placed, and I'll define s(25) as the smallest state number that is consistent with this position of ball #25 (i.e. it's a number of the form 99C24 + 98C24 + 97C24 + ... + nC24), and I'll define the corrected state number for ball #24 as c(24) = state number - s(25).

We can work with this corrected state number using a procedure much like the one above for ball #25. Since s(25) is the first state consistent with ball #25's position, we know that it has all 24 remaining balls in jars #j-23 to #j. If ball #24 is in jar #j, then there are (j-1)C23 ways of arranging the other 23 balls in the preceding (j-1) jars, so c(24) is less than (j-1)C23. If ball #24 is in jar (j-1), then c(24) is greater than or equal to (j-1)C23 but less than (j-1)C23 + (j-2)C23.

Continuing along those lines, find the largest n such that the state number is less than (j-1)C23 + (j-2)C23 + ... + (j-n)C23, and ball #24 will be in jar n+1.

That's the method behind my madness. Now for the implementation.

Given a state number, to transform it to the positions of the balls: First calculate the position of ball #25 by finding the largest n such that the state number < 99C24 + 98C24 + 97C24 + ... + nC24, and place ball #25 in jar n+1 and call this jar j(25). Subtract this sum of combinations from the state number to get a corrected state number c(24). Then calculate the position of ball #24 by finding the largest n such that the c(24) < (j(25)-1)C23 + (j(25)-2)C23 + ... + (j(25)-n)C23, and place ball #24 in jar n+1 and call this jar j(24). Subtract this sum of combinations from the corrected state number c(24) to get the corrected state number c(23). In general, to calculate the position of ball #m after the positions of the greater numbered balls have been determined, find the largest n such that c(m) < (j(m+1)-1)C(m-1) + (j(m+1)-2)C(m-1) + ... + (j(m+1)-n)C(m-1), and place ball #m in jar n+1 and call that jar j(m) and calculate c(m-1) = c(m) minus the sum of combinations.

Given a set of positions of balls, to convert it to a state number: Start with state 0. If ball #25 is NOT in jar #100, then add 99C24 to the state number. Then if ball #25 is not in jar #99, add another 98C24 to the state number. Continue doing so until you specify the position of ball #25 (in jar j(25)). Now, if ball #24 is NOT in jar (j(25)-1) then add (j(25)-2)C23 to the running state number total, and if ball #24 is not in jar (j(25)-2) then add another (j(25)-3)C23 to the running state number total, etc until you specify the position of ball #24. In general, for ball #m, if it is not in jar (j(m+1)-1) then add (j(m+1)-2)C(m-1), and if it not in jar (j(m+1)-2) then add (j(m+1)-3)C(m-1), etc. until its position is specified.

It's not SUPER fast, but should be doable in a reasonable number of calculations if you've got a calculator that can handle large numbers.

Edited May 23, 2009 by plasmid

[Guest]

Anyone see anything wrong with how I did it? I know its confusing, but I think it might work, and would be alot easier than calculating huge numbers.

post #26

Edited May 23, 2009 by James8421

[bushindo]

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.

With any random number of balls in the 100 jars, the possible number of configurations are 2¹⁰⁰ = 1.267651 * 10³⁰. If you try to uniquely identify all configurations made by putting any number of balls randomly in 100 jars, it won't be possible since 39 prisoners can only convey 4³⁹ = 3.02 * 10²³ configurations.

The key to this is to use the piece of information that there are 25 balls. That can drastically cut down the possible number of configurations to within the range uniquely identifiable by the 39 prisoners.

Edited May 23, 2009 by bushindo

[plasmid]

With any random number of balls in the 100 jars, the possible number of configurations are 2¹⁰⁰ = 1.267651 * 10³⁰. If you try to uniquely identify all configurations made by putting any number of balls randomly in 100 jars, it won't be possible since 39 prisoners can only convey 4³⁹ = 3.02 * 10²³ configurations.

The key to this is to use the piece of information that there are 25 balls. That can drastically cut down the possible number of configurations to within the range uniquely identifiable by the 39 prisoners.

True, but James did something rather clever: not all the prisoners are identical. Apparently, he's assuming that the prisoners can go in whatever order they wish, and the identity of the prisoner going into room B carries some information. I haven't calculated how much more information he gets with that approach, though... I'm sorry, but I can't totally follow how the implementation would work as it's currently stated.

[Guest]

With any random number of balls in the 100 jars, the possible number of configurations are 2¹⁰⁰ = 1.267651 * 10³⁰. If you try to uniquely identify all configurations made by putting any number of balls randomly in 100 jars, it won't be possible since 39 prisoners can only convey 4³⁹ = 3.02 * 10²³ configurations.

The key to this is to use the piece of information that there are 25 balls. That can drastically cut down the possible number of configurations to within the range uniquely identifiable by the 39 prisoners.

The problem I'm having is that when attempting to divide and conquer, the 1:4 ratio goes away. I tried encoding "repeat x" and allowing the next prisoner to define "x" based on prior patterns. That worked most of the time, but I could always contrive a scenario that proved too expensive to compress. I came up with 2 test cases that were sufficient in combination to fail most of my attempts at compression-based solutions. Maybe they'll be useful for others as well.

Case 1:

00010101011000000010000000101010010001000001000001

00100010001000100100011100001000000011000000010000

Case 2:

10100100010000100000100000010000000100000000100000

00001110000000100000010000010000100010010111111100

[bushindo]

True, but James did something rather clever: not all the prisoners are identical. Apparently, he's assuming that the prisoners can go in whatever order they wish, and the identity of the prisoner going into room B carries some information. I haven't calculated how much more information he gets with that approach, though... I'm sorry, but I can't totally follow how the implementation would work as it's currently stated.

That is true. If we simplify James' approach by assuming that each prisoner can carry one more binary bit of information (high or low), then the possible configurations identifiable are 2*4³⁹ = 6.04 * 10²³, which is still far short of the unrestricted number of configuration 2¹⁰⁰, since the approach doens't use the information about the 25 balls.

There also is an issue with how this is implemented. Each prisoner is divided into groups of high or low, and then each prisoner takes a group of 3 jars. Assuming the prisoners can go in any order they like, there is an issue of how each prisoner is supposed to convey to prisoner B which 3 jars they cover. Remember that each prisoner does not know the configuration until it is their turn to see the jars.

[bushindo]

The problem I'm having is that when attempting to divide and conquer, the 1:4 ratio goes away. I tried encoding "repeat x" and allowing the next prisoner to define "x" based on prior patterns. That worked most of the time, but I could always contrive a scenario that proved too expensive to compress. I came up with 2 test cases that were sufficient in combination to fail most of my attempts at compression-based solutions. Maybe they'll be useful for others as well.

Case 1:

00010101011000000010000000101010010001000001000001

00100010001000100100011100001000000011000000010000

Case 2:

10100100010000100000100000010000000100000000100000

00001110000000100000010000010000100010010111111100

I think the issue here is that an optimal encoding algorithm on average can only compress this down to a 39-digit base-4 number. This limit is specified by the shannon information theory, and only the most optimal compression algorithm can approach it. Less optimal algorithm will result in longer encoded sequence, meaning that we need more than 39 prisoners.

The issue is that the "repeat x" approach (also known as run-length encoding) is not an optimal encoding algorithm, and thus generally will require more than 39 prisoners to express the jar configuration. I expect that it will work on some cases, but certainly not all.

[Guest]

I figured if they just do 3 jars at a time, there would be 8 combinations possible for B,N,N..B,B,B...ect. Call each combo a number 1-8. Assign 2 numbers to each of the 4 words, like the way I showed. Now have 16 P represent the lower numbered combos and 16 P be the higher ones. If you have more of the high combos than low combos, or the other way around, then you send in a guy that will have a word that lets PB know the representation of the prisoners has changed. Out of only 25 balls I doubt that would happen, considering your taking 3 jars per word said. I'll try an example of what I mean.

3J=8 possible combos. Number each one 1-8.

B B B=1

B B N=2

B N N=3

N N N=4

N B N=5

B N B=6

N N B=7

N B B=8

Give each word 2 numbers like this:

BRAIN= 1 5

TEASER= 2 6

FORUM= 3 7

RULE= 4 8 (SO EACH WORD HAS 1-4 AND 5-8)

Now the night before you could determine 16 guys who, when they say a word, it will mean the lower of the 2 number combos on that word. And same for 16 guys who will be the higher number. All together taking care of 3J each for 96 jars.

So they open all the jars and determine which order they go to talk to Prisoner B.

Example: If Ted has low number when he says a word, and John has high number when he says a word:

Jars 1-3 go: B,N,N, that is combo #3 from above. It is also the word Forum. So Ted goes to Prisoner B and says Forum, and prisoner B knows that Ted is one of the low number guys, he also knows Forum has combo #3, thus he knows the order of the first 3 Jars.

Jars 4-6 go: N,N,B Thats combo #7 from above. It is also the word Forum. But this time its the higher of the 2, so now one of the 16 higher numbers guys could go in, in this case John. John goes to Prisoner B and says Forum, PB knows John is a high number guy, he also knows Forum is also combo #7, thus he knows the order of Jars 4-6.

Just keep going until jars 1-96 are taken care of. I don't see any problems with that, even if all 25 balls are somewhere in the first 96 jars. You should be able to take care of it.

Now the night before all this, you need to establish 2 guys that are responsible for the last 4 Jars. If they take on two jars each, thats 4 possible combos, simply attach them to the 4 words, and the last 4 jars would be easy.

That leaves 5 guys. They will represent nothing, and simply come and say the same word each. Or if you need to switch around what the 2 sets of 16 men represent (high or low ) They could be used for that to let PB know that it has been changed, But I think it can be done without.

Is that still incorrect? I can't see where I went wrong, could someone help explain?

EDIT:

Nevermind I saw your earlier post, you're right Prisoners in A would have to communicate with each other somehow to determine the order. I must have been thinking they could.

Edited May 23, 2009 by James8421

[Guest]

All these Prisoners on death row are putting my Brain on death row!!

Edited May 23, 2009 by James8421

[plasmid]

That is true. If we simplify James' approach by assuming that each prisoner can carry one more binary bit of information (high or low), then the possible configurations identifiable are 2*4³⁹ = 6.04 * 10²³, which is still far short of the unrestricted number of configuration 2¹⁰⁰, since the approach doens't use the information about the 25 balls.

There also is an issue with how this is implemented. Each prisoner is divided into groups of high or low, and then each prisoner takes a group of 3 jars. Assuming the prisoners can go in any order they like, there is an issue of how each prisoner is supposed to convey to prisoner B which 3 jars they cover. Remember that each prisoner does not know the configuration until it is their turn to see the jars.

I think James is on a reasonable track, although he has yet to prove that there aren't any situations in which his approach might fail. If EACH of the 39 prisoners would carry an extra bit of information, the total number of possibilities would be 2³⁹ * 4³⁹ = 2¹¹⁷, which is greater than 2¹⁰⁰.

The only thing he has left to prove is that there aren't any arrangements of balls where you would need to have a total of more than 16+5 prisoners representing either "high" or "low" combinations. (I'm not convinced that it's true myself, and until then I'm claiming that my solution on post #34 is the only proven one so far, although an easier implementation with a more elegant answer would be desirable.)

[Guest]

The only thing he has left to prove is that there aren't any arrangements of balls where you would need to have a total of more than 16+5 prisoners representing either "high" or "low" combinations. (I'm not convinced that it's true myself, and until then I'm claiming that my solution on post #34 is the only proven one so far, although an easier implementation with a more elegant answer would be desirable.)

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

Edited May 23, 2009 by James8421

[Guest]

im vaguely confused are we saying the only one that works is prismatic (unless im wrong i think that is what plasmid is using too)

and for james saying you dont think prisoners could reasonabley do this i think the only purpose of the prisoner thing is to provide a concrete example the real problem is you have two methods

one that looks at the jars and passes one of five words to the main method and only has temp variables (each method call all info not hard coded is lost)

and then the main method that calls the other method 39 times and gets one of 5 words as return

thats how understand it anyway, thats y u can assume each prisoner has perfect memory and infinite intelligence

otherwise we probably couldnt assume that each prisoner could remember 4 words

anyway i didnt check the math to be honest but as long as its right i think prismatic has it tho i doubt thats what bushindo was fishin for

[bushindo]

I figured if they just do 3 jars at a time, there would be 8 combinations possible for B,N,N..B,B,B...ect. Call each combo a number 1-8. Assign 2 numbers to each of the 4 words, like the way I showed. Now have 16 P represent the lower numbered combos and 16 P be the higher ones. If you have more of the high combos than low combos, or the other way around, then you send in a guy that will have a word that lets PB know the representation of the prisoners has changed. Out of only 25 balls I doubt that would happen, considering your taking 3 jars per word said. I'll try an example of what I mean.

3J=8 possible combos. Number each one 1-8.

B B B=1

B B N=2

B N N=3

N N N=4

N B N=5

B N B=6

N N B=7

N B B=8

Give each word 2 numbers like this:

BRAIN= 1 5

TEASER= 2 6

FORUM= 3 7

RULE= 4 8 (SO EACH WORD HAS 1-4 AND 5-8)

Now the night before you could determine 16 guys who, when they say a word, it will mean the lower of the 2 number combos on that word. And same for 16 guys who will be the higher number. All together taking care of 3J each for 96 jars.

So they open all the jars and determine which order they go to talk to Prisoner B.

Example: If Ted has low number when he says a word, and John has high number when he says a word:

Jars 1-3 go: B,N,N, that is combo #3 from above. It is also the word Forum. So Ted goes to Prisoner B and says Forum, and prisoner B knows that Ted is one of the low number guys, he also knows Forum has combo #3, thus he knows the order of the first 3 Jars.

Jars 4-6 go: N,N,B Thats combo #7 from above. It is also the word Forum. But this time its the higher of the 2, so now one of the 16 higher numbers guys could go in, in this case John. John goes to Prisoner B and says Forum, PB knows John is a high number guy, he also knows Forum is also combo #7, thus he knows the order of Jars 4-6.

Just keep going until jars 1-96 are taken care of. I don't see any problems with that, even if all 25 balls are somewhere in the first 96 jars. You should be able to take care of it.

Now the night before all this, you need to establish 2 guys that are responsible for the last 4 Jars. If they take on two jars each, thats 4 possible combos, simply attach them to the 4 words, and the last 4 jars would be easy.

That leaves 5 guys. They will represent nothing, and simply come and say the same word each. Or if you need to switch around what the 2 sets of 16 men represent (high or low ) They could be used for that to let PB know that it has been changed, But I think it can be done without.

Is that still incorrect? I can't see where I went wrong, could someone help explain?

EDIT:

Nevermind I saw your earlier post, you're right Prisoners in A would have to communicate with each other somehow to determine the order. I must have been thinking they could.

James' method is very inventive, I'll have to give him prop for thinking out of the box. However, the method assumes that the prisoners from can communicate with one another. It also fails for cases where the configuration requires more than 23 low or high prisoners. Take the following example

Empty, Empty, Ball, Empty, Empty, Ball, Empty, Empty, Ball, Empty, Empty, Ball, ....

Basically, repeat (Empty, Empty, Ball) 25 times in a row. And then do all Empty thereafter. That would require 25 low prisoners. However, as James mentioned, there are some redundancy in the last few prisoners (only 34 prisoners are required to cover 100 jars), and you could push some more information there too.

Overall, I'd say plasmid got this one in the bag. His method could be done within a reasonable amount of time, and guarantee the survival of all. Well done.

[Guest]

What if there are 6 empties, before the next ball? Or, seven? What do they say then?

[Guest]

so just for **** and giggles did you have a solution in mind when you set it up or did you just make the easy problem harder and see if anyone could solve it?

[bushindo]

so just for **** and giggles did you have a solution in mind when you set it up or did you just make the easy problem harder and see if anyone could solve it?

I made the problem was working backwards, basically by computing ₁₀₀C₂₅ and then see what power of 4 would be close enough to it (39, incidentally). The solution i had in mind was along the lines of what I posted in post 33, although I have to say plasmid surprised me with a solution that is actually could be accomplished by the prisoners before the sun burns out.

This is why i love posting problem on this board. Time and time again the board members surprised me with a novel solution, or approaches that go deeper than my own. Reading these solutions help me learn a lot. Posting them also helps me clarify concepts in my mind. This problem, for instance, clarified the theoretical framework behind shannon's information theory. If shannon had access to this board, he would have done more with his career, I'm sure.

Edited May 24, 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.

I have not read all the post yet but did anyone think of....

brain = ball - no ball

teaser = no ball - ball

forum = ball - ball

rules = no ball - no ball - ball

silence = no ball - no ball - no ball

same idea but more combo's if you also use combined words s/a:

brain brain

brain teaser

brain forum

brain rules

brain silence

teaser brain

teaser teaser

teaser forum

etc......

get it?

you almost have a whole new language

[Guest]

If a prisoner has shoes on consider 'ball' and if he does not consider 'no ball'. So three prisoners can cover 8 jars. In this way you need even less that 40 prisoners. I guess this is only valid if prisoners are not blindfolded.

no shoes brain = no ball - no ball - no ball

no shoes teaser = no ball - no ball - ball

no shoes forum = no ball - ball - no ball

no shoes rules = no ball - ball - ball

with shoes brain = ball - no ball - no ball

with shoes teaser = ball - no ball - ball

with shoes forum = ball - ball - no ball

with shoes rules = ball - ball - ball