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\ne v,\text{ and the shortest directed path from }v\text{ to }x\text{ has length }k\},$$ and set $T_k=N_1\cup \cdots \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\ne 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}|.\text{\hspace{1em}(1)}$$ Put $t_i=|T_i|=|N_1|+\cdots +|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 $\overrightarrow{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|\ge 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|\ge |N_1|+\frac{4(1+|N_1|)}{|N_1|}>|N_1|+4\ge 8,$$ Thus, we have $t_2\ge 9=3^2$.

Based on this, we use induction to prove that, for $1\le k\le r$, we have $t_k\ge (k+1{)}^2$. Suppose that for some $3\le m\le r$, we have $t_{m-2}\ge (m-1{)}^2$ and $t_{m-1}\ge m^2$. Using (1), we know that, for $1\le i\le r-1$, we have $4t_i\le (t_i-t_{i-1})(t_{i+1}-t_i)$. Thus, we have $$\begin{array}{rlrlrl}{t}_m& \ge 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}}& \ge t_{m-2}+2\sqrt{4t_{m-1}}& \ge (m-1{)}^2+2\sqrt{4m^2}& =(m+1{)}^2,\end{array}$$ This completes the inductive proof and therefore, $|T_r|\ge (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\ne v$, and the shortest directed path from $x$ to $v$ has length $i\}$ and put $U_i=K_1\cup \cdots \cup K_i$. Symmetrically, one can prove that $|U_r|\ge \frac{n}{2}$.

Finally, note that both $T_r$ and $U_r$ are subsets of $V(G)\setminus \{v\}$ and we have $|T_r|\ge \frac{n}{2}$ and $|U_r|\ge \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 $\le r$ and there is a directed path from $x$ to $v$ of length $\le r$. Combining these two gives a directed cycle through $v$ of length less than or equal to $2r$. Contradiction! □