==> 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.