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 $\displaystyle G(n)$ , the minimum

number of telephone calls that are needed for all n people to

learn about all the scandals. Prove that

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

Here is my attempt at the solution.

Base step: $\displaystyle 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

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

So $\displaystyle P(4)$ is true.

Inductive step:Let $\displaystyle n\geqslant 4$ be arbitrary. Suppose

$\displaystyle P(n)$. To prove $\displaystyle P(n+1)$, consider $\displaystyle 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 $\displaystyle n$ persons.

Using the inductive hypothesis, $\displaystyle 2n-4$ calls will be made

between these $\displaystyle 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

$\displaystyle n+1$ persons will know each other's scandals. So we can see that

the minimum no. of calls required are

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

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

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

sound reasoning ?