Loading ...
Sorry, an error occurred while loading the content.

Answer of Brain-storm 8

Expand Messages
  • Abhijit Ghosh
    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
    • ajb@spamcop.net
      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
      • Ankur Jain
        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
          >
          >
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
          >
          >
        Your message has been successfully submitted and would be delivered to recipients shortly.