how to spread gossip

Consider when x people know 1 distinct set of info each, and 1 person outside (Mr K) knows the union of those two sets. The group x has two possible strategies of spreading the gossip, they can call each other, or they can each call Mr K

for x = 2 it is cheaper for the two x's to call each other (1 call) than it is for each of them to call Mr K (2 calls)

for x = 4 it is the same calls for them to call each other (4 calls) as it is for them to call Mr K

for x = 8 they will need 12 calls, but it would only take 8 calls to call Mr K

So, if N is a power of 2:

We need n-1 calls to get to the state where 2 people know all the info, 2 people know discrete halves, 4 people know discrete quarters, 8 people who know eights etc.

another call (between the two who know half each) gives us:
4 people who know all, 4 people who know discrete quarters, 8 people who know eights etc.

At this point, we have proved that the 4 people (and anyone who knows less then them) should "Call Mr K"

so we need n-4 more calls to finish

So, if N is a power of 2 we can always do it in 2n - 4 calls, except for n=1 which is 0 calls, and n = 2 which is 1 call

Originally posted by WanderingKing
Edit: Oh, and this contradicts wolfgang's conjecture, since 2*8-2 is 14. 🙂 But wolfgang's 2*n-2 is certainly correct as an upper bound ...

My thinking was wrong, I inadvertently was assuming the phone
conversation was one-way!

My solution works (I think) if they communicate by post!

If C(n) is number of calls required by n people then note that;

C(n+1) =< C(n) + 2
because the extra person can give his info t "A" as first call and
then get another call from "A" when "A" knows everything.

I would therefore suggest that for all n >3 C(n) = 2n-4

Originally posted by wolfgang59
If C(n) is number of calls required by n people then note that;

C(n+1) =< C(n) + 2
because the extra person can give his info t "A" as first call and
then get another call from "A" when "A" knows everything.

I would therefore suggest that for all n >3 C(n) = 2n-4

Beautiful. 🙂 Would you like to attempt a proof that it's optimal?

Originally posted by iamatiger
Consider when x people know 1 distinct set of info each, and 1 person outside (Mr K) knows the union of those two sets. The group x has two possible strategies of spreading the gossip, they can call each other, or they can each call Mr K

for x = 2 it is cheaper for the two x's to call each other (1 call) than it is for each of them to call Mr K (2 calls ...[text shortened]... we can always do it in 2n - 4 calls, except for n=1 which is 0 calls, and n = 2 which is 1 call

I feel that there's a very interesting idea in this, but I having trouble following your train of thought. Maybe if you answer these two questions, something will click in my brain:

1) Who is Mr K? I've had a couple of ideas on how to understand his introduction, but then it all went blurry in my head.

2) What are the "two sets" Mr K knows? If x people know 1 distinct set of info, then shouldn't there be x sets?

Originally posted by WanderingKing
I feel that there's a very interesting idea in this, but I having trouble following your train of thought. Maybe if you answer these two questions, something will click in my brain:

1) Who is Mr K? I've had a couple of ideas on how to understand his introduction, but then it all went blurry in my head.

2) What are the "two sets" Mr K knows? If x people know 1 distinct set of info, then shouldn't there be x sets?

I was considering the case where we have reached the state where a few people know all the info and a few people know distinct fractions of the info.

so, with 16 gossipers we could have

a,b,c and d know everything.
e knows about aeim
f knows about bfjn
g knows about cgko
h knows about dhlp

now, amongst themselves e,f,g,h know distinct quarters of the information that add up to the whole. In 4 calls they can call each other so they each know everything

"Mr K" is one of a,b,d or d. In 4 calls e,f,g and h can each call Mr K and again know everything. (I'm sorry, I was unclear before, I meant to say that he knows the union of all the sets)


Here is a modification of my method which works with any n > 3

Pick 4 people (at random)

everyone outside the 4 rings one of those 4 (n - 4 calls)
the 4 share their info amongst themselves in 4 more calls calls eg:
ab, cd, ac, bd
so we have had n calls so far and 4 people know all the gossip.
Then everyone outside the 4 calls one of those 4 again (n-4 calls)

and by then everyone knows the gossip, in 2n-4 calls

so it is:
1 person : 0 calls
2 people : 1 call
3 people : 3 calls
N > 3 people : 2N-4 calls

Originally posted by WanderingKing
Beautiful. 🙂 Would you like to attempt a proof that it's optimal?

I would suggest a "reductio ad absurdum" proof by assuming
there exists an "m" such that C(m+1) = C(m) + 1 and showing
that is impossible.

It seems impossible but I don't know how to express it vigorously.