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

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

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

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?

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