# Puzzle about sharing of information

combinatoricspuzzle

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.