# Thread: induction on gossip problem

1. ## induction on gossip problem

Hello

Here is another problem which I am doing.

Suppose there are n people in a group,
each aware of a scandal no one else in the group knows
about. These people communicate by telephone;
when two people in the group talk, they share
example, on the first call, two people share information, so
by the end of the call, each of these people knows about two
scandals. The gossip problem asks for $G(n)$ , the minimum
number of telephone calls that are needed for all n people to
learn about all the scandals. Prove that

$G(n) = 2n - 4 \;\forall n\geqslant 4$

Here is my attempt at the solution.
Base step: $n=4$. Let's call the four people
A,B,C,D. Now here is the scheme so they can call each other
and learn the scandals. A calls B and C calls D. So A and
B learn each other's scandals as well as C and D learn each
other's scandals. Now let C call B. So both C and B now know
all the four scandals. Also let D call A. Here too, both of them
learn all the scandals. So total 4 calls were necessary so that
all 4 persons know each other's scandals. Now

$G(4)=2\cdot 4-4=4$

So $P(4)$ is true.

Inductive step:Let $n\geqslant 4$ be arbitrary. Suppose
$P(n)$. To prove $P(n+1)$, consider $n+1$ persons. Here
is the scheme for the calls. Let's call 1st person A and
let's call (n+1)th person B. Now first call will be
between A and B. So A knows B's scandal. So A knows two scandals,
which no one except B knows. Now except B, we have $n$ persons.
Using the inductive hypothesis, $2n-4$ calls will be made
between these $n$ persons , so that everybody knows everyone else's
scandals. Now the last call will be made between A and B again. A will
tell B all the scandals learned by A. So after this call all
$n+1$ persons will know each other's scandals. So we can see that
the minimum no. of calls required are

$1+(2n-4)+1 = (2(n+1)-4)$

So, $P(n+1)$ is true. Since $n$ is arbitrary,

$G(n) = 2n - 4 \;\forall n\geqslant 4$

sound reasoning ?

2. ## Re: induction on gossip problem

One simple remark is that you use the induction hypothesis where one person knows two rumors instead of one. The induction hypothesis and the base case need to be relaxed so that it is not essential how many rumors each person knows in the beginning.

More importantly, by providing a way to exchange rumors in 2n - 4 calls, you only proved that G(n), the minimum number of calls, is <= 2n - 4. For the converse it is probably essential that the sets of rumors each person knows are pairwise disjoint.

3. ## Re: induction on gossip problem

oh , i see. how do you think i should resolve that ?

4. ## Re: induction on gossip problem

To prove G(n) >= 2n - 4 is apparently more difficult. I found a proof here (PDF) but have not studied it. This is a well-known problem, so Google gives many links.

5. ## Re: induction on gossip problem

Actually since this is an odd numbered problem, solution is
given at the back of the book. Though induction is not used
I think, even though the problem appears in the section of
mathematical induction. Here is the solution given....

To show that 2n - 4 calls are sufficient to
exchange all the gossip, select persons 1, 2, 3, and 4 to be the
central committee. Every person outside the central commit-
tee calls one person on the central committee. At this point
the central committee members as a group know all the scan-
dals. They then exchange information among themselves by
making the calls 1-2, 3-4, 1-3, and 2-4 in that order. At this
point, every central committee member knows all the scan-
dals. Finally, again every person outside the central committee
calls one person on the central committee, at which point ev-
eryone knows all the scandals. [The total number of calls is
(n - 4) + 4 + (n - 4) = 2n - 4.] That this cannot be done
with fewer than 2n - 4 calls is much harder to prove.

here is one link I found for the harder proof. same as yours I think
http://www.mcs.anl.gov/~csverma/Pape...telephones.pdf

And yes, this is a famous problem , first solved in 1971 by Robert Tijdeman
(Robert Tijdeman). The link to the original paper
"On a telephone problem, Nieuw Arch. Wiskunde (3) 19 (1971), 188-192"