Chinese Mathematical Olympiad

Proof. We represent each airport with a point. If there is a one-way direct flight from airport a to airport b, we draw a directed edge $ab$, thus obtaining a directed graph G. Let $r = \lfloor \sqrt{\frac{n}{2}} \rfloor$, then $r \ge 2$. We will prove that for any vertex v, there exists a directed cycle passing through v with length at most $2r$. This will imply the desired proposition.

We prove by contradiction. Suppose that $G$ does not admit a directed cycle through $v$ of length less than or equal to $2r$. For each positive integer $k \le r$, set
$$N_k = \{x \in V(G) \mid x \neq v, \text{ and the shortest directed path from } v \text{ to } x \text{ has length } k\},$$
and set $T_k = N_1 \cup \dots \cup N_k$. We first prove the following fact:

(*) For $1 \le k \le r-1$, if the directed edge $\overrightarrow{xy}$ has source in $T_k$ and target in the complement $T_k^c$, then $x \in N_k$ and $y \in N_{k+1}$.

The proof of fact (*) is as follows: Clearly, $y \neq v$. Otherwise, we could connect the directed path from $v$ to $x$ of length at most $k$ with the edge $\overrightarrow{xy} = \overrightarrow{xb}$, obtaining a directed cycle passing through $v$ with length at most $1+k \le r < 2r$, which is a contradiction. Let $x \in N_i$ ($1 \le i \le k$), then there exists a directed path $P$ from $v$ to $x$ of length $i$. Connecting $P$ with the edge $\overrightarrow{xy}$ yields a directed path from $v$ to $y$ of length at most $i+1$. Let $d$ be the length of the shortest directed path from $v$ to $y$. Then $d \le i+1 \le k+1$. Since $y \in (T_k \cup v)^c$, we have $d \ge k+1$, which implies $d = k+1$ and $i=k$, i.e., $x \in N_k$ and $y \in N_{k+1}$.

Next, we claim that: $|T_r| \ge \frac{n}{2}$.

Proof of the claim: We prove by contradiction. Suppose that $|T_r| < \frac{n}{2}$. For each $1 \le i \le r-1$, consider the set $M$ of all directed edges from $T_i$ to $T_i^c$. On the one hand, the condition of the problem implies that
$$|M| \ge 4 \cdot \min\{|T_i|, n - |T_i|\} = 4 \cdot |T_i|.$$
On the other hand, (*) implies that for any directed edge $\overrightarrow{xy}$ in $M$, we have $x \in N_i$ and $y \in N_{i+1}$. From this we know that the number of directed edges in $M$ is less than or equal to the ordered pairs $(x, y) \in N_i \times N_{i+1}$, i.e.
$$|M| \le |N_i| \cdot |N_{i+1}|.$$
Combining these two discussions, we deduce that, for any $1 \le i \le r-1$, we have
$$4 \cdot |T_i| \le |N_i| \cdot |N_{i+1}|. \tag{1}$$
Put $t_i = |T_i| = |N_1| + \dots + |N_i|$. From the given conditions, we see that $t_1 = |N_1| \ge 4 = 2^2$. Using (*), we know that all directed edges $\overrightarrow{xy}$ from $T_1$ to its complement $T_1^c$ all satisfy $y \in N_2$. In particular, $|N_2| \ge 1$. So $|N_1| \le |T_2| - 1 \le |T_r| - 1 < \frac{n}{2} - 1$. Similarly to (*), one can prove all directed edges $\vec{xy}$ from $\{v\} \cup N_1$ to its complement satisfy $x \in N_1, y \in N_2$.

So we have
$$|N_1| \cdot |N_2| \geq 4 \cdot \min\{1 + |N_1|, n - 1 - |N_1|\} = 4(1 + |N_1|).$$
We deduce from this that
$$t_2 = |N_1| + |N_2| \geq |N_1| + \frac{4(1 + |N_1|)}{|N_1|} > |N_1| + 4 \geq 8,$$
Thus, we have $t_2 \geq 9 = 3^2$.

Based on this, we use induction to prove that, for $1 \leq k \leq r$, we have $t_k \geq (k+1)^2$. Suppose that for some $3 \leq m \leq r$, we have $t_{m-2} \geq (m-1)^2$ and $t_{m-1} \geq m^2$. Using (1), we know that, for $1 \leq i \leq r-1$, we have $4t_i \leq (t_i - t_{i-1})(t_{i+1} - t_i)$. Thus, we have
$$\begin{align*} t_m &\geq t_{m-1} + \frac{4t_{m-1}}{t_{m-1} - t_{m-2}} \ &= t_{m-2} + (t_{m-1} - t_{m-2}) + \frac{4t_{m-1}}{t_{m-1} - t_{m-2}} \ &\geq t_{m-2} + 2\sqrt{4t_{m-1}} \ &\geq (m-1)^2 + 2\sqrt{4m^2} \ &= (m+1)^2, \end{align*}$$
This completes the inductive proof and therefore, $|T_r| \geq (r+1)^2 = \left(\lfloor\sqrt{\frac{n}{2}}\rfloor + 1\right)^2 > \frac{n}{2}$, contradicting with earlier assumption $|T_r| < \frac{n}{2}$! This proves the claim.

Similarly, define $K_i = \{x \in V(G) | x \neq v$, and the shortest directed path from $x$ to $v$ has length $i\}$ and put $U_i = K_1 \cup \dots \cup K_i$. Symmetrically, one can prove that $|U_r| \geq \frac{n}{2}$.

Finally, note that both $T_r$ and $U_r$ are subsets of $V(G) \setminus \{v\}$ and we have $|T_r| \geq \frac{n}{2}$ and $|U_r| \geq \frac{n}{2}$. So the intersection of $T_r$ and $U_r$ is nonempty. Take $x \in T_r \cap U_r$, then there is a directed path from $v$ to $x$ of length $\leq r$ and there is a directed path from $x$ to $v$ of length $\leq r$. Combining these two gives a directed cycle through $v$ of length less than or equal to $2r$. Contradiction! □