3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$... $\endgroup$
    – doppz
    Nov 24, 2013 at 15:00
  • $\begingroup$ @doppz Apologies, I forgot to type in $n\geq 4$. The lower cases are trivial of course. $\endgroup$ Nov 24, 2013 at 15:02
  • 1
    $\begingroup$ I'm reminded of a "gossip problem". Are you familiar with semigroups? I think they might be helpful here. $\endgroup$
    – Shaun
    Nov 24, 2013 at 15:04
  • 1
    $\begingroup$ @Shaun I am not, but I shall look them up. $\endgroup$ Nov 24, 2013 at 15:10
  • $\begingroup$ @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. $\endgroup$
    – Shaun
    Nov 24, 2013 at 15:15

1 Answer 1

3
$\begingroup$

This is also known as the "Gossip Problem" and is a classic problem. Incidentally it appeared as the last question on an example sheet for the "Numbers and Sets" course at Cambridge this year.

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.)

Knowledge of graph theory will definitely be a good boost to helping you solve the problem, but since not much graph theory is needed for the proof, it is entirely possible (but harder) to come up with a proof without using any graph theory.

$\endgroup$
2
  • $\begingroup$ Thanks for the hint. And yes, that is precisely where I have taken the problem from - thought I should spice it up with prisoners rather than dons. $\endgroup$ Nov 24, 2013 at 15:09
  • $\begingroup$ This question is a Cambridge tradition -- it was on the Cambridge Numbers & Sets sheets 12 years ago when I was a first-year undergrad. (I didn't solve it :-) ) $\endgroup$ Nov 25, 2013 at 9:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .