A Bunch of Rectangles. Topic: Pigeonhole Principle. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) Suppose we have $101$ rectangles with sides of integer lengths not exceeding $100$. Prove that there exist three of these rectangles, which we call $A$, $B$, and $C$, such that $A$ fits wholly inside $B$ and $B$ fits wholly inside $C$. (Note: If two rectangles are identical, then each ‘fits’ inside the other.)

Solution: Well, again the numbers suggest Pigeonhole, so we get right to it. We want to construct sets of rectangles such that any three rectangles in each set would satisfy the condition. It might help to redefine the condition. Let $ l_X $ and $ w_X $ denote the length and width of rectangle $ X $, respectively. We may assume $ w_X \le l_X $ or we just switch the values for $ l_X $ and $ w_X $ to obtain the same rectangle. We want to find rectangles $ A,B,C $ such that $ w_A \le w_B \le w_C $ and $ l_A \le l_B \le l_C $.

Consider plotting rectangles on the coordinate plane with the axes equal to $ w_X $ and $ l_X $. All the rectangles lie below or on the line $ w_X = l_X $ (shown in blue below. We want to create fifty different holes to guarantee that three fall into a single one; all while keeping in mind that any three in a hole must satisfy our condition. Consider the following holes (shown in red):



If we continue these sets of red lines until the entire portion of the graph we want is full, we will have exactly fifty. Algebraically defined, we have

$ S_k = \{(w_X,l_X) | w_X = k, k \le l_X \le 101-k\} \cup \{(w_X, l_X) | l_X = 101-k, k \le w_X \le 101-k} $ for $ 1 \le k \le 50 $.

Since we have $ 50 $ holes and $ 101 $ pigeons, we know there are at least $ 3 $ pigeons in a single hole, or three rectangles in a single set. From the graph, it's easy to see that if three rectangles lie on either the vertical or horizontal line of any set, they fit within each other. They all have one equal dimension, so we just arrange the other dimension in nondecreasing order. If two lie on a vertical line and the third on the horizontal, the third is clearly the smallest and then arrange the other two in nondecreasing order by length. Similarly, if two lie on a horizontal line and a third on the vertical, the third is the largest and arrange the other two in nondecreasing order by width. Hence the problem is solved. QED.

--------------------

Comment: More good Pigeonhole practice. Transfering the problem onto the graph and then determining the sets were the key steps, and the details pretty much worked themselves out from there. It's often a good idea to reduce things to algebra instead of geometry - in reality, this problem had nothing to do with geometry.

--------------------

Practice Problem: If you wanted four rectangles that fit inside each other, how many total rectangles would you need? Five? $ n $?