2020 IMO 第 4 题

There is an integer $n > 1$ . There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$ , operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$ . We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies.

有一个整数 $n > 1$ 。山坡上有 $n^2$ 个车站，且海拔高度不同。两家缆车公司 $A$ 和 $B$ 各运营 $k$ 缆车；每辆缆车提供从一个车站到更高车站的换乘服务(无中间站)。 $A$的$k$缆车有$k$个不同的起点和$k$个不同的终点，并且起点越高的缆车终点也越高。 $B$ 也适用相同的条件。如果一个人可以从较低的车站出发，使用该公司的一辆或多辆汽车到达较高的车站(车站之间不允许有其他移动)，我们就说两个车站是由一家公司连接起来的。确定可以保证两家公司链接的两个车站的最小正整数 $k$。