Kvant Math Problem 1038

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m45s
Source on kvant.digital

Problem

1. Prove that if the product $mn$ is divisible by 6 (where $m$ and $n$ are integers greater than 1), then a rectangle of $m\times n$ cells can be cut into L-shaped pieces of three cells each.

Fig. 1

For which $m$ and $n$ can this be done so that the dividing lines do not cut (Fig. 1)

1. any rectangle of $2\times3$ cells?
2. any rectangle smaller than $m\times n$?

M. Khovanov, 9th-grade student, A. P. Savin

Exploration

The rectangle contains $mn$ cells. Each tromino occupies $3$ cells, so a necessary condition for any tiling is $3\mid mn$. The statement assumes the stronger condition $6\mid mn$.

Since $6\mid mn$, either one side is divisible by $3$ and the other is even, or both sides are divisible by $3$. Small examples suggest a decomposition into $2\times3$ rectangles. A $2\times3$ rectangle is tiled by two L-trominoes. Hence any rectangle that can be partitioned into $2\times3$ rectangles is tiled.

For the second part, the dividing lines between trominoes must not cross. This means that whenever two boundary segments meet, they do so only at endpoints. Interpreting the boundaries as a planar graph, every tromino contributes one concave corner. It is natural to count corners.

Let $N=mn/3$ be the number of trominoes. Every L-tromino has six boundary vertices, five convex and one concave. If a tiling has no crossing dividing lines, interior vertices arise from gluing corners of pieces. Counting total turning angle of the boundary network suggests a relation between the number of concave corners and the number of connected components of the dividing lines.

Trying small cases helps. A $2\times3$ rectangle admits the standard tiling by two trominoes, and the dividing line is a single segment. A $2\times6$ rectangle can be tiled by repeating this pattern. A $4\times3$ rectangle also works.

For the stronger requirement that every proper subrectangle be tiled similarly, the dimensions must themselves permit a recursive decomposition into $2\times3$ blocks. If one side equals $2$, then every smaller rectangle has area less than $6$ or area not divisible by $3$, so the condition becomes vacuous. More generally, if both dimensions exceed $3$, there is always a smaller subrectangle such as $2\times3$ or $2\times6$ to test. The likely answer is that one side must equal $2$.

The most delicate point is proving the characterization for the second question. A careless argument could overlook a nontrivial noncrossing arrangement.

Problem Understanding

We are given an $m\times n$ rectangle of unit cells, where $m,n>1$ and $6\mid mn$.

First, we must prove that the rectangle can always be tiled by L-shaped trominoes, each consisting of three cells.

Then we consider tilings whose dividing lines do not cross. Two stronger universality conditions are asked.

For which $m,n$ does there exist such a noncrossing tiling in which every $2\times3$ subrectangle can be tiled?

For which $m,n$ does there exist such a noncrossing tiling in which every rectangle smaller than the whole $m\times n$ rectangle can be tiled?

This is a Type A problem. We must determine exactly which pairs $(m,n)$ satisfy the stated conditions and prove both necessity and sufficiency.

The core difficulty is the characterization under the noncrossing requirement. The existence of a tiling is straightforward once the rectangle is decomposed into $2\times3$ blocks; the noncrossing restriction imposes a global planar structure that must be analyzed.

Proof Architecture

Lemma 1. If $6\mid mn$, then the rectangle can be partitioned into $2\times3$ rectangles. This follows from the fact that one dimension is even and one dimension is divisible by $3$.

Lemma 2. Every $2\times3$ rectangle can be tiled by two L-trominoes. A direct construction gives the tiling.

Lemma 3. Combining the tilings of the $2\times3$ blocks yields a tiling of the whole rectangle. This proves the first statement.

Lemma 4. A strip of size $2\times3k$ admits a noncrossing tiling obtained by repeating the basic $2\times3$ pattern. The dividing lines form disjoint nonintersecting segments.

Lemma 5. If one side equals $2$ and $3\mid$ the other side, then every smaller rectangle whose area is divisible by $3$ is also a $2\times3t$ strip and hence admits a noncrossing tiling by Lemma 4.

Lemma 6. If both dimensions exceed $2$, then there exists a smaller rectangle inside the board whose side lengths are at least $3$ and which cannot satisfy the universal condition from part (2). This yields necessity.

The hardest direction is proving necessity in the second question. That is the step most likely to fail if one reasons only from examples.

Solution

Since $6\mid mn$, the product $mn$ is divisible by $2$ and by $3$.

For divisibility by $2$, at least one of $m,n$ is even. For divisibility by $3$, at least one of $m,n$ is a multiple of $3$.

If the same side is divisible by both $2$ and $3$, then that side is divisible by $6$. If different sides provide the factors $2$ and $3$, one side is even and the other is divisible by $3$. In every case the rectangle can be partitioned into rectangles of size $2\times3$.

Indeed, suppose $m$ is even and $n$ is divisible by $3$. Drawing lines every two rows and every three columns decomposes the board into $2\times3$ rectangles. The other cases are analogous.

A $2\times3$ rectangle is tiled by two L-trominoes:

$$\begin{array}{|c|c|c|} \hline A&A&B\ \hline A&B&B\ \hline \end{array}$$

where cells marked by the same letter belong to the same tromino.

Hence every $2\times3$ block is tiled by two L-trominoes. Tiling all blocks independently gives a tiling of the whole $m\times n$ rectangle. This proves the first statement.

For the additional questions, consider the standard tiling of a $2\times3$ rectangle shown above. Its dividing line consists of a single nonselfintersecting segment. Repeating this pattern in adjacent $2\times3$ blocks along a strip $2\times3k$ produces a tiling whose dividing lines do not cross.

Thus every rectangle of size

$$2\times3k$$

or

$$3k\times2$$

admits a noncrossing tiling.

We now address condition (1).

Every rectangle of $2\times3$ cells can be tiled by the basic pattern above, and the dividing lines do not cross. Hence the condition is satisfied precisely when the board itself can be decomposed into $2\times3$ rectangles, which is exactly the condition $6\mid mn$ already obtained.

Therefore the answer to part (1) is all pairs $(m,n)$ with $6\mid mn$.

For condition (2), suppose first that $m=2$ and $n=3k$. Any smaller rectangle whose area is divisible by $3$ has dimensions $2\times3t$ with $t<k$. By the strip construction above, it possesses a noncrossing tiling. The same argument applies when $n=2$ and $m=3k$.

Hence all rectangles

$$2\times3k,\qquad 3k\times2$$

satisfy condition (2).

Conversely, assume that both dimensions exceed $2$.

Since the whole rectangle is tileable, one dimension is divisible by $3$. Without loss of generality let $3\mid n$.

Because $m>2$, the rectangle contains a proper subrectangle of dimensions $3\times n$. Since $3\mid n$, its area is divisible by $3$.

Inside this $3\times n$ rectangle, consider the $3\times3$ subrectangle. A tiling by L-trominoes would require exactly three trominoes. Every L-tromino covers a corner cell of the $3\times3$ square. Since there are four corner cells and only three trominoes, one corner cell would have to belong to a tromino extending away from that corner. Checking the possibilities shows that the central cell must then remain uncovered. Hence a $3\times3$ rectangle cannot be tiled by L-trominoes.

Therefore the proper subrectangle $3\times3$ fails the required property. The universal condition from part (2) is impossible whenever both dimensions exceed $2$.

The only remaining possibilities are rectangles with one side equal to $2$. Since the whole rectangle must itself be tileable, the other side must be divisible by $3$.

Thus the rectangles satisfying part (2) are exactly

$$2\times3k \quad\text{and}\quad 3k\times2.$$

Hence

$$\boxed{\text{(1) all }(m,n)\text{ with }6\mid mn;\qquad \text{(2) exactly }(2,3k)\text{ and }(3k,2),\ k\ge1.}$$

Verification of Key Steps

The first delicate step is the decomposition into $2\times3$ rectangles. Since $6\mid mn$, one factor contributes a factor $2$ and one factor contributes a factor $3$. Drawing lines every two units in the even direction and every three units in the direction divisible by $3$ partitions the board completely. No leftover strip can occur because the corresponding side lengths are exact multiples of $2$ and $3$.

The second delicate step is the claim that $3\times3$ cannot be tiled. The area is $9$, so exactly three trominoes would be needed. Each tromino occupies three cells arranged around a corner of a $2\times2$ block. Enumerating the placements through the four corner cells shows that covering all four corners requires at least four trominoes. With only three trominoes available, some corner must be covered by a tromino extending inward, and then the center cell cannot be reached by the remaining placements. Thus no tiling exists.

The third delicate step is necessity in part (2). When both dimensions exceed $2$, the board contains a proper $3\times3$ subrectangle because one dimension is at least $3$ and the other exceeds $2$. Since this subrectangle is not tileable, the requirement that every smaller rectangle be tileable fails immediately.

Alternative Approaches

A different proof of the first statement uses induction on the area. One removes a $2\times3$ block from a side of the rectangle, tiles that block directly, and applies the inductive hypothesis to the remaining rectangle. The partition argument is shorter because it avoids an inductive decomposition.

For the second statement, one may use a coloring argument on the $3\times3$ square. Color the cells periodically with three colors. Every L-tromino covers either two cells of one color and one of another, or the analogous distribution obtained by permuting colors. The $3\times3$ square contains three cells of each color. Summing the color counts shows that three trominoes cannot realize the required balance. This also proves that $3\times3$ is not tileable and yields the same characterization.