2023 CMO 第 5 题

There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$ , there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$ ). For any set $A$ composed of airports $(1\le | A| \le n-1)$ , there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$ .

Prove that: For any airport $x$ , we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.

有 $n(n\ge 8)$ 个机场，其中一些机场之间有单程直达航线。对于任意两个机场 $a$ 和 $b$ ，最多有一条从 $a$ 到 $b$ 的单向直达航线(可能同时存在从 $a$ 到 $b$ 和从 $b$ 到 $a$ 的单向直达航线)。对于任何由机场 $(1\le | A| \le n-1)$ 组成的集合 $A$ ，至少有 $4\cdot \min \{|A|,n-|A| \}$ 从 $A$ 机场到非 $A$ 机场的单程直达路线。

证明：对于任意机场 $x$ ，我们可以从 $x$ 出发，通过不超过 $\sqrt{2n}$ 的单向直达路线返回机场。