From: "Iain Davidson" Subject: Re: Gossip problem Date: Sun, 12 Dec 1999 16:06:53 -0000 Newsgroups: sci.math Keywords: minimum number of calls to exchange information Chris Wildhagen wrote in message news:82rej3$2jpt$1@reader1.wxs.nl... > The following problem seems to be known, but I can't find a reference. > > Each of 6 people knows exactly one gossip, each a different one. They can > reach eachother by telephone. What is the smallest number of calls that are > needed to ensure that each person knows all gossips? > > What about the generalisation to n people? In "Introduction to Combinatorics" by Ioan Tomescu a general problem (Baker, Shostak and Hajnal, Milner, Szemerdi, 1972) is stated as There are n gossips each of whom knows some gossip not known to the others. They communcate by telephone, and whenever one gossip calls another, they tell each other all they know at that time. Prove that the minimum number of calls required before each gossip knows everything is equal to 2n-4 for n>= 4 The first sentence is slightly ambiguous. The following references are given Baker, B., Shostak, R., Gossips and telephones, Discrete Math., 2. 1972, 191 -193 Berman, G., The Gossip problem, Discrete Math., 4. 1973, 91; Corrigendum 4., 1973, 397