The Gossip Problem

A community consists of n people, each of whom knows something special. What is the best strategy for transmitting all of the information to everyone by telephone and how many telephone calls will be required? Conference calls are not permitted.

References

  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. Math. 2 (1981), 13-18.
The consensus is that the best strategy is to create a committee of four people. Each member of the committee takes a fourth of the population and calls them to gather their information. The committee now divides itself into pairs and the pairs call each other. The committee next divides itself into pairs the other way and the pairs call each other. At this point every member of the committee knows everything. The committee members then call the rest and everyone knows everything. The number of calls required is 4 + 2(n - 4) = 2n - 4.

This is the standard solution, but it ignores the number of calls needed to set up the committee. Complicated and detailed schemes do not occur simultaneously to a number of people. In order to set up the scheme at least three calls must be made to assign quarters of the population and to describe the plan for calling each other in pairs. The total number of calls required, therefore, is 2n - 1.

This is one less than the number of calls required by a committe of one. A committee of two can do the job with one organization call and one information sharing call, for a total of 2n - 1 calls.

One may ask, couldn't the first person in the telephone book call the second, the second call the third, and so around and around until the last person in the book was reached? n - 1 calls would be required to reach the n'th person. At that point he would have all of the information and would have to call everyone but himself and the person who called him. Alternatively, the n - 1 person could initiate calls back up the list and the first person would be reached in n - 2 calls. With a total of 2n - 3 calls required, the obvious method does better than the sophisticated method.

The above formula holds whether n is small or large. Two people require one call; three people require 3 calls. Four people can do it in five calls. Five people need seven calls, etc.