Here's the problem:

There are n people, each knows a single unique fact. I need a function to model the minimum number of phone calls it would take for everyone to know every fact. When a phone call is made, the people exchange all the facts that they currently know. Can someone help?

## Answers (2)

One way you could do it is the method divide and conquer:

in the begining everyone knows only their unique facts. Pair every person with someone else and make the call (n/2 in total). If the number of people is odd, move the person to the next wave. In the next step choose one from each pair who phoned and pair those (n/4 calls). Repeat that step until you get one pair, who knows every fact. In total you needed n/2 + n/4 + ... +1 = n-1 calls. Now use the same method to propagate the complete information back through the network (another n-2) calls.

In total this method needs 2n-3 phone calls and since many calls can be made at the same time, the time needed will be approximately log2(n) of the call lengths.

Other way to do this would be to choose one outspoken person (an accumulator) and have everybody call her (-:) and then, when she knows all the gossip, have her call everyone back. The number of calls is the same, but all the calls must be made sequentialy. This method would be much easier to organise.

There might be a way to spare one or two other calls, but not substantialy more. It stands to reason, that each person should call approximately twice - once to pass their information into the network and once to get the complete information back.

I'm having a little trouble figuring out how to prove this, but it seems like the function would just be n-1.