Each of \(n\) male citizens knows a different piece of gossip. They are allowed to exchange the gossip they know by phone. During a call, just one of the men speaks and tells the other all the gossip he knows. What is the minimum number of calls required to enable each man to know all the gossip?

[SOLVED]

5 comments

Tim Ophelders solved this puzzle:

Let \(F(i)\) if and only if all \(n\) pieces of gossip can be spread in \(i\) calls. We can use \(n - 1\) calls to gather all gossip at a single person, and another \(n - 1\) calls for that person to spread the gossip to all other people. Therefore, \(F(2n - 2)\).

Let \(M_i\) be the maximum number of pieces of gossip a person knows after \(i\) calls. If \(M_i \lt n\), then \(\neg F(j)\) for \(j \lt i+n\) because nobody knows all gossip after the \(i\)th call and it takes at least one additional call per person to get to know all gossip. Thus, if \(F(j)\) and \(j = i + n - 1\), \(M_i = n\). In other words, if \(F(j)\), then \(M_{j - (n - 1)} = n\).

To prove the claim that \(2n - 2\) is the minimum number of calls required to spread all gossip, we show that \(\neg F(2n - 3)\). Assuming \(F(2n - 3)\), \(M_{(2n - 3) - (n - 1)} = M_{n - 2} = n\); that is one person must know all gossip after \(n - 2\) calls. But it takes at least \(n - 1\) calls to get all gossip to a single person, so \(\neg F(2n - 3)\).

Therefore, \(2n - 2\) is the minimum number of calls required for every man to know all gossip.

Rino Raj solved this puzzle:

Let \(f(n)\) be the minimum number of calls needed by \(n\) people to enable each man to know all the gossip. Now, if we add one more person, it is easy to see that at least one extra call is needed to get his information, and one more to provide him all the gossip. Thus, \(f(n+1) \geq f(n) + 2\) is a lower bound.

In fact, all the gossip can be shared exactly by two more calls. To differentiate between transmitting and receiving gossiping, let us, without loss of generality, assume that the person making the call always tells all the gossip he has and the person receiving a call only receives gossip. In the \(f(n)\) calls needed by \(n\) people to share all gossip with each other, let \(A\) be the first person to make a call and \(B\) be the last person to receive a call. Clearly, in the last call \(B\) receives all the gossip. When we add one more person to the group, this new person should call \(A\) and transmit his gossip, and after the \(f(n)\) calls are made among the first \(n\) people, \(B\) should call the new person and tell him all the gossip. Hence, \(f(n+1) = f(n) + 2\).

When \(n = 1\), it is trivially seen that no calls are needed. Thus, \(f(n) = 0\). Therefore, \(f(n) = 2n - 2\).

Ed Murphy solved this puzzle:

If each call is limited to two men, then \(2n - 2\) calls is necessary and sufficient. Sufficiency is shown by construction; pick one man, have everyone else call him, then have him call everyone else. Necessity is shown as follows:

  • Call a man "informed" if he knows all rumors; call two men "connected" if they know at least one rumor in common; call a man "isolated" if he is not connected to anyone else.
  • It takes at least \(n - 1\) calls for someone to become informed. (The first call connects two men, and each of the next \(n - 2\) calls connects at most one previously isolated man. No one can be informed if anyone is still isolated, as an informed man is connected with all others.)
  • Only one man's knowledge increases at a time, so only one man becomes informed at a time.
  • Once one man is informed, it takes at least \(n - 1\) calls for everyone else to become informed. (Each is uninformed, so each must receive a call.)

If conference calls with an arbitrary number of participants are allowed, then \(n\) calls is necessary and sufficient. All the calls include everyone, and each man in turn shares their rumor.

Indhu Bharathi solved this puzzle:

In the sequence of calls that leads to all men knowing all the gossip, there is a state when there is only one person who knows all the gossip. Let's call this state C. I'll argue that atleast \(n - 1\) calls are required to reach state C and another \(n - 1\) calls to move from state C to the final state when every man knows all the gossip.

For a man E to know all the gossip, it requires all men except E to make a call and tell the gossip he knows, so we need \(n - 1\) calls to reach the point C. To reach the final state from C, at the very least, each of \(n - 1\) men, who don't know all parts of the gossip, need to receive a call from someone and get all the gossip. This requires another \(n - 1\) calls.

Therefore, we need at least \(2(n - 1)\) calls for all men to know all the gossip.

To show that there is a way to solve this probem with \(2(n - 1)\) calls, I only need to show that one such solution exists. Mark one of the men as S. First, every man except S calls S and tells the gossip he knows. Then, S calls everyone else and tells them all the gossip.

Alex Yeilding commented:

The answer of \(2n - 2\) given so far make sense, but makes an assumption not stated explicitly in the puzzle. How do the \(n\) individuals know who to call when? The person designing the communication scheme needs to communicate that scheme to all the participants. So I contend that the correct answer is \(3n - 2\).

Note that the designer of the communication scheme must be external to the group, or else you would have the potential for multiple participants designing conflicting communication schemes.

Or, as probably intended, state that meta-communication about the communication plan is not included in the call count.

Credit

This puzzle is taken from:

  • Savchev, Svetoslav; Andreescu, Titu. Mathematical Miniatures. Washington, D.C.: Mathematical Association of America, 2003. 98.

Post a comment

RSS