Jump to content
BrainDen.com - Brain Teasers

Question

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 by bushindo
Link to post
Share on other sites
  • Answers 51
  • Created
  • Last Reply

Top Posters For This Question

Recommended Posts

  • 0

tell the guy in room B beforehand that whichever color ball there is the least of that's the first color that will be said then counting that one add more of that color till you reach the amount there are then say the other color and repeat it until you have no more messages then the guy will know there are 3 black balls and they all go first followed by all the reds for example

say there are 3 black and 5 red the first 3 messages say black and the 4th says red and it repeats so it would go

BBBR BBBR BBBR BBBR at some point there would be a problem so it might look like BBBR BRBR BBRR BBBR so by pointing out which occurs most often is obviously the correct amount if there's one of one color its BR BR BR BR BR BR BR BR if its messed up it would look like BB BR BR RB BR BR BR BR and if there are two it would go BBR BBR BBR BBR BBR B if messed up it would look like BRR BBR BBR RBR BBR B if there are four of the same color use my previous example by saying BBBBRRRR BBBBRRRR and then he'll know make sure to use the color that comes first as the one that has the least amount and will come first in the lineup

final example; say that in the room there are 2 red balls so my messages would go RRB RRB RRB RRB RRB R they could be confused to look like this RRB BRB RRB RBB R he will always know that the most common pattern is right.

Mt last solution was redundent if they knew there were four of each the messengers would be pointless so here's a better solution:

Link to post
Share on other sites
  • 0

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.

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.

Edited by araver
Link to post
Share on other sites
  • 0

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.

... shouldn't Hamming code (8,4,4) solve the problem taking 4 bits at a time?

Edited by KlueMaster
Link to post
Share on other sites
  • 0

... shouldn't Hamming code (8,4,4) solve the problem taking 4 bits at a time?

Welcome to BrainDen!

No, since Hamming (8,4) can detect 2-errors but cannot correct them.

So if you split the problem into 2 instances of Hamming (8,4) and the randoms/flippers both occur in the same instance, you're busted.

Edited by araver
Link to post
Share on other sites
  • 0

let the series of balls be a1, a2, a3.... a8. any of them can be red or black.

the messenger series would be

a1, a2, a3, a4, a5, a6, a7, a8

b1, b2, b3, b4, c1, c2, c3, c4

where

b1 is combination of a1, a2 ( its black if a1 a2 are of same color, red if they are different)

b2 is combination of a3, a4

b3 is combination of a5, a6

b4 is combination of a7, a8

c1 is combination of a2, a3

c2 is combination of a4, a5

c3 is combination of a6, a7

c4 is combination of a8, a1

to solve the puzzle, we take a8, a1, a2, a3 and check with c4, b1, c1

this 7 piece will be in shape if none of the elements are reported wrong

else, there are two way of arriving at a solution. By changing 2 of the values or just by changing 1.

Now, First we take the solution of 2 changes and then take the next 7 piece that is, a1, a2, a3, a4 and check with b1, c1, b2 and proceed. If everything matches, the 2 changes are from the first 7 blocker.

Else we take the 1 change as fixed in the first 7 blocker. Now there can be a maximum of only 1 more change. If we proceed with all the 7 blockers we can find out that change ( if indeed the messengers reported 2 wrong)

This will work of all cases.

Let me take an example

Let BRRBBBRR be the arrangement

B1 here would be R ( since a1 and a2 are different) b2 is R etc

Similarly the full messenger code should be

BRRBBBRR

RRBBBBRR

Now lets assume instead the messengers transmit

RRRBBBRR

RRRBBBRR

(change in a1 and b3)

Lets take the first 7 ( a8 a1 a2 a3, c4 b1 c1)

RRRR

RRB

Here RR should lead to B and not R(a8 a1 c4). there is an issue with second pair (a1 a2 b1) too.

There can be 2 solutions to this:

2 change :

RRRR

BBB

1 change:

RBRR

RRB

Now we fix 2 change and try to see if the rest solves fine:

RRRBBBRR

BRBBBBRB

This will fail in the next 7 itself ( 2 changes are done so it should not fail)

RRRB

BRB

Now we go back to accepting the 1 change:

BRRBBBRR

RRRBBBRR

Now, at max only 1 change is left. So going by this cyclically, we arrive at the solution

Link to post
Share on other sites
  • 0

Have given a lot of thought to this and still nothing. I think I need to change the approach may be as in

The prisoner in room B starts with a pre-defined combination, say all balck balls and prisoner A sends messages to convey if where the combinations are right/ wrong. As an example, black denotes even and red meand odd. So first black means an even number of positions are correct... and so on. But again, it is only a start, and needs lot of thinking further. But do let me know Bushindo if I should think further on this. I dont want to try pushing the wall again as I have been doing so far on this puzzle.

Link to post
Share on other sites
  • 0

It was suggested in some posts above, but not in a systematic way.

The two prisoners construct a (16,8,5) block code with 16-bit words, 8 information bits, 8 parity check bits.

Such a code is given here http://www.wolframalpha.com/entities/algebraic_codes/greedy_code_8,_5/qx/32/l0/

This code is optimal, has minimum Hamming distance 5, can correct up to 2 errors and detect up to 4 errors.

Then A encodes the word from the balls [codeword = ballword * generator matrix]

B decodes it (correcting the errors in the process) [syndrome = parity check matrix * codeword transposed]. In other words, B can even say which messenger delivered a wrong message.

Edited by Kornrade
Link to post
Share on other sites
  • 0

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

Edited by bushindo
Link to post
Share on other sites
  • 0

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.

Edited by NikkiF
Link to post
Share on other sites
  • 0

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?

Link to post
Share on other sites
  • 0

let the series of balls be a1, a2, a3.... a8. any of them can be red or black.

the messenger series would be

a1, a2, a3, a4, a5, a6, a7, a8

b1, b2, b3, b4, c1, c2, c3, c4

where

b1 is combination of a1, a2 ( its black if a1 a2 are of same color, red if they are different)

b2 is combination of a3, a4

b3 is combination of a5, a6

b4 is combination of a7, a8

c1 is combination of a2, a3

c2 is combination of a4, a5

c3 is combination of a6, a7

c4 is combination of a8, a1

to solve the puzzle, we take a8, a1, a2, a3 and check with c4, b1, c1

this 7 piece will be in shape if none of the elements are reported wrong

else, there are two way of arriving at a solution. By changing 2 of the values or just by changing 1.

Now, First we take the solution of 2 changes and then take the next 7 piece that is, a1, a2, a3, a4 and check with b1, c1, b2 and proceed. If everything matches, the 2 changes are from the first 7 blocker.

Else we take the 1 change as fixed in the first 7 blocker. Now there can be a maximum of only 1 more change. If we proceed with all the 7 blockers we can find out that change ( if indeed the messengers reported 2 wrong)

This will work of all cases.

Let me take an example

Let BRRBBBRR be the arrangement

B1 here would be R ( since a1 and a2 are different) b2 is R etc

Similarly the full messenger code should be

BRRBBBRR

RRBBBBRR

Now lets assume instead the messengers transmit

RRRBBBRR

RRRBBBRR

(change in a1 and b3)

Lets take the first 7 ( a8 a1 a2 a3, c4 b1 c1)

RRRR

RRB

Here RR should lead to B and not R(a8 a1 c4). there is an issue with second pair (a1 a2 b1) too.

There can be 2 solutions to this:

2 change :

RRRR

BBB

1 change:

RBRR

RRB

Now we fix 2 change and try to see if the rest solves fine:

RRRBBBRR

BRBBBBRB

This will fail in the next 7 itself ( 2 changes are done so it should not fail)

RRRB

BRB

Now we go back to accepting the 1 change:

BRRBBBRR

RRRBBBRR

Now, at max only 1 change is left. So going by this cyclically, we arrive at the solution

this solution will definitely work.

Link to post
Share on other sites
  • 0

No, it won't.

You cannot distinguish between the cases:

1) b1 is changed

2) a1 and c4 are changed.

Making messages depend on only 2 balls cannot work (separate 1 error from 2 errors in all cases)

can you please explain with an example why it wont work? see this example of mine

for the same code

BRRBBBRR

RRBBBBRR

if b1 is changed it is

BRRBBBRR

BRBBBBRR

if a1 and c4 are changed, it becomes

RRRBBBRR

BRBBBBRB

i can still see my algorithm working in both the cases separately.

Link to post
Share on other sites
  • 0

can you please explain with an example why it wont work? see this example of mine

for the same code

BRRBBBRR

RRBBBBRR

if b1 is changed it is

BRRBBBRR

BRBBBBRR

if a1 and c4 are changed, it becomes

RRRBBBRR

BRBBBBRB

i can still see my algorithm working in both the cases separately.

You're not getting my exact meaning: 2 different messages with 2 different changes yield the same transmitted result. And your algorithm cannot determine which one was the original message.

Assume your example. The following message is transmitted by the first person:

BRRBBBRR

RRBBBBRR

And assume b1 is changed during transmission then it is received by the second person as:

BRRBBBRR

BRBBBBRR

My point is that you cannot distinguish this case from the case where the transmitted message was:

RRRBBBRR

BRBBBBRB

and where a1 and c4 are changed resulting in the same received message

BRRBBBRR

BRBBBBRR

For this received message, there are 2 possible explanations - each from a different starting message.

Link to post
Share on other sites
  • 0

You're not getting my exact meaning: 2 different messages with 2 different changes yield the same transmitted result. And your algorithm cannot determine which one was the original message.

Assume your example. The following message is transmitted by the first person:

BRRBBBRR

RRBBBBRR

And assume b1 is changed during transmission then it is received by the second person as:

BRRBBBRR

BRBBBBRR

My point is that you cannot distinguish this case from the case where the transmitted message was:

RRRBBBRR

BRBBBBRB

and where a1 and c4 are changed resulting in the same received message

BRRBBBRR

BRBBBBRR

For this received message, there are 2 possible explanations - each from a different starting message.

ok. got that. thanks for explaining. should have checked properly myself.

Link to post
Share on other sites
  • 0

ok. got that. thanks for explaining. should have checked properly myself.

It's OK. I know the thrill that comes when you think it works ... sometimes it does, sometime it doesn't.

Don't let that ever stop you from searching solutions ;)

And welcome to BrainDen!

Link to post
Share on other sites
  • 0

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?

So A escorts them each time.

Link to post
Share on other sites
  • 0

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!

Edited by bushindo
Link to post
Share on other sites
  • 0

They have the night to prepare a strategy, do they not? Why not also prepare an order? It seems that they already know the rules of the game, how many balls they have, and the colour of said balls, so why not just stop worrying about a complicated strategy and agree on a simple arrangement?

Link to post
Share on other sites
  • 0

we can repeat each ball color twice with only 15 messengers,like this,let me give each ball a number 1-8.so we send the messages in this order:-

1..2..3

4..5..6

7..8..1

2..3..4

5..6..7

each ball will be twice called,now

if :1- No different messages found

means either both random tellers told the truth or only

one of them did,and in both cases the order is true.

2-One message differs,we can control it with the last

messenger and see with which one matched .

3:- Two messages differs.which means both random tellers

lied,so we send the last (truth teller)to check out one of

them,then conferm both balls.

Edited by wolfgang
Link to post
Share on other sites
  • 0

Totally new at logic puzzles. please excuse much ignorance to follow.

I think that this puzzle's solution must assume a certain rate to which the messengers walk, no? if no such assumption exists, your messenger 1 can go out to lunch and come back, reporting after messenger 4 has already reported. Hence, no matter what your strategy is, it won't work. So we must assume a reasonable arrival rate--that is messenger 1 arrives before messenger 2. hence, this is an assumption as to the rate of the messenger, contrary to bushindo's claim that we cannot make this assumption. ... do I make sense :)? I agree with N. that 2 messengers = black vs. 1 messenger = red. It really doesn't violate the conditions set forth in the puzzle. Even if we can't assume they will arrive at exactly the same time, we can assume that they will arrive before the next messenger (s). This is the same assumption that ANY strategy involving Hamming code and so forth would need to rely on--that the previous messenger arrives before subsequent messengers. Afterall, if Prisoner A sent 2 messengers (Messenger C and D) and Messenger C arrives shortly but Messenger D arrives after/with the second group of messenger(s) then in any strategy that can happen---the first messenger arrives after the second so then you can't even rely on the truth of messenger order (in terms of 1st, 2nd, 3rd messengers, etc).

...I do hope this makes sense to someone other than me...

Link to post
Share on other sites
  • 0

They have the night to prepare a strategy, do they not? Why not also prepare an order? It seems that they already know the rules of the game, how many balls they have, and the colour of said balls, so why not just stop worrying about a complicated strategy and agree on a simple arrangement?

The OP is clear that the arrangement is given by the warden, the second day, directly in room A therefore it is previously unknown by both prisoners.

Totally new at logic puzzles. please excuse much ignorance to follow.

I think that this puzzle's solution must assume a certain rate to which the messengers walk, no?

if no such assumption exists, your messenger 1 can go out to lunch and come back, reporting after messenger 4 has already reported. Hence, no matter what your strategy is, it won't work. So we must assume a reasonable arrival rate--that is messenger 1 arrives before messenger 2. hence, this is an assumption as to the rate of the messenger, contrary to bushindo's claim that we cannot make this assumption. ... do I make sense

:)? I agree with N. that 2 messengers = black vs. 1 messenger = red. It really doesn't violate the conditions set forth in the puzzle. Even if we can't assume they will arrive at exactly the same time, we can assume that they will arrive before the next messenger (s). This is the same assumption that ANY strategy involving Hamming code and so forth would need to rely on--that the previous messenger arrives before subsequent messengers. Afterall, if Prisoner A sent 2 messengers (Messenger C and D) and Messenger C arrives shortly but Messenger D arrives after/with the second group of messenger(s) then in any strategy that can happen---the first messenger arrives after the second so then you can't even rely on the truth of messenger order (in terms of 1st, 2nd, 3rd messengers, etc).

...I do hope this makes sense to someone other than me...

Welcome to BrainDen!

Your post makes perfect sense. :thumbsup: However, please use spoilers - big blue button spoiler-button.png when you write a reply in the editor. Some of your statements reference things that are hidden in spoilers in the posts before.

To answer your question from my point of view: there is no need for an assumption on the speed with which each messenger walks.

There are however two natural assumptions may be needed, concerning more the fair-play of the warden than the speed of the messengers:

1) Each messenger does arrive to Room B eventually (i.e. he's not stopped by the warden) (Non-blocking)

2) Either implicitly, or upon request from the two prisoners, the warden will supply a confirmation that a messenger sent from room A has arrived in room B. In this case, the prisoner in Room A can delay sending the next messenger until he receives confirmation that his previous message was received. (Non-interference)

You are correct that something must be assumed in order for messages to not get permuted during transmission. However assumption 2 above shows how this can be done by assuming just a confirmation of successful delivery and not by assuming anything about the speed of the messengers.

Assumption 1 is another example of implicit assumption we all make and should make in order for the problem to have a solution. If no messenger arrives in room B (or equivalently their speed can be 0), then no strategy would ensure a win (barring developing psychic powers over night ;)).

Edited by araver
Link to post
Share on other sites
  • 0

we can repeat each ball color twice with only 15 messengers,like this,let me give each ball a number 1-8.so we send the messages in this order:-

1..2..3

4..5..6

7..8..1

2..3..4

5..6..7

each ball will be twice called,now

if :1- No different messages found

means either both random tellers told the truth or only

one of them did,and in both cases the order is true.

2-One message differs,we can control it with the last

messenger and see with which one matched .

3:- Two messages differs.which means both random tellers

lied,so we send the last (truth teller)to check out one of

them,then conferm both balls.

Your strategy is not possible since it is adaptive (see red steps in the quote above). Essentially this is a one-way communication problem: Prisoner in Room A does not know what is received in Room B.

Therefore while the prisoner in Room B can indeed make that type of reasoning after 15 messengers have been sent, this reasoning cannot possibly affect what prisoner in Room A does with the last messenger.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.


×
×
  • Create New...