Irish Mathematical Olympiad

We write $R \le R'$ if $R$ fits inside $R'$. (Note that $\le$ is a preorder: it is reflexive and transitive. It might not be a partial order because two different rectangles might have matching widths and lengths.)
We call an $n$-element subset $C$ of $S$ an $n$-chain if its elements can be listed in "increasing order", i.e. in the form
$$R_1 \le R_2 \le \dots \le R_n$$
An $n$-chain is allowed to contain congruent rectangles; for example, all $n$ rectangles $R_1, R_2, \dots, R_n$ may be congruent to each other. We call $A \subset S$ an anti-chain if it contains no 2-chains. In particular, no two rectangles are congruent in an anti-chain. For each rectangle $R$ in $S$, we select a chain $GR$ with $R$ as a maximal element, and which has maximal cardinality among chains having $R$ as a maximal element. Let $f(R)$ be the size of $GR$.
Claim 1: The subset $f^{-1}(n)$ is an anti-chain for all $n \in N$.
To prove this claim, it suffices to show that if $f(R) = f(R')$ for distinct $R, R' \in S$, then $\{R, R'\}$ is an anti-chain. But this is easy since if $f(R) = f(R')$ and if $R' \le R$, then $S_R \cup \{R\}$ is a chain with maximal element $R$ and size $f(R) + 1$, contradicting the definition of $f(R)$.
Claim 2: An anti-chain $A$ of $S$ has at most $1009$ elements.
Let $A$ be an anti-chain with $n$ elements: $A = \{R_1, \dots, R_n\}$, where the width and length of $R_i$ are $w_i$ and $l_i$, respectively, with $w_i \le l_i$.

We assume that the rectangles are ordered so that $w_i \le w_j$ for $i \le j$. If $w_i = w_j$ for some $i < j$, then it is clear that $\{R_i, R_j\}$ is a chain, contradicting our anti-chain assumption. Similarly, we deduce that $l_i$ must be strictly decreasing in $i$. Thus, we have numbers
$$w_1 < w_2 < \dots < w_n \le l_n < \dots < l_2 < l_1.$$
There are at least $2n - 1$ distinct numbers above, and all are between $1$ and $2018$, so $2n - 1 \le 2018$ and we deduce Claim 2.
Combining Claim 1 and Claim 2, we see that $f^{-1}(1) \cup f^{-1}(2)$ has at most $2018$ elements. Since this is less than the cardinality of $S$, we must have $f(R) \ge 3$ for some $R \in S$, as required.

We represent a rectangle by the ordered pair $(x, y)$ of its side lengths, where $x \le y$. We shall write $(x_1, y_1) \le (x_2, y_2)$ if $x_1 \le x_2$ and $y_1 \le y_2$. When the $x_i$ are positive, this means that a rectangle with side lengths $x_1$ and $y_1$ fits inside a rectangle with side lengths $x_2$ and $y_2$. A set of ordered pairs will be called a chain if its elements can be listed as $R_1, R_2, \dots, R_n$ such that $R_i \le R_j$ whenever $i \le j$.
Let $T(m, n)$ be the set of all pairs $(x, y)$ of integers that satisfy $m \le x \le y \le n$. Of course, $T(m, n)$ is empty if $m > n$ and it contains exactly one element, namely $(m, m)$, if $m = n$. More generally, if $d = n - m \ge 0$, the number of elements in $T(m, n)$ is equal to the triangular number
$$t_{d+1} = \sum_{i=1}^{d+1} i = \frac{1}{2}(d+1)(d+2).$$
To see this, observe that, for $i = 1, 2, \dots, d+1$, the pair $(x, m + i - 1)$ is in $T(m, n)$ exactly for $i$ values of $x$, namely $x = m, m+1, \dots, m+i-1$.
Because we do not identify congruent rectangles that are different, some pairs $(x, y)$ may appear more than once in the set $S$ mentioned in the problem. We will describe $S$ by selecting a subset $S_0$ of $T(1, 2018)$ and attaching to each of its elements a multiplicity. Multiplicities are positive integers and they represent the number of rectangles in $S$ that have the given side lengths.
More formally, $S$ is represented by $S_0 \subset T(1, 2018)$ together with a map $\mu: S_0 \to \mathbb{Z}_+$ that takes values in the positive integers. We will then write $S = (S_0, \mu)$. The number of elements in $S$ is equal to $\sum_{R \in S_0} \mu(R)$. A chain in $S$ is a chain in $S_0$, but when we calculate its length, we take multiplicities into account. For example, if $S_0$ contains just one element but the multiplicity of it is three, then $S$ contains a chain of length three, consisting of three congruent rectangles, the side lengths of which give the element of $S_0$.

We are going to prove the following slightly more general statement by induction on $d = n - m \ge 1$ for odd $d$.
Claim. If $S = (S_0, \mu)$ where $S_0$ is a subset of $T(m,n)$, $n - m$ is odd and $\mu: S_0 \to \mathbb{Z}_+$ is a map such that $\sum_{R \in S_0} \mu(R) \ge n - m + 2$, then $S$ contains a chain with at least three elements.
Note that the validity of this claim depends on $d = n - m$ only and not on the individual values of $m$ and $n$, because $(x_1 - k, y_1 - k) \le (x_2 - k, y_2 - k)$ is equivalent to $(x_1, y_1) \le (x_2, y_2)$ for any integer $k$.
Let $E(m, n)$ be the subset of $T(m, n)$ that consists of those pairs $(x, y)$ for which $x = m$ or $y = n$. If $d = n - m = 1$ we have $E(m, n) = T(m, n)$. Note that $E(m, n)$ is a chain for any $d = n - m \ge 1$, because
$$(m, m) \le (m, m+1) \le \dots \le (m, n-1) \le (m, n) \le (m+1, n) \le \dots \le (n, n).$$
A crucial observation for the proof is that for $d \ge 2$ the set $T(m, n)$ is the disjoint union of $E(m, n)$ and $T(m+1, n-1)$.
In the inductive step we use the claim for $d-2$ when we prove the claim for $d$. Because we deal with odd $d$ only, it suffices to consider $d=1$ in the base case of the induction.
If $d=1$, the set $T(m, n) = T(m, m+1)$ contains three elements, namely $(m, m) \le (m, m+1) \le (m+1, m+1)$, so it is a chain. Therefore, any possible set $S$ in this case is a chain as well.
For the inductive step, we assume that $S' = (S_0, \mu')$ contains a three-element chain if it contains at least $n' - m' + 2$ elements, $S'_0 \subset T(m', n')$ and $0 < n' - m' = n - m - 2$.
Suppose $S = (S_0, \mu)$ contains at least $n - m + 2$ elements and $S_0 \subset T(m, n)$. We consider $S_0 \cap E(m, n)$ and $S_0 \cap T(m+1, n-1)$. Because $E(m, n)$ is a chain, $S \cap E(m, n)$, which is $S_0 \cap E(m, n)$ with the multiplicities given by $\mu$, is a chain as well. If this set with multiplicities contains at least three elements, the proof is finished. Otherwise, $S \cap T(m+1, n-1)$, i.e. $S_0 \cap T(m+1, n-1)$ equipped with the multiplicities given by $\mu$, contains at least $n - m + 2 - 2 = (n-1) - (m+1) + 2$ elements, hence it contains a chain with at least three elements by the inductive assumption. This proves the claim.
The statement of the problem follows now because $d = n - m = 2018 - 1 = 2017$ for $T(1, 2018)$ and $S$ is supposed to contain $2019 = n - m + 2$ elements.