A group of five spies, Agent A, Agent B, Agent C, Agent D, and Agent E, meet every Friday to share all the information they have uncovered over the previous week. To avoid suspicion, a spy can never be seen with more than one other spy at a time. As well, the spies always communicate face to face to avoid a paper trail.
Every Friday the spies conduct several rounds of meetings at various locations around town. Each round consists of two simultaneous meetings, which involve four spies in total. There is always one spy sitting out of the round.
In each meeting, each spy passes along all of the information they know. This includes both the information they gathered the previous week, as well as all of the information passed on to them from other spies in earlier meetings that day.
Determine the minimum number of rounds of meetings required in order for each spy to learn all of the information gathered by each of the other spies during the previous week.
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
In this solution, we will first show that in order for each spy to learn all of the information gathered by each of the other spies, at least four rounds are needed. Then we will show that this is possible in exactly four rounds. Thus, we will conclude that the minimum number of rounds needed is four.
In the first round, two meetings can take place, and at least one spy will sit out. Suppose Agent E sits out the first round. Since Agent E was not involved, Agent E’s original information is known only by Agent E. Therefore, it is not possible for anyone to know all of the information after one round.
In the second round, Agent E could meet with another spy or Agent E could sit out again.
Suppose Agent E meets with another spy. Then only two spies would know Agent E’s original information. In the third round, these two spies could meet with at most two other spies, so after three rounds, at most four spies would know Agent E’s original information. Therefore, at least one more round would be needed, and so at least four rounds in total are needed.
Suppose Agent E sits out again on the second round. Then in the third round Agent E could meet with another spy, and so only two spies would know Agent E’s original information. Using similar reasoning to that above, we can show that in this case, at least five rounds in total would be needed.
We have shown that at least four rounds are needed if Agent E meets with another spy in the second round. We will now show that this can be done in exactly four rounds.
In the first round, suppose Agent A meets with Agent B, Agent C meets with Agent D, and Agent E sits out.
We can summarize the information each spy knows after the first round in the following table.
| Agent | Agents whose information is known by this Agent |
|---|---|
| A | A, B |
| B | A, B |
| C | C, D |
| D | C, D |
| E | E |
In the second round, suppose Agent E meets with Agent A, Agent B meets with Agent C, and Agent D sits out. Now Agent A knows the original information from Agent B and Agent E, but not Agent C or Agent D. Agent B knows the original information from Agent A, Agent C and Agent D, but not Agent E.
We can summarize the information each spy knows after the second round in the following table.
| Agent | Agents whose information is known by this Agent |
|---|---|
| A | A, B, E |
| B | A, B, C, D |
| C | A, B, C, D |
| D | C, D |
| E | A, B, E |
In the third round, suppose Agent A meets with Agent C, Agent D meets with Agent E, and Agent B sits out. Then the following table summarizes the information each spy knows after the third round.
| Agent | Agents whose information is known by this Agent |
|---|---|
| A | A, B, C, D, E |
| B | A, B, C, D |
| C | A, B, C, D, E |
| D | A, B, C, D, E |
| E | A, B, C, D, E |
In the fourth round, Agent B can meet with any other spy to learn the original information gathered by Agent E. No other meeting needs to take place in this round, as the remaining spies all know all the information gathered by each of the other spies.
We have shown that at least four rounds are needed and we’ve also shown that it is possible for each spy to learn the information gathered by each of the other spies in exactly four rounds. Therefore, the minimum number of rounds required for each spy to learn the information gathered by each of the other spies is four.
Extension:
Suppose there were \(6\) spies instead of \(5\). Determine the minimum number of rounds of meetings required so that all of the information known by each spy has been shared with every other spy. You may be surprised by the result.