Thread: 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
information about all scandals each knows about. For
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 , the minimum
number of telephone calls that are needed for all n people to
learn about all the scandals. Prove that



Here is my attempt at the solution.
Base step: . 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



So is true.

Inductive step:Let be arbitrary. Suppose
. To prove , consider 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 persons.
Using the inductive hypothesis, calls will be made
between these 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
persons will know each other's scandals. So we can see that
the minimum no. of calls required are



So, is true. Since is arbitrary,



sound reasoning ?

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.

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

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.

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"