MathDB

Determine the smallest constant

N

so that the following may hold true: Geostan has deployed secret agents in Combostan. All pairs of agents can communicate, either directly or through other agents. The distance between two agents is the smallest number of agents in a communication chain between the two agents. Andreas and Edvard are among these agents, and Combostan has given Noah the task of determining the distance between Andreas and Edvard. Noah has a list of numbers, one for each agent. The number of an agent describes the longest of the two distances from the agent to Andreas and Edvard. However, Noah does not know which number corresponds to which agent, or which agents have direct contact. Given this information, he can write down

N

numbers and prove that the distance between Andreas and Edvard is one of these

N

numbers. The number

N

is independent of the agents’ communication network.

Problem Statement