IMO 2020 Problem 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.  

======================================

Solution:

Represent a cable car by a tuple $(a, b)$ where $0\leq a\lt b\leq n^2-1$.

First, we show that with $k=n^2-n+1$, companies $A$ and $B$ will both link a common pair of stations. Consider only company $A$'s cable cars. There will be at least $2(n^2-n+1)-n^2=n^2-2n+2$ stations that is both a starting point and an end point, because no two cable cars could start or end at the same station. Thus there are at most $2n-2$ stations that are only a starting or end point but not both, which we call singleton station. We group cable cars into chains. A chain is a sequence of connecting cable cars, i.e. $(a_1,b_1), (a_2,b_2),\ldots$ where $b_i=a_{i+1}$ for all $i$. Each chain has exactly $2$ singleton stations, so there are at most $n-1$ chains, and thus the longest chain must have at least $n+1$ cable cars. However every cable car connects two stations no more than $n-1$ intervals apart, as otherwise the company will have at most $n^2-(n+1)+1=n^2-n\lt k$ cable cars. So the longest chain has only one possibility: sequence $(m(n-1), (m+1)(n-1))$ for $0\leq m\leq n$. Since it applies to any company, the statement holds.

Then, we show that for $k=n^2-n$ companies $A$ and $B$ could have no common pair of linked stations. Let $A$ be $(i, i+n)$ for $0\leq i\leq n^2-n-1$, i.e. all stations $n$ intervals apart. Let $B$ be $(i,i+n-1)$ for $0\leq i\leq n^2-2n$ and $(j,j+1)$ for $n^2-n\leq j\leq n^2-2$. We could verify that the pairs of stations linked by companies $A$ and $B$ are indeed disjoint.