Kvant Math Problem 144

Consider small rectangles with integer sides.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m55s
Source on kvant.digital

Problem

Find the necessary and sufficient conditions that the numbers $a$, $b$, $\alpha$, $\beta$ must satisfy in order for the rectangle $a\times b$ to be partitioned into several rectangles $\alpha\times\beta$.

For example, can the rectangle $50\times 60$ be partitioned into rectangles of the following dimensions:

  1. $20\times 15$;
  2. $5\times 8$;
  3. $6{,}25\times 15$;
  4. $(2-\sqrt{2})\times (2+\sqrt{2})$.

A. T. Kolotov

Exploration

Consider small rectangles with integer sides. If a rectangle of size $a\times b$ is tiled by rectangles of size $\alpha\times \beta$, then both $a$ and $b$ must accommodate integer multiples of $\alpha$ or $\beta$ along their sides. For example, a $4\times 6$ rectangle can be partitioned into $2\times 3$ rectangles, because $4/2=2$ and $6/3=2$ are integers. However, swapping orientation may be necessary: $4\times 6$ can also be partitioned into $3\times 2$ rectangles with a different layout. Fractional dimensions introduce subtleties; for $6.25\times 15$ rectangles, the number of tiles must still multiply to integer counts along each dimension. For rectangles involving irrational lengths, such as $(2-\sqrt{2})\times (2+\sqrt{2})$, rational linear combinations of sides become critical. The core difficulty is distinguishing between divisibility constraints and orientation choices while accommodating all tiles without overlap or gaps.

Problem Understanding

The problem asks for necessary and sufficient conditions on $a$, $b$, $\alpha$, and $\beta$ so that a rectangle of size $a\times b$ can be exactly covered by a finite number of rectangles of size $\alpha\times \beta$, possibly rotated. This is a Type A problem: classification. The challenge is twofold: one must ensure the total area matches an integer multiple of the smaller rectangle area, and that the rectangle sides are compatible with multiples of $\alpha$ and $\beta$ in some orientation. Intuitively, the necessary conditions are that the total area $ab$ is divisible by $\alpha\beta$, and that either $\alpha$ divides $a$ and $\beta$ divides $b$, or $\alpha$ divides $b$ and $\beta$ divides $a$.

Proof Architecture

Lemma 1: If a rectangle $a\times b$ is partitioned into $\alpha\times \beta$ rectangles, then $ab$ is an integer multiple of $\alpha\beta$, because the sum of areas of the tiles equals the area of the large rectangle.

Lemma 2: Either $\alpha$ divides $a$ and $\beta$ divides $b$, or $\alpha$ divides $b$ and $\beta$ divides $a$, because each row and column must accommodate an integer number of tiles along its length. This is the hardest step, particularly ensuring no gaps or fractional tiling.

Lemma 3: These two conditions are sufficient, because one can align tiles along the dimension divisible by $\alpha$ and stack them along the other dimension divisible by $\beta$, covering the rectangle completely.

Hardest direction: proving sufficiency in the general (possibly non-integer) case. The lemma most likely to fail is Lemma 2 if irrational lengths are involved.

Solution

Consider a rectangle of size $a\times b$ and rectangles of size $\alpha\times \beta$. Let $N$ denote the number of tiles used. The total area condition requires

$$N \alpha \beta = ab.$$

Thus $ab / (\alpha \beta)$ must be a positive integer. This proves Lemma 1.

Next, examine how the tiles fit along the sides. Along the side of length $a$, either $\alpha$ or $\beta$ must divide $a$, otherwise there will be a leftover length that cannot be filled by the tiles. Similarly, along side $b$, the remaining dimension of the tiles must divide $b$. Therefore either $\alpha \mid a$ and $\beta \mid b$, or $\alpha \mid b$ and $\beta \mid a$, which proves Lemma 2.

Conversely, assume $ab/(\alpha\beta)$ is an integer and either $\alpha \mid a$, $\beta \mid b$, or $\alpha \mid b$, $\beta \mid a$. Then the number of tiles along each dimension is also an integer. For instance, if $\alpha \mid a$ and $\beta \mid b$, set $m = a/\alpha$ and $n = b/\beta$. Place $m$ tiles along the length $a$ and $n$ tiles along the length $b$, forming $mn = ab/(\alpha \beta)$ tiles in total. This completely covers the rectangle without gaps or overlaps. If the alternative orientation is chosen, the same argument applies with $\alpha$ and $\beta$ swapped. This proves Lemma 3.

For the examples: the rectangle $50\times 60$ can be partitioned as follows:

  1. $20\times 15$ tiles: $50/20 = 2.5$, $60/15 = 4$. One must rotate the tiles: $50/15 \approx 3.333$, $60/20 = 3$. Neither gives integer counts, so tiling is impossible.
  2. $5\times 8$ tiles: $50/5=10$, $60/8=7.5$, rotated: $50/8=6.25$, $60/5=12$. Both give non-integer numbers, impossible.
  3. $6.25\times 15$ tiles: $50/6.25=8$, $60/15=4$. Both integers, so tiling is possible.
  4. $(2-\sqrt{2})\times(2+\sqrt{2})$: $50/(2-\sqrt{2})$ and $60/(2+\sqrt{2})$ are not rational, so no tiling is possible.

Therefore the necessary and sufficient conditions are exactly that $ab/(\alpha\beta)$ is an integer, and either $\alpha$ divides $a$ and $\beta$ divides $b$, or $\alpha$ divides $b$ and $\beta$ divides $a$.

$$\boxed{\text{A rectangle } a\times b \text{ can be partitioned into rectangles } \alpha\times \beta \text{ if and only if } \frac{ab}{\alpha \beta} \in \mathbb{Z} \text{ and } (\alpha \mid a \text{ and } \beta \mid b) \text{ or } (\alpha \mid b \text{ and } \beta \mid a).}$$

Verification of Key Steps

The most delicate step is Lemma 2. For non-integer dimensions, one must carefully check divisibility rather than relying on visual alignment. For example, a $50\times 60$ rectangle and $5\times 8$ tiles seem close to fitting, but fractional quotients $50/8 = 6.25$ show tiling fails. For irrational tiles, $(2-\sqrt{2})\times (2+\sqrt{2})$, multiplication yields $4$, but neither $(50/(2-\sqrt{2}))$ nor $(60/(2+\sqrt{2}))$ is rational, confirming impossibility. The sufficiency step is verified by explicitly constructing the tiling grid and computing $m$ and $n$ to match the total area.

Alternative Approaches

One could attempt a linear-algebraic approach by encoding the tiling as integer solutions to $m \alpha + n \beta = a$ and $p \alpha + q \beta = b$, but this reduces ultimately to the divisibility condition derived above. Another approach is geometric induction, repeatedly subtracting strips of width $\alpha$ or $\beta$ and filling the remainder, but this also relies on the same integer quotient property. The area plus divisibility method is superior because it directly captures both necessary and sufficient conditions without iterative arguments.