Efficient gossip by telephone

Each of 10 friends knows some item of gossip not known to the others. They communicate by telephone, and in each call the two friends on the line share everything they have heard thus far. What is the smallest number of calls that can be made, such that by the end, everyone knows everything?

Image credit: LittleGreenFrog


The answer is 16.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Ankit Jain Aj
Jan 25, 2014

Suppose everybody has following gossip :
a,b,c,d,,e,f,g,h,j,k
now if person with knowledge a calls person with knowledge b , then person(a) will have a+b knowledge and same person(b) will have , Similarly in next 3 calls of person(a) with person(c) ,(d) and (e),, person(a) and person(e) will have a+b+c+d+e knowledge . If same scenario happens in other half row (k calling j,h,g,f) then person(k) and person (f) have f+g+h+j+k knowledge .
Till now 8 calls have been made . Now if person(a) and person(k) calls then they both will know every gossip , similarly if person(e) and person(f) calls then they will know every gossip.


Total calls : 10 and a,e,f,k knows full gossip . Now if remaining persons i.e (b,c,d,g,h,j ) will call anyone from (a,e,f,k) they will know every gossip .
So total calls will be 10+ 6 =16
Enjoy ;)

How to prove that 16 is the least amount of call needed?

Habibi Reverse - 7 years, 4 months ago

Log in to reply

How is it that people are upvoting that solution and downvoting your question? This solution doesn't even prove anything, the question asks you to prove that it 16 is the minimum.

Liu Tianyi - 7 years, 3 months ago

Let f(n) be the number of minimum calls necessary to complete gossiping among n people, where any pair of people may call each other.

f(1) = 0, f(2) = 1, f(3) = 3, and f(n) = 2n - 4.

Denoting the gossip-spreaders as A, B, C, and D, a solution for n=4 is given by {A,B}, {C,D}, {A,C}, {B,D}. The n=4 solution can then be generalized to n>4 by adding the pair {A,X} to the beginning and end of the previous solution, i.e., {A,E}, {A,B}, {C,D}, {A,C}, {B,D}, {A,E}.

Proof link

Shamik Banerjee - 7 years, 4 months ago

Log in to reply

Excellent link.

A Brilliant Member - 7 years, 3 months ago

I still think it's 15! anybody who got the same answer?

Mayank Holmes - 7 years, 1 month ago
Ujjwal Uttaray
Jan 31, 2014

We need to find f(10). We can find by hand calculation that f(4) = 4.

we can point out f(n+1)<= f(n)+2 for people a 1,a 2,...a n, a n+1

first a n+1 calls a 1 then f(n) calls happen between a 1 to a n. Then we can see everyone except a {n+1} knows everything . One more call is required for a {n+1}

So, f(10) = f(4)+6*2=16

It would seem that nobody is tackling the hardest part of this problem.

Peter Byers - 7 years, 4 months ago

Log in to reply

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf

Justin Palumbo - 7 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...