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 ?