Puzzle about sharing of information 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.

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.

Brenda Baker, Robert Shostak, "Gossips and telephones," Discrete Mathematics, Volume 2, Issue 3,
1972,
Pages 191-193,
ISSN 0012-365X,
https://doi.org/10.1016/0012-365X(72)90001-5.
R. Tijdeman, On a telephone problem,
Nieuw Archief voor Wiskunde (3), XIX, 188–
192 (1971).

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.
