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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{k=n^2-n+1}. \]

Solution

For either company, at most one cable car starts at each station, and at most one finishes there. Moreover, every cable car goes strictly uphill. Therefore, that company’s cars partition the stations into disjoint directed paths, including isolated stations as paths with one station.

Indeed, from any station, follow incoming cars backwards until reaching a station with no incoming car, and then follow outgoing cars forwards until reaching a station with no outgoing car. Both procedures terminate because altitudes strictly decrease or increase. The uniqueness of incoming and outgoing cars ensures that any two such paths either coincide or are disjoint.

A path containing \(t\) stations has \(t-1\) cars. Thus, if a company has \(m\) paths, then \[ k=n^2-m, \qquad\text{so}\qquad m=n^2-k. \] Any two distinct stations on one path are linked by that company.

The proposed value guarantees a common linked pair. Suppose \[ k=n^2-n+1. \] Each company then has exactly \(n-1\) paths. Assign to each station the ordered pair consisting of its \(A\)-path and its \(B\)-path. There are only \[ (n-1)^2<n^2 \] possible ordered pairs. By the pigeonhole principle, two distinct stations have the same pair. They lie on the same path for each company, so they are linked by both.

One fewer car does not suffice. Label the stations \(1,2,\ldots,n^2\) in increasing order of altitude. Give company \(A\) the cars \[ i\longrightarrow i+n \qquad (1\le i\le n^2-n), \] and give company \(B\) the cars \[ jn+r\longrightarrow jn+r+1 \qquad (0\le j\le n-1,\quad 1\le r\le n-1). \] Each company has exactly \(n(n-1)=n^2-n\) cars.

These arrangements satisfy all the required conditions. Every car goes uphill, and each company has distinct starting points and distinct finishing points. For \(A\), the finishing label is always the starting label plus \(n\); for \(B\), it is always the starting label plus \(1\). Hence a car starting higher also finishes higher.

Any two stations linked by \(A\) have labels congruent modulo \(n\). Meanwhile, every journey using \(B\) remains within one of the blocks \[ \{jn+1,jn+2,\ldots,jn+n\}, \qquad 0\le j\le n-1. \] Two distinct labels in the same block differ by an integer between \(1\) and \(n-1\), so they cannot be congruent modulo \(n\). Consequently, no two stations are linked by both companies.

For any smaller positive \(k\), retain any \(k\) cars of each company in this construction. Deleting cars preserves all the required conditions and cannot create a linked pair. Thus no smaller positive value guarantees the desired conclusion, proving the answer.

The solution was checked against the official IMO shortlist solutions.