Prison break: a minimisation problem

Consider a prison with $n$ prisoners. Each cell contains a phone which can be used to call any other cell. Each prisoner has a different piece of information which, when put together, will allow them to make a successful escape. To avoid suspicion, they wish to minimise the number of calls that need to be made such that all of them know the information.

What is the mimimum?

For notational purposes let the set of individuals be $\{p_1,\;\cdots , \;p_n\}$, and let $p_i\to p_j$ indicate a phone call from $p_i$ to $p_j$. It is understood that in any such phone call, $p_i$ and $p_j$ exchange all the information they have.

After considering small cases, it would appear the minimum is $2n-4$ when $n\geq 4$. One can easily show that this is sufficient. For instance, consider the following algorithm:

• $n=2m:$ Let $p_{2i-1}\to p_{2i}$ for $i=1,\,2,\,\cdots ,\,m\;\;(m$ calls$)$. Let $p_{2m}\to p_{2i}$ for $i=m-1,\,\cdots ,\,2,\,1\;\;(m-1$ calls $)$. At this point $p_{2m}$ and $p_2$ have all the information. Let $p_1\to p_4$, who both have all the information now. We are left with $\{p_3,\;p_5,\;p_6,\cdots p_{2m-1}\}$, $\text{i.e.}\;2m-4$ individuals without all the information. Let $p_1\to p_i$ for all $p_i$ in this set and every prisoner can now escape after exactly $4m-4\;\text{i.e.}\;2n-4$ calls.

• $n=2m+1:$ Consider the previous case, but let $p_{2m+1}\to p_1$ before the chain of calls and $p_{2m+1}\to 1$ again at the end of the chain. The information is passed in $4m-2\;\text{i.e.}\;2n-4$ calls.

The difficult part is showing that $2n-4$ is in fact necessary, and I have had no luck with it. I feel a knowledge of graph theory might help. The problem comes from a series of exercises which were set as part of a course in elementary number theory. Hints or ideas would be greatly appreciated.

• What about for $n=2,3$? You have $0$ and $2$ calls respectively in those cases. You would need $1$ when $n=2$ and $3$ when $n=3$... Nov 24, 2013 at 15:00
• @doppz Apologies, I forgot to type in $n\geq 4$. The lower cases are trivial of course. Nov 24, 2013 at 15:02
• I'm reminded of a "gossip problem". Are you familiar with semigroups? I think they might be helpful here. Nov 24, 2013 at 15:04
• @Shaun I am not, but I shall look them up. Nov 24, 2013 at 15:10
• @Lachryma Papaveris: I mention semigroups because, if I recall correctly, you can view the act of exchanging information in this case as the binary operation of a semigroup; I could be wrong. Nov 24, 2013 at 15:15

Hint: Use induction for $n \geq 4$, assume on the contrary that there is an algorithm with $\leq 2n-5$ calls, then use the induction hypothesis to prove the following lemma: "No prisoner hears his own information from some other prisoner"
(Strictly speaking $2n-4$ is the minimum only for $n \geq 4$; you have to consider the small cases seperately.)