Problem

Source: Irmo 2018 p1 q4

Tags: rectangle, combinatorics, combinatorial geometry



We say that a rectangle with side lengths $a$ and $b$ fits inside a rectangle with side lengths $c$ and $d$ if either ($a \le c$ and $b \le d$) or ($a \le d$ and $b \le c$). For instance, a rectangle with side lengths $1$ and $5$ fits inside another rectangle with side lengths $1$ and $5$, and also fits inside a rectangle with side lengths $6$ and $2$. Suppose $S$ is a set of $2019$ rectangles, all with integer side lengths between $1$ and $2018$ inclusive. Show that there are three rectangles $A$, $B$, and $C$ in $S$ such that $A$ fits inside $B$, and $B$ fits inside $C$.