Four spies share secrets over the phone: each call updates both participants on everything the other knows. The question is how many calls are enough for no one to ignore anything.
The relay of messages
Riddle statement
Four spies—A, B, C, and D—each have a different secret.
Every time two spies talk on the phone, they both tell each other everything they know at that moment.
What is the minimum number of calls necessary for all four to know the four secrets?
Show solution
Solution
Answer: 4 calls are needed.
A sequence that achieves this is:
- A calls B. A and B know A and B's secrets.
- C calls D. C and D know C and D's secrets.
- A calls C. A and C exchange what they know, so they both know the four secrets.
- B calls D. B and D exchange what they know, so they both know the four secrets.
In the end, the four spies know the four secrets.
3 calls cannot be enough. With only 3 calls between 4 people, at least one person participates in a single call. That person can only learn what his interlocutor knew at that moment; It cannot receive information that arrives later through other calls. Therefore, not everyone can finish all four secrets.
So the minimum is 4.