7
$\begingroup$

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 =).

$\endgroup$
  • $\begingroup$ I have some concerns about this puzzle. a) is "everyone" the 50 users, everyone on PSE, or everyone in the world? b) do the 50 users all know the same juicy bit of gossip, do they all know different bits of gossip, or is there some other number of bits of gossip < 50 that they know in some distribution? $\endgroup$ – Ian MacDonald Jun 3 '15 at 17:42
  • $\begingroup$ @IanMacDonald: Good points, I'll edit to clarify. $\endgroup$ – Tyler Seacrest Jun 3 '15 at 17:45
  • $\begingroup$ 2. Do a conference call with everyone. So 1 call ! $\endgroup$ – TroyAndAbed Jun 3 '15 at 17:48
  • $\begingroup$ @TroyAndAbed But they live in 50 different timezones! $\endgroup$ – user10203 Jun 3 '15 at 18:02
6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Your second problem solution doesn't use phone calls. $\endgroup$ – Ian MacDonald Jun 3 '15 at 18:04
  • $\begingroup$ Oh, I didn't notice that the OP switches from emails to phone-calls in the second problem! $\endgroup$ – leoll2 Jun 3 '15 at 18:06
  • $\begingroup$ Why is 4 chosen as the arbitrary ideal number of important people? If you had 8 people chosen, the same procedure would take 50-8 calls, then 12 to let those 8 all know, and then 50-8 again to spread it (96) calls. $\endgroup$ – Ryan B Jun 3 '15 at 18:15
  • 4
    $\begingroup$ Your proof of the lower bound is flawed: you say everyone must send an email, and everyone must receive one, and then add two numbers. However, their may be overlap, so you could be double counting $\endgroup$ – Mike Earnest Jun 3 '15 at 20:13
  • $\begingroup$ Nicely done, this is the best you can do for both parts. However, I don't totally buy either of the "why is this optimal" sections. Mike Earnest explained the issue with part I; with part II, it seems possible that by adding a new person, their two calls could pass along information in a way to reduce the number of calls needed elsewhere. $\endgroup$ – Tyler Seacrest Jun 4 '15 at 2:24
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If every even calls every odd, it is (25*25)=625 calls! $\endgroup$ – leoll2 Jun 3 '15 at 18:09
  • $\begingroup$ @leoll2 every next odd... $\endgroup$ – user10203 Jun 3 '15 at 18:13
  • $\begingroup$ If every even number calls the number after it, who calls the 1? $\endgroup$ – leoll2 Jun 3 '15 at 18:38
  • $\begingroup$ @leoll2 The 2 since it's 2-way gossiping $\endgroup$ – user10203 Jun 3 '15 at 19:23
  • $\begingroup$ It's clear that leoll2 is not a fan of gossiping ;-P $\endgroup$ – Masclins Jun 3 '15 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.