Expand Messages
• Here is the answer with complete explanation...... ( 2N - 3) telephone calls, for N = 2,3 (Not considering N=1) ( 2N - 4) telephone calls, for N 3
Message 1 of 3 , Nov 13, 2005
• 0 Attachment

Here is the answer with complete explanation......

( 2N - 3) telephone calls, for N = 2,3 (Not considering N=1)
( 2N - 4) telephone calls, for N > 3

Explanation:

Divide the N secret agents into two groups. If N is odd, one group will contain one extra agent.
Consider first group: agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. Similarly in second group, agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. After (N - 2) calls, two agents in each the group will know anything that anyone knew in his group, say they are Y1 & Y2 from group 1 and Z1 & Z2 from group 2.
Now, Y1 will call up Z1 and Y2 will call up Z2. Hence, in next two calls total of 4 agents will know everything.
Now (N - 4) telephone calls are reqiured for remaining (N - 4) secret agents.
Total telephone calls require are
= (N - 2) + 2 + (N - 4)
= 2N - 4
Let's take an example. Say there are 4 secret agents W, X, Y & Z. Divide them into two groups of 2 each i.e. (W, X) and (Y, Z). Here, 4 telephone calls are required.

1. W will call up X.
2. Y will call up Z.
3. W, who knows WX will call up Y, who knows YZ.
4. X, who knows WX will call up Z, who knows YZ.

Take an another example. Say there are 5 secret agents J, K, L, M & N. Divide them into two groups i.e. (J, K) and (L, M, N). Here, 6 telephone calls are required.

1. J will call up K.
2. L will call up M.
3. M will call up N. Now M and N know LMN.
4. J, who knows JK will call up M, who knows LMN.
5. K, who knows JK will call up N, who knows LMN.
6. L will call up to anyone of four
• G day all. While we re on the subject, there s a related problem which is slightly easier to solve. Suppose instead of using the telephone, the secret agents
Message 2 of 3 , Nov 14, 2005
• 0 Attachment
G'day all.

While we're on the subject, there's a related problem which is slightly
easier to solve.

Suppose instead of using the telephone, the secret agents use email or
post, which is a one-way communication channel. For example, after
agent 1 mails agent 2, agent 2 knows everything that agent 1 knew, but
agent 1 is none the wiser.

Now how many communications does it take for N agents to mutually
exchange all of their information?

Cheers,
Andrew Bromage
• 2N-2, just one more than the previous case.. Agents 1 to N-1 email agent N, and once agent N receives all the emails, he/she reply back to all of them. Ankur
Message 3 of 3 , Nov 14, 2005
• 0 Attachment
2N-2, just one more than the previous case..

Agents 1 to N-1 email agent N, and once agent N receives all the
emails, he/she reply back to all of them.

Ankur Jain

On Mon, 14 Nov 2005 ajb@... wrote:

> G'day all.
>
> While we're on the subject, there's a related problem which is slightly
> easier to solve.
>
> Suppose instead of using the telephone, the secret agents use email or
> post, which is a one-way communication channel. For example, after
> agent 1 mails agent 2, agent 2 knows everything that agent 1 knew, but
> agent 1 is none the wiser.
>
> Now how many communications does it take for N agents to mutually
> exchange all of their information?
>
> Cheers,
> Andrew Bromage
>
>
>
>