bushindo

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!

Well, I see what you're saying.

How about this strategy

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!

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?

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.

That was a pretty clear explanation. Some comments,

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!

I replied too quick. Let me qualify that statement

And rest of my thoughts The rest of your thoughts are spot on, araver.

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?

No conditional message allowed, unfortunately.

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

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

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.

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.

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

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!

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.

Comment

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

You're on track for the first question, but i have some question about the second 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.

Some comment