n people each know a different piece of gossip.

combinatorics/gossip

Problem

n people each know a different piece of gossip.  They can telephone each other
and exchange all the information they know (so that after the call they both
know anything that either of them knew before the call).  What is the smallest
number of calls needed so that everyone knows everything?

Show solution

1 for n=2
3 for n=3
2n-4 for n>=4

This can be achieved as follows: choose four people (A, B, C, and D) as
the "core group".  Each person outside the core group phones a member of
the core group (it doesn't matter which); this takes n-4 calls.  Now the
core group makes 4 calls: A-B, C-D, A-C, and B-D.  At this point, each
member of the core group knows everything.  Now, each person outside the
core group calls anybody who knows everything; this again requires n-4
calls, for a total of 2n-4.

The solution to the "gossip problem" has been published several times:

        1.  R. Tidjeman, "On a telephone problem", Nieuw Arch. Wisk. 3
                (1971), 188-192.

        2.  B. Baker and R. Shostak, "Gossips and telephones", Discrete
                Math. 2 (1972), 191-193.

        3.  A. Hajnal, E. C. Milner, and E. Szemeredi, "A cure for the
                telephone disease", Canad Math. Bull 15 (1976), 447-450.

        4. Kleitman and Shearer, Disc. Math. 30 (1980), 151-156.

        5.  R. T. Bumby, "A problem with telephones", Siam J. Disc. Meth. 2
                (1981), 13-18.