Results 1 to 5 of 5

Math Help - induction on gossip problem

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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 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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction on gossip problem

    oh , i see. how do you think i should resolve that ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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"
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induction problem
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: May 17th 2010, 12:02 AM
  2. Induction Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 30th 2009, 07:44 PM
  3. induction problem,
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 7th 2009, 05:57 AM
  4. induction problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 26th 2008, 12:04 PM
  5. Induction problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 16th 2008, 04:41 AM

/mathhelpforum @mathhelpforum