On a successful mission, each spy obtains a unique secret. The n spies need to share all their secrets with each other, which they accomplish through a series of phone calls between 2 spies at a time. During a call, a spy can share all the secrets the spy knows, including secrets learned from previous calls.
What is the minimum number of phone calls needed so every spy learns all of the secrets? Solve the problem for the following two specifications of phone calls.
a) Each phone call is a 1-way call. Only the spy that makes the call can share secret information to the spy on the receiving end.
b) Each phone call is a 2-way call. Both spies can share their secret information with each other.
*Warning: it is very difficult to prove minimality for case b).
Watch the video for a solution.
Can You Solve The Spies Sharing Secrets Puzzle?
Or keep reading.
Answer To Spies Sharing Knowledge
I will present the answer first and then justify why these are minimal procedures in the proof section later.
I will label the spies with letters in alphabetical order (A, B, C, etc.). I will write X→Y to indicate a 1-way call from X to Y, so spy X shares information to spy Y. I will write X↔Y to indicate a 2-way call between spies X and Y where both spies exchange information.
Here is an optimal procedure for 1-way calls. Call one of the spies the “the hub.” All of the other spies call the hub (n – 1 calls), and then the hub calls everyone back (n – 1 calls). If spy A is the hub, for example, the calling procedure with 3 spies would be B→A, C→A, A→B, A→C with the calls in that order.
For n spies, there are 2n – 2 calls made:
2 for 2 spies
4 for 3 spies
6 for 4 spies
2n – 2 for n ≥ 5 spies
The minimum number of 1-way calls is 2n – 2.
There can be other minimal methods too. Consider a “circular pattern” of calls. Imagine arranging the spies in a circle in alphabetical order. The spies first make a clockwise chain of calls starting and ending with A, which is n calls. At this point the last spy and spy A are fully informed. Now spy A starts a clockwise chain of calls which ends two calls before spy A; this is n – 2 calls.
For example, with 4 spies the procedure would be A→B, B→C, C→D, D→A for the first clockwise chain (4 calls), and then A→B, B→C for the second clockwise chain (2 calls). This greedy algorithm has the advantage that the first call shares 1 secret, the second call shares 2 secrets, and so on until n secrets, so each call shares a maximum number of secrets. This method also requires n + (n – 2) = 2n – 2 calls.
With 2-way calls, you might expect that about half the number of calls are needed because both spies can share information during a call. Surprisingly this is not the case! With 2-way calls you can only save 2 calls, and the minimum number of calls is 2n – 4.
For 2 spies, only 1 call is needed: A↔B. For 3 spies, 3 calls are needed: A↔B, B↔C, C↔A. For 4 spies, 4 calls are needed: A↔B, C↔D, A↔C, B↔D. The pattern for 4 spies is particularly important. The graph shows the pattern and the number on each edge indicates the order of the call.
For 5 or more spies, the pattern can be generalized by adding 2 calls. The new spy calls A, B, C, or D at the beginning, and then the new spy gets a call from A, B, C, or D at the end. For example with spy A, the new spy calls A at the beginning, and the new spy calls A at the end. In this way the new spy shares information with A (which then gets shared with all other spies), and then A calls back at the end (so the new spies learns all the other secrets too). For 5 spies, for example, the calling pattern results in 6 calls: A↔E, A↔B, C↔D, A↔C, B↔D, A↔E.
The pattern continues like this, and we have the result:
1 for 2 spies
3 for 3 spies
4 for 4 spies
2n – 4 for n ≥ 5 spies
With 2-way calls, the efficient procedures for n > 4 have the following pattern. Designate 4 spies as hubs A, B, C, and D. Each of the other n – 4 spies calls one of the hubs. Then the 4 hubs share information in the “square” pattern for the case n = 4, which takes 4 calls. Finally, each of the n – 4 spies receives a call from exactly one hub spy. The total number of calls is (n – 4) + 4 + (n – 4) = 2n – 4, and this is the minimum number of calls. The key to the procedure is that 4 hub spies can share information efficiently in 4 calls. The general pattern looks like the following graph (here only spy B is being called by all other spies):
This is the least number of calls needed with 2-way calls. Now compare the result with 1-way calls.
The surprising part is that sharing information is a fairly inefficient process! Although 2-way calls allow for twice the information exchange as 1-way calls, they only reduce the total number of calls by 2. The process of sharing secrets is not much better than everyone calling the hub, and then the hub calling everyone back.
The proofs that these formulas are minimal appear below.
Video with proofs
You can watch the proofs.
Spies Sharing Secrets Proof Minimum Number Calls
Or keep reading.
Proof for 1-way calls
For 1-way calls, each new spy adds on a minimum of 2 calls–one to share the secret and one to learn other secrets. From the base cases where 2n – 2 calls are necessary, it is intuitive that you need 2 more calls for each spy, hence the formula 2n – 2 makes sense.
Why is this minimal? The proof comes from Harary and Schwenk in 1974. Consider any n – 2 calls. It is impossible for any spy to be fully informed, as fully informing a single spy requires the transmission of n – 1 secrets in n – 1 calls. After n – 2 calls, it is possible that each subsequent call could fully inform 1 spy. To inform n spies means n additional calls. Therefore the minimum number of calls is (n – 2) + n = 2n – 2. The protocols of calling the hub and calling circularly do acheive this lower bound, and therefore they are minimal.
Proof for 2-way calls
For 2-way calls, it is not possible to get fewer than 2n – 4 calls when n ≥ 4. The formal proof involves many steps. The reason is that if you assume you could make fewer calls to inform everyone, that would force a specific condition on the calling procedure. The defining condition is that no spy can share his secret and then have that secret shared back to himself. This condition then leads to the conclusion, after a series of logical deductions, that each spy has to make at least 5 calls. This means the total number of 2-way calls is at least 5n/2 > 2n, which is more than 2n – 4 calls. To summarize: assuming fewer than 2n – 4 calls are possible leads to contradiction that more than 2n calls are needed. This proves that 2n – 4 is a lower bound on the calls needed. The procedure to call 4 hub spies above acheives this lower bound, so this is the theoretical minimal number of calls required.
This proof method is due to Brenda Baker and Robert Shostak “Gossips and Telephones” in Discrete Mathematics Volume 2 (1972), 191–193. There are other proofs of this problem; see the references at the end.
Assume that 2n – 4 is not the minimal number of calls for some n > 4. Let m be the smallest value, so that at most 2m – 5 calls are sufficient. The m spies call each other in some procedure.
Claim (NOHOI): The procedure obeys the principle that no one hears their own information (NOHOI) from another person. That is, no spy shares a secret and then has that secret told back to them by another person. If the calling procedure is drawn as an ordered graph (the spies are vertices and the edge number equals order of the call), then NOHOI means that there is no closed walk of edges in increasing order.
(Side note: the optimal method with 2n – 4 calls does not obey NOHOI–a spy calls the hub, and then the hub calls back, so that spy hears his own information.)
Proof (NOHOI): This is a proof by contradiction. If the procedure does not obey NOHOI, we will show we can share secrets with m – 1 spies in fewer than 2(m – 1) – 4 calls. This would be a contradiction because m is defined as the smallest value for which spies can share secrets in at most 2m – 5 calls.
Suppose there is a closed walk of edges in increasing order starting and ending with spy X. This is a sequence of calls X↔S1, S1↔S2, …, Sk↔X. If there are other people that call X, denote those calls by the grouped sets E0, E1, …, Ek+1, where Ei denotes all the calls made before Si↔X and Ek+1 is any calls made after X↔Sk.
Now let’s make a new procedure for m – 1 agents that shares all secrets in less than 2(m – 1) – 4 calls.
All calls that do not involve X remain the same (they are omitted in the diagrams below). Then we will eliminate all calls with X as follows. First, eliminate 2 calls X↔S1 and Sk↔X.
Next, keep all the remaining calls in the same order with the following adjustments. Replace E0↔X with the call E0↔S1, and also replace Ek+1↔X with the call Ek+1↔Sk. Also replace the remaining calls Ej↔X with the call Ej↔Sj.
This is a new calling procedure excluding spy X in which all the other spies share all their secrets. The adjustment process looks like the following:
The calling procedure with m spies had at most 2m – 5 calls. We eliminated 2 calls, so the reduced calling procedure with m – 1 spies has at most 2m – 7 = 2(m – 1) – 5 calls. If the original calling procedure informed all spies, then this adjusted calling procedure also informs all m – 1 spies excluding spy X.
But this means we have created a calling procedure with m – 1 spies that requires at most 2(m – 1) – 5 calls. This contradicts that m is the minimal value.
Therefore, we must have NOHOI in the minimal procedure.
Main proof of minimality: If NOHOI holds, then a call between two spies must be the last call for both, or for neither. Why? Suppose the call is A↔B. If it is the last call for spy A, then spy A is fully informed after the call. This means spy B will be be fully informed and knows all secrets. If spy B calls another spy (say C), then spy B will be sharing the secret of spy C to spy C. This contradicts NOHOI.
Similarly, a call between two spies must be the initial call for both, or for neither. Otherwise, imagine B↔C takes place and then A↔B, which is A’s initial call. Since spy A learns the secret of C, spy A’s information and spy C’s information will be paired together. Eventually spy C needs to learn spy A’s secret. But at that time spy C will learn the secret of C, which contradicts NOHOI.
The remaining calls are all intermediate calls between spies.
For the m > 4 spies, no initial call can be a final call. Each spy has to make an initial call and a final call, so there will be m calls that are either initial or final calls. This means there can be at most m – 5 intermediate calls to stay below the 2m – 5 limit of calls.
For a graph of m vertices, it takes a minimum of m – 1 edges for the graph to be connected. Since there can be at most m – 5 intermediate calls, the graph of intermediate calls has at most m – 5 edges, and so it must have at least 5 disjoint connected components.
Spy A is part of one component, spy A’s initial call might be with another component of intermediate calls, and spy A’s final call might be with a third component of intermediate calls at most. So at least 2 of the components are not involved, or are wasted, from spy A’s perspective of learning secrets. Write w(A) for the number of wasted calls for spy A.
It takes m – 1 calls for spy A to be informed, and it takes m – 1 calls for spy A’s secret to be shared with everyone. By NOHOI, the only calls that can do both involve spy A, which will be denoted as p(A).
The total calls for spy A to share the secret and learn others is at least 2m – 2 – p(A). Taking into account wasted calls, there are at least 2m – 2 – p(A) + w(A) total calls. The total number of calls must be less than or equal to the maximum number of calls, 2m – 5. So:
2m – 2 – p(A) + w(A) ≤ 2m – 5
p(A) ≥ 3 + w(A)
Because the number of wasted calls is non-negative, w(A) ≥ 0, this implies:
p(A) ≥ 3
This means spy A has to make at least 3 calls. Since spy A makes an initial call and a final call, spy A must also make at least one intermediate call. All of this logic is true for each spy, and so every spy makes an intermediate call.
There are at least 2 components in the graph of intermediate calls that are wasted from spy A’s perspective. Since each spy makes an intermediate call, each of the 2 components has to have at least 1 edge. This means w(A) ≥ 2.
Using this information with a previous inequality gives the following result:
p(A) ≥ 3 + w(A)
p(A) ≥ 5
This means each spy is involved in at least 5 calls. Since each call involves two spies, this means there are at least 5m/2 > 2m calls.
This results contradicts that the spies used at most 2m – 5 calls.
Therefore, 2n – 4 is the minimal number of calls for n spies to share their secrets.
This puzzle is known as the “gossiping problem” which is the primary name used in the references.
I first came across in Algorithmic Puzzles by Anany Levitin and Maria Levitin By Anany Levitin, Maria Levitin, “Rumor Spreading,” but the text does not include a proof.
The problem does appear with the above proof in in The Art of Mathematics: Coffee Time in Memphis by Béla Bollobás, “Gossiping Dons.”
MathWorld entry gossiping
One-way communications proof. Harary, F. and Schwenk, A. J. “The Communication Problem on Graphs and Digraphs.” J. Franklin Inst. 297, 491-495, 1974.
Gossiping Dons (several proofs, including Brenda Baker and Robert Shostak “Gossips and Telephones” in Discrete Mathematics Volume 2 (1972), 191–193)
Spreading Gossip Efficiently, C.A.J. Hurkens.
Gossiping problem proven
Thanks to Patrons!
Brian M. Mooney
You can support me and this site at Patreon.
Spies Sharing Secrets – Sunday Puzzle