Taiwan IMO Selection Camp, 2021

Let us construct a directed graph $G$ with cities as vertices, and $(X, N(X))$ as edges. Since $G$ is connected and has a total of $n$ edges, this graph has exactly one cycle. This means that there is at most one pair of cities $(A, B)$ satisfying $A = N(B)$ and $B = N(A)$.

Let us consider the following key lemma:

Lemma: If $B = N(A)$, then there exist at most 4 cities other than $B$ satisfying $A = N(X)$.

Proof: Suppose $X_1, \cdots, X_t$ are all the cities other than $B$ satisfying $A = N(X_i)$. By definition, $\overline{X_iA} < \overline{X_iB}$, which means $X_i$ and $A$ must lie on the same side of the perpendicular bisector of $\overline{AB}$. Also by definition, we know $\overline{X_iA} > \overline{AB}$, so $X_i$ must lie outside the circle centered at $A$ passing through point $B$. This means the possible range of angles for the ray $AX_i$ is $4\pi/3$.

Now, for any $i \neq j$, $\overline{X_iX_j}$ must be the longest side of $\triangle AX_iX_j$, that is, $\angle X_iAX_j > \pi/3$. Combining this with the previous discussion about the possible range of angles for the rays, we get
$$t - 1 \le \frac{4\pi/3}{\pi/3} = 4,$$
that is, $t \le 4$. This completes the proof of the lemma. $\Box$

Returning to the original problem. By the lemma, we know that for every city $A$, there are at most four cities $X$ satisfying $N(X) = A$ and $N(N(X)) \neq X$. Let $S$ be the set of all suburban cities, and let $S'$ be the set of all cities satisfying $N(N(X)) \neq X$. Note that we have $|S'| \ge n - 2$ and $4|S| \ge |S'|$ (since the preimage under $N : S' \to S$ has size at most 4), which means $|S| \ge (n - 2)/4$. This completes the proof.