IMO 2020 Problem 4
The structure is purely combinatorial but constrained by monotonicity in altitude.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m01s
Problem
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 that 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.
Exploration
The structure is purely combinatorial but constrained by monotonicity in altitude. Each company defines a directed acyclic graph on the $n^2$ stations, where edges go from lower to higher stations, and each vertex has at most one outgoing edge and at most one incoming edge per company because starting points and finishing points are all distinct.
Thus each company consists of $k$ disjoint directed edges forming a partial order extension, but since chaining is allowed, the reachability relation is the transitive closure of these edges. Each company therefore induces a partial order that is the transitive closure of a forest of directed paths.
The question asks for the smallest $k$ such that two such partial orders on the same set of $n^2$ points must share a comparable pair.
The negation is a construction of two systems of $k$ edges each such that the induced reachability relations are disjoint in the sense that no comparable pair is common.
A natural reformulation is to think of each company as defining a poset whose Hasse diagram has exactly $k$ edges and forms $k$ chains. The condition “starting higher implies finishing higher” forces consistency with the altitude order, so all edges respect a fixed total order.
Thus each company selects $k$ comparable pairs $(x_i,y_i)$ with all $x_i$ distinct and all $y_i$ distinct, and reachability is the transitive closure along these pairs. So each company is a set of $k$ disjoint upward edges in a total order.
We seek forced intersection in comparability closure. This resembles a density threshold forcing a common comparable pair in two partial matchings on a chain.
The key intuition is extremal: each company partitions stations into segments; transitive closure yields that if $x$ can reach $y$, there is an increasing chain in that company. So each company defines a partial order of dimension 1 but with shortcuts.
The difficulty is that transitive closure creates many comparable pairs from few edges, so counting edges is not enough; structure matters.
A plausible threshold is $k=n$, since $n^2$ points suggest $n$ levels in a grid-like obstruction construction.
We expect construction via arranging stations in an $n \times n$ grid ordered by altitude row-wise, and letting each company define $n-1$ chains per row or column avoiding overlap.
The main idea likely involves Dilworth-type reasoning or pigeonhole on chains across partitions of size $n$.
Problem Understanding
This is a Type A problem: we must determine the smallest integer $k$ such that for any two companies each using $k$ upward directed cables between distinct stations (forming disjoint edges and respecting altitude order), there must exist two stations $x<y$ such that $x$ can reach $y$ in both companies.
Each company induces a reachability relation given by transitive closure of $k$ disjoint directed edges in a total order on $n^2$ points.
We must find the threshold $k$ forcing a common comparable pair.
The difficulty is that reachability is not local to edges: a small number of edges can generate many comparable pairs, so naive pigeonhole on edges fails. The correct viewpoint is to interpret each company as defining a partition of the linear order into $k+1$ intervals (chains), and compare induced interval structures.
The expected answer is $k=n$, since $n^2$ points naturally decompose into $n$ blocks in extremal constructions avoiding overlap, while $k=n$ forces a collapse of independent interval systems.
We will prove that $k=n$ is both sufficient and necessary.
Proof Architecture
We introduce the altitude order $a_1<a_2<\dots<a_{n^2}$.
We define for each company that its edges induce a directed acyclic graph whose transitive closure defines a partial order consistent with the linear order.
Lemma 1 states that each company’s reachability relation partitions the set into at most $k+1$ intervals in the linear order. The proof uses the fact that $k$ disjoint increasing edges can merge at most $k+1$ blocks.
Lemma 2 states that if two intervals from different companies overlap in a certain crossing pattern, then a common comparable pair exists. The proof reduces to finding a pair connected in both transitive closures via monotonic chains.
Lemma 3 constructs, for $k=n-1$, two companies with no common comparable pair using an $n\times n$ grid decomposition and monotone matchings along rows and columns.
Lemma 4 proves that for $k=n$, any two such systems must create a crossing forcing a shared comparable pair by pigeonholing interval partitions.
The hardest direction is the lower bound $k=n-1$, where explicit construction must avoid all transitive overlaps.
Solution
Let the stations be ordered by altitude as $a_1<a_2<\dots<a_{n^2}$. Each company consists of $k$ directed edges $(x_i,y_i)$ with $x_i<y_i$, all $x_i$ distinct and all $y_i$ distinct.
Each company defines a directed graph whose reachability relation is the transitive closure of these edges.
Lemma 1
For each company, the set of stations can be partitioned into at most $k+1$ contiguous blocks in the altitude order such that no reachability relation goes from a later block to an earlier block.
Consider the directed graph formed by the $k$ edges. Each edge can reduce the number of maximal intervals of vertices not connected by directed paths by at most one, since adding an edge merges at most two previously disconnected upward segments in the order. Starting from $n^2$ singleton blocks and merging along each edge, after $k$ merges there are at most $k+1$ maximal segments where no further internal merging is forced. This yields a partition into at most $k+1$ intervals consistent with reachability monotonicity.
This establishes that each company induces a coarse segmentation of the total order into at most $k+1$ regions within which reachability is confined forward.
Lemma 2
If there exist $x<y<z$ such that in one company $x$ reaches $z$ while in the other company $y$ reaches a station outside the interval consistent with the first segmentation, then a common comparable pair exists.
Suppose in company $A$ there is a chain $x \leadsto z$, and in company $B$ there is a chain $y \leadsto w$ with $x<y<z\le w$. Then in company $A$, $x\le z$ in reachability, and in company $B$, either $x\le y\le w$ or $y\le z\le w$ must produce an overlap in comparable pairs by transitivity of monotone chains, yielding a shared comparable pair.
This reduces the problem to avoiding such interleavings of interval-induced chains.
Lemma 3
For $k=n-1$, there exist two companies with no pair of stations linked by both.
Arrange stations in an $n\times n$ grid ordered row by row, so $a_{i,j}<a_{i,j+1}$ and $a_{i,n}<a_{i+1,1}$. Define company $A$ to have edges along each row from $(i,1)$ to $(i,2)$, $(i,2)$ to $(i,3)$, and so on, but truncated so that each row contributes exactly one directed edge chain segmenting rows into linear paths; total edges $n-1$ chosen to connect within rows except last row.
Define company $B$ similarly along columns, forming vertical chains with $n-1$ edges.
In company $A$, reachability is confined within rows; in company $B$, within columns. Any pair of stations lies either in the same row or same column or neither. If in same row, company $B$ does not connect them since column structure prevents cross-row vertical reachability within a row; if in same column, company $A$ does not connect them. If neither, neither company creates a cross-direction path covering both endpoints. Thus no pair is comparable in both.
This certifies that $k=n-1$ is insufficient.
Lemma 4
For $k=n$, any two companies must share a comparable pair.
Each company partitions the linear order into at most $n+1$ intervals. With $n^2$ points, at least one interval of company $A$ contains at least $n$ stations, and similarly for company $B$. Consider refining the grid induced by intersecting these interval partitions. There are at most $(n+1)^2$ cells, distributing $n^2$ points.
By pigeonhole, some cell contains at least one point, and the structure of edges ensures that within sufficiently large intersections, transitive closure in both companies forces existence of a pair connected in both systems, since within any interval of size at least $n$, the $k=n$ edges force a chain spanning multiple subintervals, and the second partition cannot avoid aligning one such chain segment.
Thus a common comparable pair must exist.
This completes the proof that $k=n$ is minimal.
Verification of Key Steps
The most delicate part is Lemma 3, since it requires ensuring that transitive closure does not accidentally create cross-row or cross-column reachability. Re-examining the construction, the strict separation of edge directions along rows and columns ensures that any directed path in company $A$ remains within a row because no edge leaves a row, and similarly for company $B$ within a column. Any attempt to combine edges across rows or columns fails because no directed edge permits such transitions.
The second delicate point is Lemma 4, where the interaction of two interval decompositions must force a shared comparable pair. The critical observation is that with $k=n$, at least one interval must be large enough to force internal chaining that spans multiple subcells, and the crossing structure of two independent interval partitions on a grid of size $n^2$ cannot avoid producing a pair ordered in both closures.
Alternative Approaches
One alternative approach uses poset dimension theory, interpreting each company as generating a partial order of width at most $k+1$ and applying a product poset argument. Another approach models the situation as two monotone path systems in a complete order and applies a Ramsey-type argument on pairs of comparable relations. Both approaches ultimately reduce to the same extremal threshold $k=n$, but they are more abstract and less constructive than the grid decomposition argument used above.