[Guest]

This problem seems trivial but I think that I'm just interpreting it wrong.

A collection of n gossips each knows a unique tidbit of scandal not known to

any of the others. They communicate by mailing letters. Of course each gossip will

share all of the scandal he (she) knows at that time whenever he (she) sends a letter.

Find, with proof, the minimum number of letters that can suffice to share all of the

scandal

[Guest]

This problem seems trivial but I think that I'm just interpreting it wrong.

A collection of n gossips each knows a unique tidbit of scandal not known to

any of the others. They communicate by mailing letters. Of course each gossip will

share all of the scandal he (she) knows at that time whenever he (she) sends a letter.

Find, with proof, the minimum number of letters that can suffice to share all of the

scandal

Is it enough that one person gain all the details, or does everyone have to know all details?

[Guest]

There are n details. Sending n-1 letters will get all details to the last to recieve all letters. The proof is that each letter holder except the last must send at least one letter in order to pass their detail along. If all letters are sent to the same person, or in a chain to that person, that will be n-1 letters and have all details with 1 person.

If all gossips must gain all details, that requires 2n-2 letters. n-1 must be used to gather all detail and another n-1 to send details back out. The proof is that before the first n-1 letters are sent, there is no way for anybody to have all the details. n-1 letters will put all detail with 1 person. Everyone else must still recieve a letter to inform them of details they do not have, so another n-1 letters are needed, for a total of 2n-2.

[Guest]

Yeah I'm not sure as to whether everybody must get details or if one person gets them all.

I think proof for one person getting them all follows like this. If you let the people be vertices of a graph and the letter mailings be edges you know it takes at least n-1 edges to connect n vertices so it will take n-1 letters.

[Guest]

2(n-1)?

If all people send the info to one person, then they can send it to everyone else in the second volley. That seems simplest to me.

[Guest]

how about a greater challenge?

what would be the maximum amount of letters required? (assume each person shares all the gossip they currently have, to the person who would gain the most from it?)

[Guest]

The correct answer is 2n - 3. Take the example of 4 persons. 1 gives his info to 2, 2 adds his info and gives to 3, 3 adds his info & gives to 4 (3 letters). Notice that 3 and 4 have the same info, therefore, on return, 4 needs to give back only to 2 &1 (2 letters). Total 5 = 2n - 3. This can be generalised to 2n - 3.

There are n details. Sending n-1 letters will get all details to the last to recieve all letters. The proof is that each letter holder except the last must send at least one letter in order to pass their detail along. If all letters are sent to the same person, or in a chain to that person, that will be n-1 letters and have all details with 1 person.

If all gossips must gain all details, that requires 2n-2 letters. n-1 must be used to gather all detail and another n-1 to send details back out. The proof is that before the first n-1 letters are sent, there is no way for anybody to have all the details. n-1 letters will put all detail with 1 person. Everyone else must still recieve a letter to inform them of details they do not have, so another n-1 letters are needed, for a total of 2n-2.

[k-man]

The correct answer is 2n - 3. Take the example of 4 persons. 1 gives his info to 2, 2 adds his info and gives to 3, 3 adds his info & gives to 4 (3 letters). Notice that 3 and 4 have the same info, therefore, on return, 4 needs to give back only to 2 &1 (2 letters). Total 5 = 2n - 3. This can be generalised to 2n - 3.

when person #3 sends a letter with details 1-3 to person #4 they don't have the same info. Person #3 doesn't know what person #4 knows, so person #4 must send his letter to all 3 resulting in 6 letters total or 2(n-1).

On a side note, I came to the same result as Nana and Wyze, but I couldn't find a solid proof that this is the absolute minimum. It seems obvious, but that's not proof.

[k-man]

how about a greater challenge?

what would be the maximum amount of letters required? (assume each person shares all the gossip they currently have, to the person who would gain the most from it?)

I don't really see a greater challenge in this.

n(n-1). There are n pieces of data that needs to be communicated to n-1 people. If each person sends one letter to each of the rest n-1 people they will all know the whole story.

[Guest]

Got a question, is "minimum number of letters that can suffice to share all of the

scandal" supposed to be the total letters sent by all the gossips, or all the letters by a single gossip?

If we want all the letters sent by a single gossip (node) then it can be done in less than n-1 (haven't made exact formula yet). Assume there are 6 nodes. It will be possible to share all the info by each node sending 3 letters. In the case of 6 nodes, n1 can send to n2,n3,n4 in 3 different iterations. At the same time, n1 receives letters from n6,n5,n4. And since each knows something from the previous ones then we get this:

At the begining, n1 only knows message 1 (m1)

After Iteration 1 (from n6): n1 knows m1,m6

After iteration 2 (from n5): n1 knows m1,m6,m5,m4

After Iteration 3 (from n4): n1 knows m1,m6,m5,m4,m3,m2

Thus, n/2 messages.

For 9 nodes, it requires 4 letters to be sent by a single node.

[k-man]

Got a question, is "minimum number of letters that can suffice to share all of the

scandal" supposed to be the total letters sent by all the gossips, or all the letters by a single gossip?

If we want all the letters sent by a single gossip (node) then it can be done in less than n-1 (haven't made exact formula yet). Assume there are 6 nodes. It will be possible to share all the info by each node sending 3 letters. In the case of 6 nodes, n1 can send to n2,n3,n4 in 3 different iterations. At the same time, n1 receives letters from n6,n5,n4. And since each knows something from the previous ones then we get this:

At the begining, n1 only knows message 1 (m1)

After Iteration 1 (from n6): n1 knows m1,m6

After iteration 2 (from n5): n1 knows m1,m6,m5,m4

After Iteration 3 (from n4): n1 knows m1,m6,m5,m4,m3,m2

Thus, n/2 messages.

For 9 nodes, it requires 4 letters to be sent by a single node.

2.

And the total minimum is still 2n-2. There are many ways this can be done, but the simplest is this:

All gossips 1 through n-1 send a letter to gossip n. Now n knows the whole story. He sends one letter to gossip 1. 1 sends it to 2, and so on... In this scheme there are still 2n-2 letters total with every gossip sending at most 2 letters.

[Guest]

say instead of everyone sending 1 letter to 1 person, and then that one person sending 1 letter back to everyone else, n/2 send letters to 1 person, the other n/2 send letters to a second person, the two single poeple excange letters, then they send them back. this is still 2*n-2. can you gernalize this to 3? 4? n? with still keeping 2*n-2?

[k-man]

say instead of everyone sending 1 letter to 1 person, and then that one person sending 1 letter back to everyone else, n/2 send letters to 1 person, the other n/2 send letters to a second person, the two single poeple excange letters, then they send them back. this is still 2*n-2. can you gernalize this to 3? 4? n? with still keeping 2*n-2?

There are a ton of specific ways on exchanging letters between n people, while still keeping the total count at 2n-2. Aren't the solutions posted already general enough?

Representing n people as vertices of a directed graph (digraph) with every letter sent from person a to person b as a directed edge of a graph we can build a huge number of different graphs to meet the requirements of the puzzle (provided large enough n). Translated to the graph theory the requirement is to build a strongly connected graph with n vertices using the least number of edges. It was shown how to do it with 2n-2 edges, but no one proved that it cannot be done with fewer edges. There might be a theorem in the graph theory that proves that, but I'm not well-versed in the graph theory. Maybe someone who knows it can chime in...

[Guest]

One letter is needed. If treated as a chain letter, everyone adds their piece to the letter and mails it to the next person. The letter must be sent the amount of times previously determined by other posters, but the OP is asking about letters, not stamps used!

[Guest]

Maximum would be n(n-1). assume 50 people, each of the 40 people send letters to 49 others to share their single piece of gossip, all done at the same time.

[Guest]

Yeah, proving the answer is the hard part I guess.

Maybe showthat if you have less than 2(n-1) it can't work and show that 2(n-1) works for sharing?

[Guest]

As many people have written, the answer is 2(n-1) or 2n-2. No proof has yet been given.

The proof is by induction on n:

First, show it works for n=2, the smallest n which makes sense. 2*2-2 =2. Clearly, node A send gossip to B, and B sends it back.

Second, assume it holds for n. Prove that for n+1 nodes, 2n letters are required.

For n nodes, the gossip occurs in two steps:

First, n-1 letters are sent to node n by the lower-numbered nodes.

Then, Node n sends back the information to the lower nodes, for a total of 2(n-1) letters.

For n+1 nodes, we just insert a node after the first step defined above. Node n sends a letter to n+1 with all the gossip. Node n+1 sends out a letter back to node n, and node n completes step 2. Total number of added steps = 2; thus, total steps = 2n – 2 + 2 = 2n. QED.

[k-man]

As many people have written, the answer is 2(n-1) or 2n-2. No proof has yet been given.

The proof is by induction on n:

First, show it works for n=2, the smallest n which makes sense. 2*2-2 =2. Clearly, node A send gossip to B, and B sends it back.

Second, assume it holds for n. Prove that for n+1 nodes, 2n letters are required.

For n nodes, the gossip occurs in two steps:

First, n-1 letters are sent to node n by the lower-numbered nodes.

Then, Node n sends back the information to the lower nodes, for a total of 2(n-1) letters.

For n+1 nodes, we just insert a node after the first step defined above. Node n sends a letter to n+1 with all the gossip. Node n+1 sends out a letter back to node n, and node n completes step 2. Total number of added steps = 2; thus, total steps = 2n – 2 + 2 = 2n. QED.

Your proof assumes a particular method of sending letters. You have proven that using this method of sending letters it takes 2(n-1) steps for any n. That is not what required proof, though. We need to prove that there is no such method that would complete the task in fewer than 2(n-1) steps. Therefore, a proof cannot assume any particular method of sending letters.