Friday Puzzler -- Information, please

Re: Friday Puzzler - questions

Larry Barrett

Can we assume that messages need not be sent simultaneously?

Can we assume that if B receives message a from A, B can send both message a and message b to C?

Re: Friday Puzzler - questions

Larry Barrett

Assuming that the answer to both questions is yes, then the number 2 appears twice in the answer.

Re: Friday Puzzler - questions

Alex Y

Can we assume that messages need not be sent simultaneously?

Yes. The messages need not be (and if fact are not) sent simultaneously.

Can we assume that if B receives message a from A, B can send both message a and message b to C?

Yes, if I understand you correctly. But the way you describe it sounds like B is sending two messages. In fact, B sends one message containing both the information he knew at the start as well as the information he learned from A.

Correct

Alex Y

Assuming you are not using parentheses in your answer

Now, can you prove that answer is minimal?

Re: Correct

Larry Barrett

My scheme for disseminating messages is this:

A sends his message a to B. B sends messages a and b to C (in a single message). C sends messages a,b,c to D, and so on. Thus, N receive messages a,b,c,...n-1 from N-1 which, combined with his message n means N will now have all messages. This requires N-1 messages.

N can now send all messages to A, B, C, ...N-1 - an additional N-1 messages.

Alternatively, N can send selected subsets of messages to A, B, etc, but it will still require N-1 messages.

So there are a total of 2N-2, or 2(N-1) messages needed.

Consider a different scheme, say where A sends his message a to B and to C. Then B sends message b to C. C now has messages a,b,c, but it required 3 messages to do this, rather than 2 in the scheme above.

Nice job!