Question
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)\leq2n-4$ where $n\geq4$
Attempt using proof by induction
Basis step:
$\text{when }n=1$
$$\text{by phone calls } (A\rightarrow B,C\rightarrow D),(AB\rightarrow CD,AB\rightarrow CD)=(ABCD,ABCD)(ABCD,ABCD)\\
\text{Thus, 4 phone calls needed, so since }2(4)-4=4\\ \therefore \text{true for n=4}
$$
Assumption
$$\therefore G(k)\leq2k-4 \text{ by assumption}$$
Inductive step
$$G(k+1)\leq 2k-4+2 $$
And this is where I'm stuck. Can I say that since
$$G(k)\leq2k-4 $$
$$G(k+1)\leq2k-4
\\\text{ since adding +2 makes the right side larger so G(k+1) is still smaller than 2k-4}$$
And how do I go on from there?
Best Answer
I think your induction logic may be a little off, if I'm interpreting what you're saying correctly. You assume that $G(k) \leq 2k-4$, which is fine, but you can't think about adding $2$ to anything at this stage: you have to use your inductive hypothesis to prove that $G(k+1) \leq 2k -4 + 2$.
So, suppose we have a bunch of $k+1$ people. Pick one guy, say, Bob, and have him call someone else, say, Fred. Then remove Bob, so that there are only $k$ people left. Starting from Fred, circulate the gossip to all the $k$ people in $2k-4$ calls using the inductive hypothesis. Since Bob has told Fred his story, Bob's gossip will be circulated as well.
It only remains for Fred (or anyone else) to fill Bob in on everyone's gossip, which is done in one more call. This is, in total, $2k-4$ calls plus the $2$ extra calls between Bob and Fred, and we're done.