, 2021

Let $G$ be the graph corresponding to IMO-nation, and let $d(u,v)$ be the distance between $u$ and $v$. Consider the following strategy.

1. Arbitrarily choose a village $v$, and let $S = \{v\}$.

2. For every $u \ne v$, make one phone call asking for the distance between $u$ and $v$.

3. If there exists $v'$ such that $\min_{s \in S} d(v', s) \ge k$, and there exists $s \in S$ such that $d(v', s) = k$, then let $S = S \cup \{v'\}$, change $v$ to $v'$, and return to step 2.

4. Check whether every village is at distance at most $k$ from some $s \in S$; if so, report that $G$ is connected. Otherwise, report that $G$ is not connected.

First we prove that this algorithm indeed determines whether $G$ is connected. Denote by $S_0$ the set $S$ at the end of the algorithm. By step 3, the points in $S_0$ must all belong to the same connected set (this can be proved by induction), so if step 4 reports that $G$ is connected, then $G$ is indeed connected. Conversely, if step 4 reports that $G$ is not connected, this means there exists $u$ such that $\min_{s \in S_0} d(u, s) > k$. Suppose that $G$ is in fact connected; then for any $v \in S_0$, there must exist a shortest path from $u$ to $v$, and its length is greater than $k$. Moreover, on this path there must exist a point $w$ whose distance to a point in $S$ is at most $k$. But then, at step 3, we should have obtained $v' = w$ and returned to step 2, so the algorithm would not yet have ended, a contradiction. Hence the algorithm reports that $G$ is connected if and only if $G$ is indeed connected.

Next we prove that the number of phone calls required by this algorithm is at most $2n^2/k$. Note that we only make $n$ phone calls in step 2, and step 2 is repeated at most $|S_0|$ times, so it suffices to prove that $|S_0| \le 2n/k$. This is obvious when $|S_0| = 1$, so assume $|S_0| \ge 2$. Consider the connected set $C$ in which $S_0$ lies, and suppose $|C| = m$. Consider a spanning tree on $C$, and consider an Euler tour $v_1, \dots, v_{2(m-1)}$ on this tree. Then we can certainly choose $i_1 < i_2 < \dots < i_{|S_0|}$ such that $S_0 = \{v_{i_1}, v_{i_2}, \dots, v_{i_k}\}$.

Now, since $v_{i_j}$ and $v_{i_{j+1}}$ are two distinct elements of $S_0$, by step 3 the distance between the two points is at least $k$, and hence $i_{j+1} - i_j \ge k$. This shows that $|v_{i_S} - i_1| \ge k(|S_0| - 1)$. Also note that we may set $v_{i+2(m-1)} = v_i$, and consider the path starting from $v_{i|S_0|}$ to $v_{i_1+2(m-1)}$; this distance likewise must be at least $k$, that is, $i_1 + 2(m-1) - |S_0| \ge k$. Combining the two inequalities, we obtain $k|S_0| \le 2(m-1) < 2n$, so $|S_0| < 2n/k$. This completes the proof.