Let there be 16 people in a room each with distinct piece of information. Whenever two person interact, they share all the information that they have gained till that time. For instance if person $A$ interact with person $B$, then both of them will share their information that they have. So both will have information, say, $a+b$. Now, if $A$ interact with person $C$, then $A$ & $C$ both will have information $a+b+c$.

The question is how many minimum interactions are needed so that everyone have all pieces of information.

If we denote the minimum interaction needed for $n$ people by $p(n)$, then it is easily shown that $$ p(n)+1 \leq p(n+1) \leq p(n)+2 $$

By computation, I know $p(4)=4$ and this gives a bound , $16 \leq p(16) \leq 28$, which is not very fruitful. Any help is appreciated.

## Best Answer

The minimum number of phone calls needed is $p(n)=2n-4$, for all $n\ge 4$. The fact that $p(n)\le 2n-4$ for $n\ge 4$ is implied by $p(4)\le 4$ and your bound $p(n+1)\le p(n)+2$. Proving the matching lower bound requires careful analysis. The first published solution I could find was [Tijderman (1971)]. There is also a solution in [Baker and Shostak (1972)] which I find to be easier to understand.

The solution from [Tijderman (1971)] is available online at Torsten Sillke's homepage (direct link to file), along with a modern typesetting of the [Baker and Shostak (1972)] proof.