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$.
Problem
Source: Irmo 2018 p1 q4
Tags: rectangle, combinatorics, combinatorial geometry
10.01.2019 13:04
We prove the general case : In a set of $n+1$ ,$(n\geq 2)$ rectangles with integer sides in $[1,n]$ , there exists three rectangles $A,B,C$ such that $A$ fits in $B$ and $B$ fits in $C$. Let $R(a,b)$ be the rectangle with side lengths $a$ and $b$. We use strong induction on $n$. Base case : If $n=2$ there are three rectangles with integer sides in $[1,2]$ ,respectively $R(1,1) ,R(2,1) ,R(2,2) $ and clearly $R(1,1)$ fits in $R(2,1)$ and $R(2,1)$ fits in $R(2,2)$. Inductive step : Assume that for $n=1,2,\dots ,n-1$ the result holds . Now ,if we have $n+1$ rectangles with integer sides in $[1,n]$, we consider three cases . Firs case : None or one of rectangles has a side length of $n$ . In either case there are $n$ rectangles with sides in $[1,n-1]$ and by inductive hypothesis we are done. Second case : More than three rectangles have a side length of $n$ . Let any three of them be $R(n,a) ,R(n,b) $ and $R(n,c)$ and W.L.O.G $a\leq b\leq c$ ,clearly they fit in eachother. Third case : Exactly $2$ of rectangles have a side length of $n$. Let these two be $R(n,a)$ and $R(n,b)$ , and $a\leq b$ , if one of other rectangles have a side length smaller than $b$ we are done , but if all other rectangles have side length greater than $b$ , we consider the worst case scenario , when $b=1$ , so all other $n-1$ rectangles have sides in $[2,n-1]$ wich can be transformed to $[1,n-2]$ , and by induction hypothesis these $n-1$ rectangles have three rectangles such that one fits to another. $\blacksquare$