[bushindo]

There are two friends in prison. The warden offers them a chance to live through a game. The game is as follows: tomorrow, the warden will put one friend into room A , which contains 8 balls lined up in a row, each of which is either red or black. He will put the other friend in another room, call it room B, with 8 red balls and 8 black balls. The task is for the the friend in room A to communicate the arrangement of the 8 colored balls in his room to the other friend. If the friend in room B can successfully reconstruct the 8-balls arrangement in room A, both will win their freedom. Otherwise, they forfeit their lives.

There's a catch to this. The friend in room A has to communicate with the person in room B via messengers. The warden will only put 16 messengers in room A, and each messenger can only be instructed to either say 'Black' or 'Red'. It is known that of the 16 messengers, 14 are truth tellers (always correctly convey the message that friend A will send), and 2 are random speakers (will randomly say 'Black' or 'Red' to friend B, regardless of what he is instructed by friend A).

Each of the 16 messengers can only be sent once, and the two friends will not know which messenger is a truth teller, and which is a random speaker. Attempting to figure out which messenger is the truth teller/random speaker is not allowed. Assume that each messenger will only convey only 1 bit of information-'Red' or 'Black'- (so please rule out instructing the messenger to walk fast/slow, talk in high/low voice, sending the messengers in some order depending on their heights, etc. ).

The prisoners are told all the rules of the game as above. They have 1 night to plan a strategy. Please help them determine a strategy that is guaranteed to win the game.

Edited December 6, 2010 by bushindo

[Guest]

I think I have an answer, but it's a difficult for me to explain:

To help understand the general logic, consider the simpler problem of just 1 random messenger in the sixteen. The strategy in this case would be as follows:

Messenger 1: Communicates the colour of ball 1

Messenger 2: Says “black” if ball 1 and 2 are the same colour, or “red” if they are different

Messenger 3: Communicates the colour of ball 2

Messenger 4: Says “black” if ball 2 and 3 are the same colour, or “red” if they are different

Etc...

So the “odd” messengers directly communicate ball colour, whereas the “even” messengers communicate redundant reference information. Note that messenger 16 would compare the colour of ball 8 with ball 1 so as to complete the circle.

After player B has all 16 messages, he then calculates the “consistency” of each link, based on sets of three. So the first set of three will be messages 1,2, and 3, and the set has the value “True” if message 2 correctly links the messages 1 and 3, or “False” if the link is incorrect. The next “set of 3” consists of messages 3,4, and 5, and so on, till the last set compares messages 15, 16, and 1.

After evaluating all sets, if there are no “false” sets, then the random messages communicated the correct values, and we can simply rely on the messages from the “odd” messengers. If there is one false set, then the random message was incorrectly sent by the “even” messenger in that set, so we can still rely on all messages from the odd” messengers. If there are two false sets, then the one “odd” message in common between those sets will be the false message from the random messenger.

This was for 1 random messenger, just to explain the concept and define some labels. For 2 random messengers:

The communication strategy is exactly the same as the 1 random messenger problem above, but the interpretation is more complex. In addition to evaluating each set of three, player B also evaluates each set of 5 messages (i.e. the next two “even” messengers). So the first set of five will be messages 1,2,3,4 and 5, and this set will be “True” if message 2 is consistent with messages 1 and 3, AND message 4 is consistent with messages 3 and 5. If either message 2 or 4 (or both) are inconsistent, then the entire set of 5 is labelled “False”. The next set of 5 then consists of messages 3,4,5,6, and 7, and so on until messages 15,16,1,2 and 3.

In addition to the sets of 5, we also calculate the value of each set of 3 as per the 1 messenger problem described above.

Now, given that we can essentially think of the message arrangement as circular – there are 21 different relevant positions for the random messengers:

Arrangement 1: Both random messengers tell the truth – all sets of 5 and 3 are “True”

Arrangement 2: Only one messenger lies, and this is an “even” messenger – If the sets of five starting with message X and message X+2 are false, the set of 3 starting with message X+2 is false, and all other sets are true, then messenger X+3 has lied.

Arrangement 3: Only one messenger lies, and this is an “odd” messenger – If both the sets of 5 and sets of 3 starting with messages X and X+2 are false, and all others are true, then messenger X+2 has lied.

Arrangements 4 – 12: The first lying messenger is an “even” messenger, and there is a gap of between 0 and 8 messages between the first and second liars. (As we can consider the arrangement circular, gaps of more than 8 can be ignored).

Arrangements 13 – 21: As above, but the first lying messenger is an “odd” messenger.

For arrangements 4 to 21, I’ve calculated the set values for each, and found that there is a unique combination of sets that describes each arrangement. Hopefully, bushindo can confirm he has the same answer as me and I can get out of typing out the combinations of all 18 arrangements. If not, I’m going to get a lot of typing practice...

Edited December 6, 2010 by rajat_magic

[Guest]

Break the balls down into a binary number. Since there can only be 256 possible combinations, divise a way to communicate the base 10 number represented. I am a bit on the slow side to come up with a full proof way, but I think others can get it no problem. I believe there should be a way to commune the number up to 3 tiimes.

[Guest]

Break the balls down into a binary number. Since there can only be 256 possible combinations, divise a way to communicate the base 10 number represented. I am a bit on the slow side to come up with a full proof way, but I think others can get it no problem. I believe there should be a way to commune the number up to 3 tiimes.

you need to send the number 4 times in order to negate the two random messengers. That would mean conveying all numbers from 0 to 256 using just 4 binary switches. Not sure that's possible...

[Guest]

I think I have an answer, but it's a difficult for me to explain:

To help understand the general logic, consider the simpler problem of just 1 random messenger in the sixteen. The strategy in this case would be as follows:

Messenger 1: Communicates the colour of ball 1

Messenger 2: Says “black” if ball 1 and 2 are the same colour, or “red” if they are different

Messenger 3: Communicates the colour of ball 2

Messenger 4: Says “black” if ball 2 and 3 are the same colour, or “red” if they are different

Etc...

So the “odd” messengers directly communicate ball colour, whereas the “even” messengers communicate redundant reference information. Note that messenger 16 would compare the colour of ball 8 with ball 1 so as to complete the circle.

After player B has all 16 messages, he then calculates the “consistency” of each link, based on sets of three. So the first set of three will be messages 1,2, and 3, and the set has the value “True” if message 2 correctly links the messages 1 and 3, or “False” if the link is incorrect. The next “set of 3” consists of messages 3,4, and 5, and so on, till the last set compares messages 15, 16, and 1.

After evaluating all sets, if there are no “false” sets, then the random messages communicated the correct values, and we can simply rely on the messages from the “odd” messengers. If there is one false set, then the random message was incorrectly sent by the “even” messenger in that set, so we can still rely on all messages from the odd” messengers. If there are two false sets, then the one “odd” message in common between those sets will be the false message from the random messenger.

This was for 1 random messenger, just to explain the concept and define some labels. For 2 random messengers:

The communication strategy is exactly the same as the 1 random messenger problem above, but the interpretation is more complex. In addition to evaluating each set of three, player B also evaluates each set of 5 messages (i.e. the next two “even” messengers). So the first set of five will be messages 1,2,3,4 and 5, and this set will be “True” if message 2 is consistent with messages 1 and 3, AND message 4 is consistent with messages 3 and 5. If either message 2 or 4 (or both) are inconsistent, then the entire set of 5 is labelled “False”. The next set of 5 then consists of messages 3,4,5,6, and 7, and so on until messages 15,16,1,2 and 3.

In addition to the sets of 5, we also calculate the value of each set of 3 as per the 1 messenger problem described above.

Now, given that we can essentially think of the message arrangement as circular – there are 21 different relevant positions for the random messengers:

Arrangement 1: Both random messengers tell the truth – all sets of 5 and 3 are “True”

Arrangement 2: Only one messenger lies, and this is an “even” messenger – If the sets of five starting with message X and message X+2 are false, the set of 3 starting with message X+2 is false, and all other sets are true, then messenger X+3 has lied.

Arrangement 3: Only one messenger lies, and this is an “odd” messenger – If both the sets of 5 and sets of 3 starting with messages X and X+2 are false, and all others are true, then messenger X+2 has lied.

Arrangements 4 – 12: The first lying messenger is an “even” messenger, and there is a gap of between 0 and 8 messages between the first and second liars. (As we can consider the arrangement circular, gaps of more than 8 can be ignored).

Arrangements 13 – 21: As above, but the first lying messenger is an “odd” messenger.

For arrangements 4 to 21, I’ve calculated the set values for each, and found that there is a unique combination of sets that describes each arrangement. Hopefully, bushindo can confirm he has the same answer as me and I can get out of typing out the combinations of all 18 arrangements. If not, I’m going to get a lot of typing practice...

Take an example as below which are the responses of 16 messengers:

1 Black

2 Black

3 Black

4 Black

5 Black

6 Black

7 Black

8 Red

9 Black

10 Black

11 Black

12 Black

13 Black

14 Black

15 Black

16 Black

Now, there could be two possibilities. Either No 8 is the liar or both number 6 & 7 are liars. Your method would not identify which could be the case.

I took the following arrangement into consideration b b b r b b b b

[Guest]

Take an example as below which are the responses of 16 messengers:

1 Black

2 Black

3 Black

4 Black

5 Black

6 Black

7 Black

8 Red

9 Black

10 Black

11 Black

12 Black

13 Black

14 Black

15 Black

16 Black

Now, there could be two possibilities. Either No 8 is the liar or both number 6 & 7 are liars. Your method would not identify which could be the case.

I took the following arrangement into consideration b b b r b b b b

You're right. Sorry about that - found an error in the way my spreadsheet was handling the circularity of the arrangement. Now that it's corrected, I see that there are actually quite a few combinations that lead to the same output. Back to the drawing board it is...

[Guest]

Can each messenger relay a longer message than just one color each?

There are only 8 balls... Can't the messengers communicate four at a time? This way you can rule out the "mis-informers" by process of elimination.

Let's say it is R R R R R B B B B B

Guy 1: R R R R <-- first four

Guy 2: B B B B <-- second four

Guy 3: R R B R <-- misinformer

Guy 4: B B B B

Guy 5: R R R R

Guy 6: B R B R <-- misinformer

Guy 7: R R R R

Guy 8: B B B B

Guy 9: R R R R

Guy 10: B B B B

Guy 11: R R R R

Guy 12: B B B B

Guy 13: R R R R

Guy 14: B B B B

Guy 15: R R R R

Guy 16: B B B B

[bushindo]

Can each messenger relay a longer message than just one color each?

There are only 8 balls... Can't the messengers communicate four at a time? This way you can rule out the "mis-informers" by process of elimination.

Let's say it is R R R R R B B B B B

Guy 1: R R R R <-- first four

Guy 2: B B B B <-- second four

Guy 3: R R B R <-- misinformer

Guy 4: B B B B

Guy 5: R R R R

Guy 6: B R B R <-- misinformer

Guy 7: R R R R

Guy 8: B B B B

Guy 9: R R R R

Guy 10: B B B B

Guy 11: R R R R

Guy 12: B B B B

Guy 13: R R R R

Guy 14: B B B B

Guy 15: R R R R

Guy 16: B B B B

Unfortunately, the messengers are provided by the warden and may not be sympathetic to your cause. Let's just say that the messengers will strictly obey the warden's instruction, and only will relay a single word, 'Red' or 'Black'. And, in order to preemptively nulify out-of-the-box solution that relies on sending more than 1 bit of message/messenger, let's also say that all 16 messengers are total strangers to the two prisoners, and that all 16 messengers are identical in look, height, gender, etc. except for their persona (truth tellers/random speaker).

Edited December 6, 2010 by bushindo

[wolfgang]

If the man in room A has a red ball,so he`ll send two messengers in a short interval between them(let us say half a Min.).But if he has a black ball,he will wait longer(about one Min.).in this case It makes no difference how many random speakers are there,and he will not listen to what color they said.

It will be like this:

red..red..blavk..red..black..black..black..red(as an example)

so he will send the messengers as follows:

11,11,1....1,11,1....1,1....1,1....1,11

That means each two messengers will code to a certain color

Edited December 6, 2010 by wolfgang

[bushindo]

If the man in room A has a red ball,so he`ll send two messengers in a short interval between them(let us say half a Min.).But if he has a black ball,he will wait longer(about one Min.).in this case It makes no difference how many random speakers are there,and he will not listen to what color they said.

It will be like this:

red..red..blavk..red..black..black..black..red(as an example)

so he will send the messengers as follows:

11,11,1....1,11,1....1,1....1,1....1,11

That's an interesting approach. I tried to preemptively rule out these solutions, which relies on sending more than 1 bit of information per messenger, but I guess I failed in boxing the out-of-the-box solutions. In wolfgang's approach, we're actually sending 2 bit of information per messenger (red/black + short wait/long wait ). I assure you that it is possible to solve the problem when we are only getting 1 bit of information (red/black) per messenger.

[wolfgang]

That's an interesting approach. I tried to preemptively rule out these solutions, which relies on sending more than 1 bit of information per messenger, but I guess I failed in boxing the out-of-the-box solutions. In wolfgang's approach, we're actually sending 2 bit of information per messenger (red/black + short wait/long wait ). I assure you that it is possible to solve the problem when we are only getting 1 bit of information (red/black) per messenger.

by sending them within a planed system,they will act like Morse signals,they`ll bring the informations even if they didn`say anything !

[bushindo]

by sending them within a planed system,they will act like Morse signals,they`ll bring the informations even if they didn`say anything !

I understand that you can append information via many methods: sending them with long/short wait, sending them in some order depending on their height, send them based on some order of their names, beat up the messenger black and blue before sending if the ball is black, and so on. It is important to notice that once we do this, we are sending more than 1-bit of information per messenger, and the solution to the problem is then trivial. The challenge here is to find the non-trivial solution.

Also, notice that your proposed solution (send with long/short wait) assumes that the messengers all walk at the same rate. Whether this is true or not is not specified in the OP, and presumably is not known to the two prisoners as they discuss their strategy during the night. They probably would not want to risk their lives upon the assumption that the messengers walk at the same pace. The non-trivial solution, of course, does not have this short-coming and can guarantee winning regardless of what the messengers' walking rate are.

Edited December 6, 2010 by bushindo

[Guest]

How about this.

The first set of 8 would answer the colour of the corresponding ball. So if the balls were R,R,R,B,B,R,B,R, they would just end up saying the colour of the ball.

The second set of 8 would say R if their ball plus the next ball are the same colour, and B if the ball is not the same colour. The last person would use the last ball and the first ball.

So let's assume that we look at 3 balls to make it easier.

B,R,B

Let's say the first three do not lie. Then let's say the 5th person is lying, they should say B,B,R but instead we get B,R,R

Looking at it if we get a discrepency.

The 5th B says that it should be, B,R,R, but if that were the case, then the 6th person and the 3rd person were lying. So if further on we had another set lying it would look like 4 people were lying. So that must mean that that person was lying.

Hard to explain but it seems like it will work.

[bushindo]

How about this.

The first set of 8 would answer the colour of the corresponding ball. So if the balls were R,R,R,B,B,R,B,R, they would just end up saying the colour of the ball.

The second set of 8 would say R if their ball plus the next ball are the same colour, and B if the ball is not the same colour. The last person would use the last ball and the first ball.

So let's assume that we look at 3 balls to make it easier.

B,R,B

Let's say the first three do not lie. Then let's say the 5th person is lying, they should say B,B,R but instead we get B,R,R

Looking at it if we get a discrepency.

The 5th B says that it should be, B,R,R, but if that were the case, then the 6th person and the 3rd person were lying. So if further on we had another set lying it would look like 4 people were lying. So that must mean that that person was lying.

Hard to explain but it seems like it will work.

You're on the right track, but not quite there yet. This approach is similar to one rajat_magic posted and its shortcoming is pointed out

The methodology can not quite deal with 2 random speakers. If there were only 1 random speaker in the 16 messengers, then this method would be perfect.

Edited December 6, 2010 by bushindo

[k-man]

How about this.

The first set of 8 would answer the colour of the corresponding ball. So if the balls were R,R,R,B,B,R,B,R, they would just end up saying the colour of the ball.

The second set of 8 would say R if their ball plus the next ball are the same colour, and B if the ball is not the same colour. The last person would use the last ball and the first ball.

So let's assume that we look at 3 balls to make it easier.

B,R,B

Let's say the first three do not lie. Then let's say the 5th person is lying, they should say B,B,R but instead we get B,R,R

Looking at it if we get a discrepency.

The 5th B says that it should be, B,R,R, but if that were the case, then the 6th person and the 3rd person were lying. So if further on we had another set lying it would look like 4 people were lying. So that must mean that that person was lying.

Hard to explain but it seems like it will work.

You will see that there is a discrepancy, but you will not know which messenger is not reliable. Effectively, your solution communicates 3 bits of information about each ball:

1) the color of the ball

2) whether the color of the ball is the same as the color of the ball preceding it

3) whether the color of the ball is the same as the color of the ball following it

When all 3 bits point to the same color then you are ok, but when there is a discrepancy you need to be able to use the majority rule to determine the color. For example, 2 bits are saying that it's red, while one bit is saying that it's black. You cannot assume that the majority is correct since you can have 2 unreliable bits, so it's possible that the correct color is black.

Here is an example to make it easier to understand.

First 8 messengers say "Red". Then the 9th and 10th messengers say "Black" and the rest say "Red" again.

There are 2 possible arrangements here

1) all balls are red and 9th and 10th were lying

2) all balls are red except the second ball, in which case the second messenger was lying.

Hope I made this clear.

[Guest]

Question...

Take each ball with them? If not, the only way I can think of is through some sort of double negative, like using two messengers for each ball...

[bushindo]

Question...

Take each ball with them? If not, the only way I can think of is through some sort of double negative, like using two messengers for each ball...

Interesting question . Unfortunately, the messengers can not take the ball with them.

[Guest]

It's a good thing that you ruled out the possibility of communicating in a different manner, like time between people or fast/slow walk. I was just going to say to slap the messenger on the face if it's a red ball...that way it doesn't matter what he says, if his face is red, it's a red ball.

oh well...back to the drawing board.

[Guest]

Can the messengers be instructed based on other variables? For example, can Prisoner #1 tell a messenger "If you see Prisoner #2 has chosen a red ball when you get to the next room, say Red"?

[bushindo]

Can the messengers be instructed based on other variables? For example, can Prisoner #1 tell a messenger "If you see Prisoner #2 has chosen a red ball when you get to the next room, say Red"?

No conditional message allowed, unfortunately.

[araver]

I've given some thought on this and failed once. It still looks possible, but I think resorting to some sort of computer program might be needed to get it right.

For now, my failed attempt:

First assume Black=0, Red=1 in the following. Just makes explaining easier.

In the following, all adition is modulo 2 addition (1+1=0+0=0, 1+0=0+1=1)

Denote bits before the transmission as ai, i=1..16 and the received bits as bi,i=1..16

2 random answerers mean at most 2 flips of the bits during the transmission (0,1 or 2 flips) so there are at most 2 differences (flips) between the sequences a and b.

First part of the transmission (8 bits) is a Hamming (8,4) code (able to correct single errors and detect but not correct double-errors), easy extension of Hamming (7,4).

That is:

a5=a1+a2+a4

a6=a1+a3+a4

a7=a2+a3+a4

a8=a1+a2+a3+a4+a5+a6+a7 (overall parity bit)

This part is able to correct 1 error and detect (but not correct) 2 errors.

Overall cases: 0,1 or 2 flips in the 8-bit sequence.

There are 5 cases:

A) 0 flips - overall parity bit (8th) says 0/2 flips, rest of bits say no error.

B) 1 flip in the first 7 bits - overall parity bit says 1 flip, rest of parity bits detect 1 flip.

C) 1 flip in the last bit - overall parity bit says 1 flip (incorrectly), rest of parity bits say no error.

D) 2 flips in the first 7 bits - overall parity bit says 0/2 flips, rest of parity bits detect 1 flip (incorrectly).

E) 1 flip in the first 7 bits, 1 flip in the last bit - overall parity bit says 0/2 flips, rest of parity bits detect 1 flip.

Cases A,B,C are OK but we cannot distinguish between case D and case E. So, if the overall parity bit says EVEN and the rest of parity bits say 1 error, then we are looking at 2-flips, but we cannot decide where those errors occur.

So from analyzing the first 8 bits received, the receiver can determine that he is in exactly one of the following cases:

case A) a1,a2,a3,a4 can be deduced correctly from the transmission using the parity bits (and at most 2 flips have occured in the last 8 bits of the transmission) OR

case B) 2 errors have occured already, so the last 8 bits are transmitted error-free.

Case B is actually simple if the last 8 bits, when transmitted correctly, can be used to determine by computation the original 8 bit sequence message.

Unfortunately in case A, worst-case, 4-bits have been transmitted correctly but the problem reverts to a sub-problem where 4-bit information must be transmitted in a 8-bit message with 2 possible flips along the way. Which is not possible IMHO.

And rest of my thoughts

The problem doesn't seem likely to be successfully broken in sub-problems so the method of transmission must make at least half of the bits depend on the message bits so that there is no separation of the message in subproblems (since 8-4-2flips sub-problem does not seem to be solvable).

Best thoughts so far:

a1..a8 are actual bits of information.

a9..a16 are parity bits depending only on the actual bits of information - using functions f1..f8.

Because of modulo 2 arithmetic, one can see such a function f(a1,a2,a3,...,a8) as a single-row matrix E.g. (1 1 0 0 0 0 0 0) is f()=a1+a2.

Two thoughts on the parity functions:

- The parity functions SHOULD be circular permutations of the same function to "disperse" the chances of any bit being flipped / equal probability of capturing errors. E.g. previously someone suggested sum of consecutive bits (which doesn't work overall, but it's a good example) - which is function f=(1 1 0 0 0 0 0 0) permuted in a circular way.

- The circular-parity function SHOULD NOT look too symmetrical itself (this is why examples so far don't work).

For any function (row-matrix) denote N(f)=number of 1's in the matrix.

- N(f)=1 means repeating the message. Doesn't work since double flips can occur on the same position

- N(f)=2 doesn't work since it doesn't capture the difference between 1-error (1 parity function error) and 2-errors (the parity function is ok, yet both bits used for that function have been flipped)

I'm going to try with N(f)=3 first, then N(f)=54 (since N(f)=4 also smells as being too "symmetrical").

However, it is hard to prove such a circular-parity function is actually an answer, except for exhaustively show all possibilities.

Edited December 6, 2010 by araver

[bushindo]

I've given some thought on this and failed once. It still looks possible, but I think resorting to some sort of computer program might be needed to get it right.

For now, my failed attempt:

First assume Black=0, Red=1 in the following. Just makes explaining easier.

In the following, all adition is modulo 2 addition (1+1=0+0=0, 1+0=0+1=1)

Denote bits before the transmission as ai, i=1..16 and the received bits as bi,i=1..16

2 random answerers mean at most 2 flips of the bits during the transmission (0,1 or 2 flips) so there are at most 2 differences (flips) between the sequences a and b.

First part of the transmission (8 bits) is a Hamming (8,4) code (able to correct single errors and detect but not correct double-errors), easy extension of Hamming (7,4).

That is:

a5=a1+a2+a4

a6=a1+a3+a4

a7=a2+a3+a4

a8=a1+a2+a3+a4+a5+a6+a7 (overall parity bit)

This part is able to correct 1 error and detect (but not correct) 2 errors.

Overall cases: 0,1 or 2 flips in the 8-bit sequence.

There are 5 cases:

A) 0 flips - overall parity bit (8th) says 0/2 flips, rest of bits say no error.

B) 1 flip in the first 7 bits - overall parity bit says 1 flip, rest of parity bits detect 1 flip.

C) 1 flip in the last bit - overall parity bit says 1 flip (incorrectly), rest of parity bits say no error.

D) 2 flips in the first 7 bits - overall parity bit says 0/2 flips, rest of parity bits detect 1 flip (incorrectly).

E) 1 flip in the first 7 bits, 1 flip in the last bit - overall parity bit says 0/2 flips, rest of parity bits detect 1 flip.

Cases A,B,C are OK but we cannot distinguish between case D and case E. So, if the overall parity bit says EVEN and the rest of parity bits say 1 error, then we are looking at 2-flips, but we cannot decide where those errors occur.

So from analyzing the first 8 bits received, the receiver can determine that he is in exactly one of the following cases:

case A) a1,a2,a3,a4 can be deduced correctly from the transmission using the parity bits (and at most 2 flips have occured in the last 8 bits of the transmission) OR

case B) 2 errors have occured already, so the last 8 bits are transmitted error-free.

Case B is actually simple if the last 8 bits, when transmitted correctly, can be used to determine by computation the original 8 bit sequence message.

Unfortunately in case A, worst-case, 4-bits have been transmitted correctly but the problem reverts to a sub-problem where 4-bit information must be transmitted in a 8-bit message with 2 possible flips along the way. Which is not possible IMHO.

And rest of my thoughts

The problem doesn't seem likely to be successfully broken in sub-problems so the method of transmission must make at least half of the bits depend on the message bits so that there is no separation of the message in subproblems (since 8-4-2flips sub-problem does not seem to be solvable).

Best thoughts so far:

a1..a8 are actual bits of information.

a9..a16 are parity bits depending only on the actual bits of information - using functions f1..f8.

Because of modulo 2 arithmetic, one can see such a function f(a1,a2,a3,...,a8) as a single-row matrix E.g. (1 1 0 0 0 0 0 0) is f()=a1+a2.

Two thoughts on the parity functions:

- The parity functions SHOULD be circular permutations of the same function to "disperse" the chances of any bit being flipped / equal probability of capturing errors. E.g. previously someone suggested sum of consecutive bits (which doesn't work overall, but it's a good example) - which is function f=(1 1 0 0 0 0 0 0) permuted in a circular way.

- The circular-parity function SHOULD NOT look too symmetrical itself (this is why examples so far don't work).

For any function (row-matrix) denote N(f)=number of 1's in the matrix.

- N(f)=1 means repeating the message. Doesn't work since double flips can occur on the same position

- N(f)=2 doesn't work since it doesn't capture the difference between 1-error (1 parity function error) and 2-errors (the parity function is ok, yet both bits used for that function have been flipped)

I'm going to try with N(f)=3 first, then N(f)=54 (since N(f)=4 also smells as being too "symmetrical").

However, it is hard to prove such a circular-parity function is actually an answer, except for exhaustively show all possibilities.

The rest of your thoughts are spot on, araver.

Such a set of parity function exists. However, the search for the parity functions could be greatly simplified if you look at them in a certain way.

[bushindo]

The rest of your thoughts are spot on, araver.

Such a set of parity function exists. However, the search for the parity functions could be greatly simplified if you look at them in a certain way.

I replied too quick. Let me qualify that statement

There exist a set of parity functions f₁(),..., f₈() that makes it possible to solve the problem. However, I wouldn't say that those functions are circular permutation of one another. Such a set of circular-parity function might exist, but my solution doesn't include them. Again, the search for those functions is easier when viewed in a certain framework.

Edited December 7, 2010 by bushindo

[Guest]

put the red balls first then the black balls then send the messengers in order for example RRRRBBBB and then send them again if there is any inconsistancies the guy in room B will be able to spot them out easily

[Guest]

How about this:

The first 8 messengers will represent the 8 bits of real data

The next 4 messengers will parity-check the real data: If 1 and 2 are the same, 9 is Black. If 1 and 2 are different, 9 is Red.

The next 2 messengers will parity-check the original parity-check: If 9 and 10 are the same, 13 is Black. If 9 and 10 are different, 13 is Red.

The next 1 messenger will parity-check the second check (messengers 13 and 14) similar to above.

The final messenger will be equal to messenger #15.

A representation can look like this:

B   B   B   R   B   R   R   B      (real data)

  B       R       R       R        (parity check on real data)

      R               B            (second parity check)

              R                    (third parity check)

              R                    (equal to third parity check)

Say for example that Messenger's #9 and #14 were random and wrong

You would know something is up between messengers #1, #2, and #9. You would see that #13 claims that #9 and #10 are different, so it turns out something is up between those three. Go a level higher and you see something's up with #15 (because #13 is R and #14 is R and wrong, so it should be B). But, #16 should always match #15 if those weren't the liars, so we know #15 is correct. Therefore #13 and #14 should be different and one of them is a liar.

Sorry for the confusing explanation, but I think this works in all the cases I've tried.

Edited December 7, 2010 by seg9585

[bushindo]

How about this:

The first 8 messengers will represent the 8 bits of real data

The next 4 messengers will parity-check the real data: If 1 and 2 are the same, 9 is Black. If 1 and 2 are different, 9 is Red.

The next 2 messengers will parity-check the original parity-check: If 9 and 10 are the same, 13 is Black. If 9 and 10 are different, 13 is Red.

The next 1 messenger will parity-check the second check (messengers 13 and 14) similar to above.

The final messenger will be equal to messenger #15.

A representation can look like this:

B   B   B   R   B   R   R   B      (real data)

  B       R       R       R        (parity check on real data)

      R               B            (second parity check)

              R                    (third parity check)

              R                    (equal to third parity check)

Say for example that Messenger's #9 and #14 were random and wrong

You would know something is up between messengers #1, #2, and #9. You would see that #13 claims that #9 and #10 are different, so it turns out something is up between those three. Go a level higher and you see something's up with #15 (because #13 is R and #14 is R and wrong, so it should be B). But, #16 should always match #15 if those weren't the liars, so we know #15 is correct. Therefore #13 and #14 should be different and one of them is a liar.

Sorry for the confusing explanation, but I think this works in all the cases I've tried.

That was a pretty clear explanation. Some comments,

Suppose that the first 8 messengers represent the state of the 8 balls. Let's say that the two random answerers happen to be in position 1 and 2. If those two flip the states of ball 1 and 2 when reporting to B, then B wouldn't know that anything wrong is going on because the parity bits will all be consistent.