So A escorts them each time.

And while A is out escorting the messengers, he might as well as poke his head in room B and tell his friend what the ball arrangements are. Flawless!

This strategy may give a "little more than 50%" winning chance, but it is still far from the optimal solution.

Well, I see what you're saying.

Modify the decision table as below. Only the bottom half is listed, the top part is similar

Sum       Decision

...

7         Abstain

8         Guess 0

9         Guess 1

10        Abstain

11        Guess 0

12        Guess 1

13        Abstain

14        Guess 0

The winning change is now 2/3. Is that still far from optimal?

Remember:

5. The players do not cheat.

To put the problem another way, all players of the team are housed in separate rooms. Everyone is informed about the colour of all others' caps by an arbiter. There is absolutely no possibility of learning more information than those colours.

How about this strategy

Let's make it easy on ourselves and call the state of the hats 0 and 1.

Every participant look and sum up all the hat state. The sum should be between 0 and 14.

If a participant see a sum that is odd, abstain from guessing.

If a participant see a sum that is 0, 2, 4, or 6, guess that his hat state is 1.

If a participant see a sum that is 8, 10, 12, or 14, guess that his hat state is 0.

This way, the winning rate is about 3/5.

Wow! Good job, Kornrade, but that's one crazy solution! My head is still spinning. Bushindo, is this the solution you had in mind?

I never thought of a solution involving communicating tons of information to the answerers before asking the questions, but if this is allowed then can the problem be solved in 5 questions?

Kornrade's solution involves preparing tables of possible combinations of truth-tellers and assigning the numbers to each combination. The number is then communicated back digit-by-digit. The total number of combinations is 65536 - a 5-digit number. If we prepare a table of all possible combinations of truth-tellers and assign a number to each combination in a way to only use the digits that are less than or equal to the number of truth-tellers in that combination then we can prepare one table with all combinations. The combination number will embed the number of truth-tellers in it, so we don't need to ask the first question. We just give the answerers the table and they communicate back to us the number corresponding to the combination they are standing in.

The only question that I don't have the answer for yet is whether it's possible to represent all combinations using only the digits that are less than or equal to the number of the truth-tellers. For example, combinations with one truth-teller would have numbers 1, 10, 11, 100, 101, etc. assigned to them. These are decimal numbers, not binary. Based on the number of combinations for each number of the truth-tellers it seems that it can be done, but I haven't proven that yet. The complexity here is that once a number is used it cannot be used again. However, the combination number doesn't have to be in the range of 0-65535. It can be in the range of 0-99999.

EDIT: added some more thoughts

Kornrade's answer is what I had in mind when I made the puzzle. Kornrade's truth tellers got it easy; my truth tellers had to do more tons more work by calculating their own combinatorial numbers instead of having the bloody combination sheets handed to them . Nice work on reducing the limit to 5. Excellent job!

Simple logic will guarantee a correct solution and (though unnecessary) reveal the possible false messages.

It doesn't say Prisoner A has to send one at a time or use all the messengers.

It doesn't say Prisoner B has to choose a colour based on what the messengers state.

They just have to devise a "guaranteed" method to communicate colour.

They only need to agree on which colour is conveyed by 1 or 2 messengers entering Room B.

For eg. 1 = Black

2 = Red

If the ball is RED, Prisoner A sends 2 messengers, Regardless of what they say B knows to place a RED ball because there is 2 messengers. If one or both states "Black", Prisoner B will instantly know the message is False because the statement contradicts the fact that 2 messengers were sent.

If the Ball is BLACK, Prisoner A sends 1 messenger, Regardless of what that messenger says B knows to choose a Black ball because there is 1 messenger (and if that one states "Red" it is obviously False because his statement contradicts the fact that 1 messenger was sent.

If all the balls are Black, Prisoner A will only need to send 8 messengers one at a time.

If all the balls are Red, Prisoner A will send all 16 messengers two at a time.

This method is flawless.

I wouldn't say that this is flawless. You're making the implicit assumption that all messengers walk at the same rate. The OP didn't clarify this, so this assumption may or may not be true. If you were one of the prisoner, would you risk your life upon this strategy and its implicit assumption?

Well,

I liked my cyclic idea since intuitively it treats all message bits as equals.

Searched all f's such as N(f)=3 with no success. Found gold when searching functions with N(f)=4. Apparently there's lots of them. Almost every function with N(f)=4 that has two consecutive 1s and the rest of 1's are separated by 0's.

Attached is an excel I used for searching. Colored balls.xls

- Cells A2-H2 are variables (blue), the rest are computed through formulas.

- First table has a1...a8 as message bits and shows the functions f1..f8 below (Each function is the function above left-shifted 1 position circularly)

- a9..a16 are parity bits - each is a function of the message bits E.g. row 1011100010000000 means a9=a1+a3+a4+a5.

- Below are the 137 cases of flips transforming a1..a16 into b1..b16:

1 possibility for 0 flips

16 possibilities of exactly 1 flip

120 possibilities of exactly 2 flips

For each such possibility 1 means bit bi differs from bit ai (so the table actually shows b_i-a_i mod 2)

Again, recomputing the parity bits using b1..b8 as input yields c9..c16. Table below c9..c16 show if these recomputed bits differ from b9..b16 respectively (so the table actually shows c_i-b_i mod 2).

For each of the 137 possibilities this table is computed as follows:

- If the parity bit a_i wasn't flipped (i.e. a_i=b_i) then c_i=b_i (denoted as 0) if an even number of bits (relevant to how parity bit i is computed) are flipped and b_i differs from c_i (denoted 1) if an odd number of bits (relevant to how parity bit i is computed) are flipped.

In other words, each message bit flip gives a difference for the parity bits that take that message bit into account AND two message bit flips cancel each other if they occur in the same parity bit.

- If the parity bit a_i was flipped (i.e. b_i=a_i+1 mod 2) then c_i=b_i (denoted as 0) if an odd number of bits (relevant to how parity bit i is computed) are flipped and b_i differs from c_i (denoted 1) if an even number of bits (relevant to how parity bit i is computed) are flipped.

In other words, if a parity bit was flipped but none of the message bits that compose it were flipped, the effect is seen as a discrepancy of the parity bit. If a parity bit was flipped and exactly one of the message bits that composes them was also flipped, then the flips cancel out each other.

Finally, this table shows which recomputed parity bits differ from the received parity bits. By considering each difference (0/1) as a digit in base 2 a number can be constructed - the error code for that possibility. Since there are 8 parity bits, the error code is a number between 0=00000000 and 255=11111111.

A function is good as long as it gives 137 distinct error codes to the 137 possibilities.

The number of distinct error codes is shown in the big cell - which turns green if there are 137 distinct error codes i.e. a solution.

The function in the file can be written as:

a9  = a1 + a3 + a4 + a5

a10 = a8 + a2 + a3 + a4

a11 = a7 + a1 + a2 + a3

a12 = a6 + a8 + a1 + a2

a13 = a5 + a7 + a8 + a1

a14 = a4 + a6 + a7 + a8

a15 = a3 + a5 + a6 + a7

a16 = a2 + a4 + a5 + a6

The excel can be used (by modifying the blue cells) to search every function and by modifying the parity table to verify any custom function - such as the ones proposed before.

Good work. I'd say araver got it. This puzzle is a logical extension of hamming code, which could correct only 1 error. Here we need to correct 2 errors.

There are 137 possible ways that 0 to 2 errors can occur in a string of 16, so we need to build a parity code of length 8 that will give us a 137 different error message. This is possible because an 8-dimensional vector can encode up to 2⁸ = 256 states. One way to think of searching for the appropriate parity functions that araver mentioned is to resort to linear algebra. Essentially we are looking for a set of sixteen 8-dimensional vectors, the first eight of which are the standard vectors

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]

    1    0    0    0    0    0    0    0

    0    1    0    0    0    0    0    0

    0    0    1    0    0    0    0    0

    0    0    0    1    0    0    0    0

    0    0    0    0    1    0    0    0

    0    0    0    0    0    1    0    0

    0    0    0    0    0    0    1    0

    0    0    0    0    0    0    0    1

And we need to look for 8 more vectors such that in the set of 16, the sum of any two vectors form a unique 8-dimensional vector. That is, we want a set of 16 such that no two distinct pair of vectors will produce the same sum. A little work shows that the next 4 vectors could be

  [,9] [,10] [,11] [,12]

    1    1    1    1

    1    1    1    0

    1    1    0    1

    1    1    0    0

    1    0    1    1

    1    0    1    0

    1    0    0    1

    1    0    0    0

Some trial and error will produce the last 4 vectors, although using a computer will make it much faster.

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.

Question 1: Are you a truth-teller?

Questions 2-6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Explanations:

Observation 1: The first question is giving the number of truth-tellers. If there are no truth-teller, the problem is readily solved.

Observation 2: Number 'abcd'_B represents a number in base B such that 'abcd'_B = a*B^3 + b*B^2 + c*B^1 + d*B^0. Base 10 is implicit if the base not mentioned.

Observation 3: A k-combination of a set is a subset of k distinct elements of the set. If the set has n elements, the number of k-combinations is equal to the binomial coefficient

(n,k) = n! / ( k! * (n-k)! ).

Observation 4: Hereunder is a table with the following significance:

- first column represents the number k of truth-tellers (information received in the first question)

- second column represents the number of combinations (16,k)

- third column represents the number of combinations (16,k) in base B = k+1 indicated

As we can see, all numbers in the third column have no more than 5 base-B-digits

[1] [16] '10000'_2

[2] [120] '11110'_3

[3] [560] '20300'_4

[4] [1820] '24240'_5

[5] [4368] '32120'_6

[6] [8008] '32230'_7

[7] [11440] '26260'_8

[8] [12870] '18580'_9

[9] [11440] '11440'_10

[10] [8008] '6020'_11

[11] [4368] '2640'_12

[12] [1820] 'AA0'_13

[13] [560] '2C0'_14

[14] [120] '80'_15

[15] [16] '10'_16

[16] [1] '1'_17

Observation 5: A table of correspondences associates to each possible combination an order number . For instance, the table for (16,2) can be written as follows:

[ 1 2] #000 == '00000'_3

[ 1 3] #001 == '00001'_3

[ 1 4] #002 == '00002'_3

[ 1 5] #003 == '00010'_3

....

[14 15] #117 == '11100'_3

[14 16] #118 == '11101'_3

[15 16] #119 == '11102'_3

The table contains #000-#119, a total of 120 combinations.

The relevant such table of correspondences is given to the persons questioned with the phrase "Given the formalism, notations and lines of logic explained below". Therefore they are all aware of all notations.

Observation 6 (line of logic): The 16 persons are to be ordered (physically or only mentally) such that each truth-teller knows his position relative to all other persons and to all other truth-tellers. This position does not change during the questioning. The relevant information (referred to in the questions 2-5) is:

- for Question2: the last digit of the base B number representing the combination of positions of all truth-tellers

- for Question3: the fore-last digit of the base B number representing the combination of positions of all truth-tellers

and so on

Observation 7: Considering that the digit b is the relevant information, the phrase "would your answer have to be yes in order to convey me relevant information" should be understood as "are you among the first b truth-tellers from left to right?". Please notice that the persons themselves know digit b from the table, even if I don't.

EXAMPLE:

Suppose there are 3 truth-tellers in positions [14 15 16]

In the table of correspondences, it is given: [14 15 16] #560 == '20233'_4

Q1: Are you a truth-teller?

Result: 3 yes answers

Q2: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q2 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q3: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q3 translated for them: Are you among the first 3 truth-tellers from left to right?

Result: 3 yes answers

Q4: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q4 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Q5: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q5 translated for them: Are you among the first 0 truth-tellers from left to right?

Result: 0 yes answers

Q6: Given the formalism, notations and lines of logic explained below, would your answer have to be yes in order to convey me relevant information?

Q6 translated for them: Are you among the first 2 truth-tellers from left to right?

Result: 2 yes answers

Other observations:

If there is 1 truth-teller, Q2-5 translate to "Is the last/fore-last/etc. bit of your position equal to 1?"

If there are 9 or more truth-tellers, there can also be a logic of conveying to the questioner a 16-bit number in which the positions of the truth-tellers is marked with bit 1.

Good work, Kornrade. I was considering posting some hints since this question may go unanswered. Seems like that fear was unfounded. You solved the problem perfectly. Way to go, and welcome to the den!

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.

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.

the riddle was "Jimmy can see his mother,his sister and even his sister in law but not his wife as ........" and the answer is that he cannot see his wife as a 'widow' ..

It's nice to see the 1 true answer. Perhaps I'm just being unimaginative, but I don't see why your explanation is preferable to the ones offered by joey, araver, mitspieler, molly mae, etc. Please enlighten me. What mades this answer more logical/fitting/appropriate than the solutions offered thus far?

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.

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.

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.

Jim can see his mother, his sister, and his sister-in-law because...

he is in the hospital recovering from a car crash. The night before his wife discovered text messages on his cellphones from 1 of his 12 mistresses. In the resulting tempest, she grab his golf clubs and chased him around the house. He managed to get to his Mercedes, avoiding a narrow club drive that missed his head and smashed the driver window. He stepped on the gas and drove from the garage, but his wife was running right behind the car and smashing the rear mirror with his prized putter. In his flustered state, he turned his head around to see if she was still behind the car. The car slowly veered off the road while he was otherwise occupied, and it slammed into a nearby light pole, knocking him out cold. Of course his wife didn't visit him in the hospital. The sister-in-law is there because she is the one who texted the message that started the whole thing.

This riddle has only one answer ,read it again.

As other posters have shown, there are multiple solutions to this. The burden of proof is on you to show that there is only 1 answer, and that this 1 true answer deserves special status over all the offered solutions. Good luck.

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.

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.

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

1982 *|* 2010 = 16

The aliens had the numbering system with the base 3, so they only had digits 0, 1 and 2. Operation *|* is performed on each corresponding digit of a number in the following manner - if the 2 digits are the same then the result is the same (e.g. 0 *|* 0 = 0, 1 *|* 1 = 1, 2 *|* 2 = 2). If the digits are different, the the result is the 3rd remaining digit (e.g. 0 *|* 1 = 2, 1 *|* 2 = 0, 0 *|* 2 = 1). To compute the result for any 2 numbers first convert the numbers to base 3 representation and then apply the operation digit-by-digit. For example,

    012001

*|* 012122

    ------

    012210

Good job, k-man. I'm very impressed that you solved this problem. Would you mind sharing your thought process when approaching this problem? What sort of test did you run on the examples? How did you narrow down the possible solutions, and what was the insight that allowed you to crack the code? Again, great job!

Thanks Bushindo. I really enjoyed this one and agree with the answer of 3.

An interesting question would be how many switches, with all the same conditions other than the number of switches, would be the minimum needed to allow you to answer the question with 1 test? Don't have the answer, but I'm going to work on it.

Interesting question indeed. I would say that a preliminary guess is 217, just enough so that the first switch will have 31 copies. But 217 seems to be rather inefficient, however. I'll have to think about other ways to improve upon that.

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.

How do you get 0, If no2 is a truth teller and I was to ask just the question "if I were to ask you if you are in position 9th to 12th and the second person is a truth teller what would your answer be?" would I not get 4 yes?

NNNNNNNNYYYYNNNN

Comment

So, suppose that we have the following configuration

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  T  0  0  0  0  0  0  0  0  0  0  0  0  0  0

where we only have 1 truth teller, and 15 naysayers. The naysayers will always say NO, regardless of what you ask. If you ask "if I were to ask you if you are in position 9th to 12th and the second person is a truth teller what would your answer be?", the naysayers in position 9th - 12th would say NO. The truth tellers in position 2 would also answer NO. Hope that clears it up.

if the questions can be of any length and you can ask

"If I were to ask you if you are in the first 8 people in the row and the first person is a truth teller or if you are in position 9th to 12th and the second person is a truth teller or if you are in position 13 or 14 and the third person is a truth teller or you are the 15th person in the row and the forth person is a truth teller what would your answer be?"

The number of Yes you get back would vary between 0 -15

if you can subtract 8 the first person is truth teller

if you can subtract an additional 4 the second person is truth teller

...

you can do it 4 times for the entire row

...

Edit: Grammer

Yes, the questions can be of any length, so there is no objection to cramming as much information into a question as possible. I have some comment on this solution

Suppose that there is only 1 truth teller in the 16, and he is arranged at position 2. Below is a diagram of the position so it's easier to follow the methodology

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  T  0  0  0  0  0  0  0  0  0  0  0  0  0  0

If we ask each of the 16 people your question:

"If I were to ask you if you are in the first 8 people in the row and the first person is a truth teller or if you are in position 9th to 12th and the second person is a truth teller or if you are in position 13 or 14 and the third person is a truth teller or you are the 15th person in the row and the forth person is a truth teller what would your answer be?"

Then the total number of YES relayed back to you would be 0. Since we can't really subtract 4 from 0 without going into the negative, then we won't be able to identify the second person as the truth teller.

Figured the binary search method would only work if there was one truth teller so the second question if there is between 1 - 4 truth tellers is

What would your answer be if I were to ask if there is a truth teller somewhere to your right?

for 12-16 truth tellers

What would your answer be if I were to ask if there is a liar somewhere to your right?

still need to work on the question for between 5-11 truth tellers

You're on track for the first question, but i have some question about the second

If there is between 1 - 4 truth tellers:

What would your answer be if I were to ask if there is a truth teller somewhere to your right?

Can you elaborate on an example of how this second question can help narrow down the position of the truth tellers? Let's say that the response to the first question is that there are 4 truth tellers in the 16. It seems to me that the second question (Is there a truth teller to your right) is redundant because we already know that there will be 3 YES.

I have a posible solution to this. Have tried quite a few times to cross-check it and it worked each time! Let me know if you find a case where it does not work.

The six questions to ask would be the following:

1) Are you a truthteller?

2) Are you in positions 1 to 8?

3) Are you in an even position (2,4,6,8,10,12,14,16)

4) Are you in a position which is a multiple of 3 (3,6,9,12,15)

5) Are you in a position which is a multiple of 4 (4,8,12,16)

6) Are you ina a position which is a prime number (2,3,5,7,11,13)

The answers are unique for each set of positions (as far as I can tell).

Some comment

It appears that the following possible 2 combinations have the same response: (1, 1, 1, 0, 1, 0 )

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16


0  0  0  T  0  0  0  0  0  0  0  0  0  0  0  0

0  0  0  0  0  0  0  T  0  0  0  0  0  0  0  0

where T indicates the truth tellers, 0 indicates a naysayer, and the index on top indicates their position.