2020 IMO Shortlist C3

Let $n$ be an integer with $n \geq 2$. On a slope of a mountain, $n^{2}$ checkpoints are marked, numbered from 1 to $n^{2}$ from the bottom to the top. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars numbered from 1 to $k$; each cable car provides a transfer from some checkpoint to a higher one. For each company, and for any $i$ and $j$ with $1 \leq i<j \leq k$, the starting point of car $j$ is higher than the starting point of car $i$; similarly, the finishing point of car $j$ is higher than the finishing point of car $i$. Say that two checkpoints are linked by some company if one can start from the lower checkpoint and reach the higher one by using one or more cars of that company (no movement on foot is allowed). Determine the smallest $k$ for which one can guarantee that there are two checkpoints that are linked by each of the two companies. (India)

设$n$ 为$n \geq 2$ 的整数。在山坡上，标记了$n^{2}$个检查点，从下到上编号为1到$n^{2}$。两家缆车公司 $A$ 和 $B$ 各运营 $k$ 缆车，编号从 1 到 $k$；每辆缆车都提供从某个检查站到更高的检查站的接送服务。对于每个公司，对于任意 $i$ 和 $j$ 且 $1 \leq i<j \leq k$，汽车 $j$ 的起点高于汽车 $i$ 的起点；同样，车$j$的终点高于车$i$的终点。假设某个公司将两个检查站连接起来，如果一个人可以使用该公司的一辆或多辆汽车从较低的检查站出发并到达较高的检查站(不允许步行)。确定可以保证两家公司各自链接两个检查点的最小 $k$。 (印度)