48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Call the directions of the sides of the square horizontal and vertical. A horizontal or vertical line, which intersects the interior of the square but does not intersect the interior of any rectangle, will be called a splitting line. A rectangle having no point on the boundary of the square will be called an interior rectangle.

Suppose, to the contrary, that there exists a dissection of the square into more than one rectangle, such that no interior rectangle and no splitting line appear. Consider such a dissection with the least possible number of rectangles. Notice that this number of rectangles is greater than $2$, otherwise their common side provides a splitting line.

If there exist two rectangles having a common side, then we can replace them by their union (see Figure 1).



Figure 1

The number of rectangles was greater than $2$, so in a new dissection it is greater than $1$. Clearly, in the new dissection, there is also no splitting line as well as no interior rectangle. This contradicts the choice of the original dissection.

Denote the initial square by $ABCD$, with $A$ and $B$ being respectively the lower left and lower right vertices. Consider those two rectangles $a$ and $b$ containing vertices $A$ and $B$, respectively. (Note that $a\ne b$, otherwise its top side provides a splitting line.) We can assume that the height of $a$ is not greater than that of $b$. Then consider the rectangle $c$ neighboring to the lower right corner of $a$ (it may happen that $c=b$). By aforementioned, the heights of $a$ and $c$ are distinct. Then two cases are possible.



Figure 3

Case 1. The height of $c$ is less than that of $a$. Consider the rectangle $d$ which is adjacent to both $a$ and $c$, i.e. the one containing the angle marked in Figure 2. This rectangle has no common point with $BC$ (since $a$ is not higher than $b$), as well as no common point with $AB$ or with $AD$ (obviously). Then $d$ has a common point with $CD$, and its left side provides a splitting line. Contradiction.

Case 2. The height of $c$ is greater than that of $a$. Analogously, consider the rectangle $d$ containing the angle marked on Figure 3. It has no common point with $AD$ (otherwise it has a common side with $a$), as well as no common point with $AB$ or with $BC$ (obviously). Then $d$ has a common point with $CD$. Hence its right side provides a splitting line, and we get the contradiction again.

---

Alternative solution.

Again, we suppose the contrary. Consider an arbitrary counterexample. Then we know that each rectangle is attached to at least one side of the square. Observe that a rectangle cannot be attached to two opposite sides, otherwise one of its sides lies on a splitting line.

We say that two rectangles are opposite if they are attached to opposite sides of $ABCD$. We claim that there exist two opposite rectangles having a common point.

Consider the union $L$ of all rectangles attached to the left. Assume, to the contrary, that $L$ has no common point with the rectangles attached to the right. Take a polygonal line $p$ connecting the top and the bottom sides of the square and passing close from the right to the boundary of $L$ (see Figure 4). Then all its points belong to the rectangles attached either to the top or to the bottom. Moreover, the upper end-point of $p$ belongs to a rectangle attached to the top, and the lower one belongs to another rectangle attached to the bottom. Hence, there is a point on $p$ where some rectangles attached to the top and to the bottom meet each other. So, there always exists a pair of neighboring opposite rectangles.



Figure 4



Figure 5



Figure 6

Now, take two opposite neighboring rectangles $a$ and $b$. We can assume that $a$ is attached to the left and $b$ is attached to the right. Let $X$ be their common point. If $X$ belongs to their horizontal sides (in particular, $X$ may appear to be a common vertex of $a$ and $b$), then these sides provide a splitting line (see Figure 5). Otherwise, $X$ lies on the vertical sides. Let $\ell$ be the line containing these sides.

Since $\ell$ is not a splitting line, it intersects the interior of some rectangle. Let $c$ be such a rectangle, closest to $X$; we can assume that $c$ lies above $X$. Let $Y$ be the common point of $\ell$ and the bottom side of $c$ (see Figure 6). Then $Y$ is also a vertex of two rectangles lying below $c$.

So, let $Y$ be the upper-right and upper-left corners of the rectangles $a^{\prime }$ and $b^{\prime }$, respectively. Then $a^{\prime }$ and $b^{\prime }$ are situated not lower than $a$ and $b$, respectively (it may happen that $a=a^{\prime }$ or $b=b^{\prime }$). We claim that $a^{\prime }$ is attached to the left. If $a=a^{\prime }$ then of course it is. If $a\ne a^{\prime }$ then $a^{\prime }$ is above $a$, below $c$ and to the left from $b^{\prime }$. Hence, it can be attached to the left only.

Analogously, $b^{\prime }$ is attached to the right. Now, the top sides of these two rectangles pass through $Y$, hence they provide a splitting line again. This last contradiction completes the proof.