\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{IMO 2020/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 30}
\maketitle
\section*{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 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.
\section*{Video}
\href{https://www.youtube.com/watch?v=JfRrlvbzKHk}{\texttt{https://youtu.be/OxeeSsdEgwI}}
\newpage
\section*{Solution}
Answer: $k = n^2 - n + 1$.
When $k = n^2-n$,
the construction for $n=4$ is shown below which generalizes readily.
(We draw $A$ in red and $B$ in blue.)
\begin{center}
\begin{asy}
pair P(int i, int j) { return (i+j/10, j+i/10); }
dotfactor *= 2;
for (int i=0; i<4; ++i) {
for (int j=0; j<4; ++j) {
dot( P(i,j) );
if (j!=0) {
draw(P(i,j-1)--P(i,j), red, EndArrow, Margin(4,4));
}
if (i != 0) {
draw(P(i-1,j)--P(i,j), blue, EndArrow, Margin(4,4));
}
}
}
\end{asy}
\end{center}
To see this is sharp, view $A$ and $B$ as graphs
whose connected components are paths (possibly with $0$ edges;
the direction of these edges is irrelevant).
Now, if $k = n^2-n+1$ it follows that $A$ and $B$
each have exactly $n-1$ connected components.
But in particular some component of $A$ has at least $n+1$ vertices.
This component has two vertices in the same component of $B$, as desired.
\begin{remark*}
The main foothold for this problem is the hypothesis
that the number of stations should be $n^2$ rather than, say, $n$.
This gives a big hint towards finding the construction
which in turn shows how the bound can be computed.
On the other hand, the hypothesis that
``a cable car which starts higher
also finishes higher'' appears to be superfluous.
\end{remark*}
\end{document}