# 99 combinatorics/gossip.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 99 combinatorics/gossip.p

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?

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.

Continue to: