Challenge 246: Security Secrets

a Each of a group of spies has a personal passcode. At the start of a mission, each only knows their own passcode, but they need to make sure that they all know the other’s passcodes for the mission to succeed. To achieve this, one spy will leave a message in a hollow tree, which gives their own passcode, along with the passcode of any other spy whose passcode they know. That message will be collected by one other spy, who will then know any passcode known to the first spy (who left the message), as well as their own passcode. This process continues until all the spies know all the passcodes.

Show that the minimum number of hollow-tree drops required with four spies in the group is 6. What is the minimum number with five spies in the group?

b Each of another group of (less security-conscious) spies also has a personal passcode. As before, initially each only knows their own passcode, but they need to exchange them so that they all know the other’s passcodes. To achieve this, one spy will phone another and the two of them will exchange their passcodes and those of any other spy whose passcode they know. This process continues until all the spies know all the passcodes.

Show that the minimum number of phone calls required with four spies in the group is 4. What is the minimum number with five spies in the group?