Maths Olympiad Prep

Library / /232 of 299

Geometry Difficulty 7.1 National Olympiad, round 2 Prove it Iran

Find the maximum number of rectangles with sides equal to 11 and 22 and parallel to the coordinate axes such that each two have an area equal to 11 in common.

Solution

The answer is 55. The picture below shows five 1×21 \times 2 rectangles mutually intersecting at rectangles with unit area.
Figure 1
It is enough to show that there are no six 1×21 \times 2 horizontal or vertical rectangles with such a property. Assume that there are 66 such rectangles.
Note that it is obvious that the intersection of two rectangles with parallel sides is again a rectangle. In solution first we show that there are at most three vertical and three horizontal rectangles. At the end we show that there are not three horizontal and three vertical rectangles satisfying the intersection property. For these we prove some lemmas.

Lemma 1. Composition of a reflection with respect to a point and a translation in the plane, is a reflection, too.
Proof. Let OO be the center of the reflection, and v\vec{v} be the vector of the translation. Then by Thales' Theorem it is easy to see the composition is a reflection with respect to point OO' such that OO=12vOO' = \frac{1}{2}\vec{v}.

Lemma 2. Let KK be a strictly convex shape in the plane. For any real number r>0r > 0 and any direction in the plane, there are at most two slices of KK with length rr parallel to the given direction. (We mean by a slice of KK, intersection of a line in the plane with KK. Obviously each slice is a line segment.)
Proof. Assume to the contrary there are three slices of length rr parallel to the given direction, say AAAA', BBBB' and CCCC'. Suppose that AA=BB=CC\overrightarrow{AA'} = \overrightarrow{BB'} = \overrightarrow{CC'} and BBBB' lies between two others.
If BB or BB' is outside the parallelogram AACCAA'C'C, then the other point lies in the interior of KK and therefore the intersection of line containing BBBB' has length greater than rr.
Figure 2
If BB lies on ACAC and BB' lies on ACA'C', then since KK is strictly convex there must be a point of KK between lines AAAA' and CCCC' outside the parallelogram, contradicts with the length rr of slice containing BBBB'.
Figure 3

Lemma 3. There are no four horizontal or four vertical rectangles satisfying the conditions.
Proof. Assume that there are at least 44 horizontal rectangles. By a horizontal scaling with factor 12\frac{1}{2} we go to the case that there are 44 unit squares with sides parallel to the axes, such that mutually intersecting at rectangles of area 12\frac{1}{2}.
Every unit square determined uniquely by its center. It is easy to see that two unit squares with centers (x,y)(x, y) and (x,y)(x', y') intersect at a rectangle of area 12\frac{1}{2} iff
(1xx)(1yy)=12()(1 - |x - x'|)(1 - |y - y'|) = \frac{1}{2} \quad (*)
Locus of points (x,y)(x', y') satisfying (*) (for fixed (x,y)(x, y)) is boundary of a strictly convex shape in the plane (Look at the shape below). We call such shape an oval with center (x,y)(x, y).
Figure 4
Suppose that A=(xA,yA)A = (x_A, y_A), B=(xB,yB)B = (x_B, y_B), C=(xC,yC)C = (x_C, y_C) and D=(xD,yD)D = (x_D, y_D) are the centers of these 44 squares such that yAyByCyDy_A \le y_B \le y_C \le y_D. Note that oval of BB is a translation of oval of AA with vector AB\vec{AB}. By lemma 22 these two ovals intersect in at most two points (Note that these ovals are strictly convex because they are intersection of 44 strictly convex shapes). These two points must be CC and DD. Since AA is center of symmetry of oval of AA, by lemma 11, these two intersection points are symmetric with respect to the midpoint of ABAB. Note that yB>yAy_B > y_A, because if yA=yBy_A = y_B, yCy_C or yDy_D become less than yA=yBy_A = y_B contradicts with the minimality of yAy_A. Now we have
yCyC+yD2=yA+yB2<yBy_C \le \frac{y_C + y_D}{2} = \frac{y_A + y_B}{2} < y_B
Contradicts with yByCy_B \le y_C.
Figure 5

Lemma 4. Every horizontal rectangle intersects every vertical rectangle in a 1×11 \times 1 square.
Proof. Intersection of such rectangles is a rectangle with sides at most 11. As intersection of every two rectangles has a unit area, both sides must be unit. □

Using lemma 33, we get that 33 rectangles are vertical (V) and other 33 are horizontal (H). Consider three horizontal rectangles with their centers sorted by xx. Fix the middle one and call it RmR_m. Call left and right rectangles RlR_l and RrR_r respectively. Without loss of generality, we can assume that RrR_r is not upper than RlR_l. As in the figure below RmR_m, RrR_r intersect in a rectangle with length β\beta and RmR_m, RlR_l intersect in a rectangle with length α\alpha. Left side of RrR_r, right side of RlR_l, top side of RlR_l and bottom side of RmR_m construct a rectangle named RHR_H. Width of RHR_H is wHw_H and height of it is hHh_H. These variables are based on rectangles in (H), we can define the same variables in (V) named RVR_V, wVw_V and hVh_V.
Figure 6
Referring to the lemma 44, every two rectangles, one in (V) and one in (H) intersect in a unit square. So every rectangle in (V) must have a horizontal side in RHR_H this means hVwHh_V \le w_H. Similarly we can show that hHwVh_H \le w_V. Without loss of generality, assume that wVwHw_V \le w_H. This yields:
hHwHh_H \le w_H
Now we can calculate all variables in terms of α,β\alpha, \beta (note that 1αβ21 \le \alpha \le \beta \le 2). Intersection of Rl,RrR_l, R_r is a rectangle with sides α+β2,11β+1α\alpha + \beta - 2, 1 - \frac{1}{\beta} + \frac{1}{\alpha} so:
(α+β2)×(11β+1α)=1(1)(\alpha + \beta - 2) \times \left(1 - \frac{1}{\beta} + \frac{1}{\alpha}\right) = 1 \quad (1)
We had hHwHh_H \le w_H. hH=21αh_H = 2 - \frac{1}{\alpha} and wH=α+β2w_H = \alpha + \beta - 2 so:
21αα+β2(2)2 - \frac{1}{\alpha} \le \alpha + \beta - 2 \quad (2)
Now we change our variables to have simpler results. Assume that:
α=a+1(0a1)\alpha = a + 1 \quad (0 \le a \le 1)
β=b+1(0b1)\beta = b + 1 \quad (0 \le b \le 1)
From (1) we have:
(b+a)(11b+1+1a+1)=1bbb+1+ba+1+aab+1+aa+1=1b2+bb+b(b+1)a+1+ab+aa+baa+1+aa+1=b+1Q(b)=b2(1+11+a)+ba1a+1=0 \begin{align*} & (b+a)\left(1 - \frac{1}{b+1} + \frac{1}{a+1}\right) = 1 \\ \Rightarrow \quad & b - \frac{b}{b+1} + \frac{b}{a+1} + a - \frac{a}{b+1} + \frac{a}{a+1} = 1 \\ \Rightarrow \quad & b^2 + b - b + \frac{b(b+1)}{a+1} + ab + a - a + \frac{ba}{a+1} + \frac{a}{a+1} = b + 1 \\ \Rightarrow \quad & Q(b) = b^2\left(1 + \frac{1}{1+a}\right) + ba - \frac{1}{a+1} = 0 \end{align*}
From (2) we conclude that the above quadratic polynomial must have a root in the interval [0,1][0, 1] satisfying the following condition:
21a+1a+b1a2a+1k=2a1a+1b2 - \frac{1}{a+1} \le a + b \Leftrightarrow \underbrace{1 - \frac{a^2}{a+1}}_{k} = 2 - a - \frac{1}{a+1} \le b
a[0,1]a \in [0, 1] so k[0,1]k \in [0, 1]. Coefficients of QQ are positive so QQ is ascending so to prove that bb cannot be a root of QQ, it's enough to show that Q(k)>0Q(k) > 0. Q(k)k2+ka1a+1Q(k) \ge k^2 + ka - \frac{1}{a+1} so we prove that k2+ka1a+10k^2 + ka - \frac{1}{a+1} \ge 0.
k2+ka1a+10(1a2a+1)2+(1a2a+1)a1a+10(a+1a2)2+a(a+1)(a+1a2)a+1(a+1a2)(2a+1)a+1 \begin{align*} & k^2 + ka - \frac{1}{a+1} \ge 0 \\ \Leftrightarrow \quad & (1 - \frac{a^2}{a+1})^2 + (1 - \frac{a^2}{a+1})a - \frac{1}{a+1} \ge 0 \\ \Leftrightarrow \quad & (a + 1 - a^2)^2 + a(a + 1)(a + 1 - a^2) \ge a + 1 \\ \Leftrightarrow \quad & (a + 1 - a^2)(2a + 1) \ge a + 1 \end{align*}
Equivalently,
2a(a+1)a2(2a+1)=2a3+a2+2a=a(2a2a2)02a(a+1) - a^2(2a+1) = -2a^3 + a^2 + 2a = -a(2a^2 - a - 2) \geq 0
a[0,1]a \in [0, 1] so the last inequality is obvious because 2a2a2=(a2a)+(a21)12a^2 - a - 2 = (a^2 - a) + (a^2 - 1) - 1. Thus we showed that there is no aa with those algebraic properties. This means there is no α\alpha with that geometric properties and this is a big contradiction because α\alpha was a length in our figure. Now we can say there are no six 1×21 \times 2 rectangles mutually intersecting at rectangles with unit area. This yields there are no n>5n > 5 such rectangles.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.