mathematics - Spreading Gossip

Initially, each of 50 Puzzling Stack Exchange users have a single distinct juicy bit of gossip not known to the others.

1. If $A$ sends an email to $B$, that email can include all the bits of gossip $A$ currently knows. What are the fewest number of emails that need to be sent so that each of the 50 users knows all 50 bits of gossip? Why can't it be done with fewer emails? Assume multiple recipients / carbon copies are not allowed.


2. If $A$ calls $B$, $A$ and $B$ can exchange all the bits of gossip that both know. What is the fewest number of calls required so that each of the 50 users knows all 50 pieces of gossip?

Note: Addressing why (2) can't be done with fewer calls is a little too difficult for a puzzle in my opinion. But then again I believe Bollobás included it in his puzzle book "Coffee Time in Memphis", so if you want to have a go at it knock yourself out =).

Answer

Problem 1:

As leoll2 illustrates, it can be done in

98 emails (everyone emails Alice, then she emails everyone).

Here's why it can't be done in fewer.

First, we show that after the $48$th email, there won't be anyone who has heard all of the gossip. Consider the undirected graph where the vertices are people, where two people are connected with an edge if one of them emailed the other. Since there are at most $48$ edges, and $50$ vertices, this graph is disconnected (every connected $n$ vertex graph has at least $n-1$ edges). This means that people in one connected component could not have heard any of the tidbits of gossip from the other components, so no one could have heard all the gossip.

Furthermore, the number of people who have heard all the gossip increases by at most one after every email. Thus, since there are 0 fully informed people after $48$ emails, there are at most $49$ fully informed people after $48+49=97$ emails have been sent, so $97$ emails is not enough.