==> combinatorics/gossip.s <==
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.