Estonian Mathematical Olympiad

Call a figure coverable if it can be exactly covered by rectangles of size $2\times 3$ and $3\times 2$. Let the original rectangle be of size $(a+d)\times (b+c)$ and let the figure remaining after cutting out the upper left corner of size $a\times b$ be coverable (Fig. 52). This would be impossible if $c=1$ or $d=1$, whence we can assume in the rest that $c\ge 2$ and $d\ge 2$. Coverability implies that $6\mid ac+bd+cd$. Also one can notice that a rectangle of integral side lengths $n\times m$ where $n\ge 2$ and $m\ge 2$ is coverable if and only if $6\mid nm$. Indeed, rectangles of size $2k\times 3l$ and $3l\times 2k$ are obviously coverable, Fig. 52

whereas rectangles of size $6k\times (6l\pm 1)$ can be divided into rectangles of size $6k\times 3$ ja $6k\times 2s$, both of which are coverable by the above; the symmetric case is analogous. Since $2\mid ac+bd+cd$, at least one of $a,b,c$ and $d$ must be even. We show next that at least one of $a,b,c$ and $d$ must be divisible by 3. For that, suppose the contrary, i.e., none of $a,b,c$ and $d$ being divisible by 3. If either $3\mid a+d$ or $3\mid b+c$ then $3\mid bd$ or $3\mid ac$, respectively, because $3\mid ac+bd+cd$. Since 3 is prime, we obtain a contradiction. Hence $3\nmid a+d$ and $3\nmid b+c$. Thus either $a\equiv d\equiv 1(\mathrm{mod}3)$ or $a\equiv d\equiv 2(\mathrm{mod}3)$, as well as either $b\equiv c\equiv 1(\mathrm{mod}3)$ or $b\equiv c\equiv 2(\mathrm{mod}3)$. If either $a\equiv b\equiv c\equiv d\equiv 1(\mathrm{mod}3)$ or $a\equiv b\equiv c\equiv d\equiv 2(\mathrm{mod}3)$ then color the squares of the figure by the rising diagonals with 3 colors. If either $a\equiv d\equiv 1(\mathrm{mod}3)$ and $b\equiv c\equiv 2(\mathrm{mod}3)$ or $a\equiv d\equiv 2(\mathrm{mod}3)$ and $b\equiv c\equiv 1(\mathrm{mod}3)$ then color the squares of the figure by the falling diagonals with 3 colors. The area to be covered, except for the neighborhood of the meeting point of the cutting lines of the original rectangle that can be of four different shape (in Figures 53–56, this area is marked by bullets and framed with bold line), can be cut into strips of size $3k\times 1$ and $1\times 3l$ containing an equal amount of unit squares of each color. Hence the area that should be coverable by assumption contains different number of unit squares of different color, which is impossible as every $2\times 3$ and $3\times 2$ rectangle contains the same number of unit squares of each color. As we got a contradiction in every case, we have proven that at least one of $a,b,c$ and $d$ is divisible by 3. Fig. 53 Fig. 54 Fig. 55 Fig. 56 It remains to show that one of the small rectangles is coverable whenever one of $a,b,c$ and $d$ is divisible by 2 and also one of $a,b,c$ and $d$ is divisible by 3. The following table shows for each case which of the small rectangles is coverable:

	3 \mid a	3 \mid b	3 \mid c	3 \mid d
2 \mid a	a \times c	a \times b	a \times c	a \times c
2 \mid b	a \times b	d \times b	d \times b	d \times b
2 \mid c	a \times c	d \times b	d \times c	d \times c
2 \mid d	a \times c	d \times b	d \times c	d \times c

One can show this by the following case study: If one of $a$ and $d$ is divisible by one of 2 and 3 and one of $b$ and $c$ is divisible by the other of 2 and 3 then the corresponding small rectangle is coverable. (Fills all squares outside the two long diagonals of the table.) If $6\mid a$ or $6\mid d$ then $a\times c$ or $d\times c$ is coverable, respectively, since $c\ge 2$ and the other side length is long enough by divisibility. Similarly, if $6\mid b$ or $6\mid c$ then $d\times b$ or $d\times c$ is coverable, respectively. (Fills all squares of the main diagonal of the table.) If $a$ is divisible by one of 2 and 3 and $d$ is divisible by the other of 2 and 3 then, by $6\mid ac+bd+cd$, we must have $6\mid ac$. As $a\ge 2$ (by divisibility) and $c\ge 2$, the rectangle $a\times c$ is coverable. Similarly, if $b$ is divisible by one of 2 and 3 and $c$ is divisible by the other of 2 and 3 then $d\times b$ is coverable. (Fills all squares of the secondary diagonal of the table.)

---

Alternative solution.

The central claim that neither $a\equiv d\not\equiv 0(\mathrm{mod}3)$ nor $b\equiv c\not\equiv 0(\mathrm{mod}3)$ can hold can be proven as follows. Color the grid by rows with three colors. Note that each rectangle of size $2\times 3$ or $3\times 2$ contains either exactly 2 unit squares of every color or 3 unit squares of each of some two colors and 0 squares of the third color. In both cases, the numbers of covered unit squares of all colors are congruent modulo 3. Thus if the figure obtained after cutting out the rectangle of size $a\times b$ were coverable, the numbers of unit squares of all colors within this area should be congruent modulo 3. We can show that in no cases this is so. As the numbers of unit squares of all colors in 3 consecutive rows of equal length are equal, it suffices to consider the area in the middle that remains after repeatedly removing horizontal strips of width 3 from both top and bottom. If $b\equiv c\equiv 1(\mathrm{mod}3)$ (Figures 57 and 58) then the numbers of unit squares of the three colors in the remaining area are $a+d$, $d$ and 0. These numbers are incongruent modulo 3, regardless of the remainders of $a$ and $d$. * If $b\equiv c\equiv 2(\mathrm{mod}3)$ (Figures 59 and 60) then the numbers of unit squares of the three colors in the remaining area are $a+2d$, $a+d$ and $d$. These numbers are also incongruent modulo 3, regardless of the remainders of $a$ and $d$. Fig. 57 Fig. 58 Fig. 59 Fig. 60