Spreading Gossip

Question

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 1

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.

Answer 2

My solution to first problem is

$98$

This is the strategy:

First, everyone sends a mail to $A$ ($49$ mails in total). Then $A$ sends a mail to everyone else ($49$ more mails).

Why is this optimal?

To share his information, everyone must send at least an email, though if they want to know other information, they must receive at least a mail as well! So, $49+49=98$ is necessarily the minimum!

---

My solution to the second problem is

$96$

A possible strategy is:

Choose $4$ "important" people in the group $(A,B,C,D)$. The other people call one of these "important" guys, doesn't matter who. These are $50-4$ calls. Those $4$ people then share their knowledge between themselves, so that they know everything. This process requires only 4 calls. Then, they call back the "ignorants", which takes again $50-4$ mails.

Why is it optimal?

It's pretty obvious that $calls(4)=4$.
When you add a member, he must make at least a call (to share his info), then he must receive at least another call (to receive the whole gossip).
Thus, $calls(n+1)=calls(n)+2$.
You can rewrite as $calls(n)=calls(4)+2(n-4)=2n-4$

Answer 3

Here's my answer to the second one:

94

Method

First, every even number calls the number after it. (25). Then, every number in $4n$ calls $4n - 2$. (12) Then $8n$ calls $8n - 4$ (5). Then $16n$ to $16n - 8$ (3). Then $32$ calls $16$. (1) Now $32$ and $16$ know all the gossip (in 46 calls). $16$ calls the rest of the numbers (48) for a total of 94 calls.

Think of it like an inverse binary tree. Every node is a call and all the branches are gossip.

If you take an example of 4 people ($1, 2, 3\text{ and }4$) Whats the fastest way to collect the gossip? 1 calls 2 and 3 calls 4 (2). Now 2 know (1, 2) and 4 knows (3, 4). 4 calls 2 (1) and now they both know all the gossip. Now 2 calls 1 and 3 to tell them (In 3 calls).

Reason for optimality:

You basically need to gather all the gossip then disperse it. Calling basically merges gossip. Take the numbers from 1 to 50. Merge each number to the next number, and call it the second number (Could be the first, but second for ease), and each time, increment a $\text{call}$ counter. You will be left with the even numbers. Repeat this. Now you have multiples of 4. Keep repeating until you have 1 number left (The largest number). This number has all the gossip (And so does the previous number that is a power of two). This optimally combines gossip, as no duplicate gossip is spread. Now call the other numbers with this gossip (total numbers - 2). This may be sub-optimal, I can't prove it is not.