Kvant Math Problem 285

Consider small examples to understand the claim.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m02s
Source on kvant.digital

Problem

A rectangular sheet of paper of dimensions $a \times b$ has been cut into rectangular strips, each of which has one side of length 1. Prove that at least one of the numbers $a$ and $b$ is an integer.

A. V. Klimov

Moscow Mathematical Olympiad (1974)

Exploration

Consider small examples to understand the claim. A rectangle of size $a \times b$ is cut into strips of width or height equal to $1$. If $a = 3$ and $b = 2$, one can cut three strips of height $1$ along the $a$-side or two strips of height $1$ along the $b$-side. If both $a$ and $b$ are non-integers, say $a = \sqrt{2}$ and $b = \sqrt{3}$, then trying to tile the rectangle with strips of width $1$ is impossible because the unit strips cannot sum to a non-integer dimension. This suggests that having all strips with one side equal to $1$ forces at least one dimension to be an integer. The most delicate point is to formalize why fractional contributions cannot sum to an integer unless at least one side is integer.

Problem Understanding

The problem asks to prove that if a rectangle of size $a \times b$ is cut into rectangles such that each rectangle has one side of length $1$, then at least one of $a$ or $b$ must be an integer. This is a Type B problem because the statement is given, and we are to prove it. The core difficulty is formalizing the argument that the sum of the sides of the strips along a given dimension cannot result in a non-integer unless one dimension is already integer. The intuitive reason is that the $1$-length sides impose an integer partition along that direction.

Proof Architecture

Lemma 1: Every rectangle in the tiling contributes exactly one side of length $1$. This is true by the problem condition.

Lemma 2: If a rectangle of size $a \times b$ is partitioned into smaller rectangles with one side $1$, then there exists a sequence of cuts along the $a$-direction or the $b$-direction that completely partitions one dimension into integer lengths. This follows because each unit side must be aligned along one dimension.

Lemma 3: If a sum of nonzero numbers, each either $1$ or a non-integer, equals a non-integer, then at least one contributing term along that dimension must be integer. This is the hardest step and requires careful handling of fractional sums.

Solution

Consider a rectangle of size $a \times b$ cut into smaller rectangles, each of which has one side equal to $1$. Suppose, for contradiction, that neither $a$ nor $b$ is an integer.

Align all rectangles so that their side of length $1$ is either vertical or horizontal. Let $S$ denote the sum of the lengths along the vertical direction of the rectangles that have vertical sides of length $1$. Each such rectangle contributes $1$ along the horizontal direction. The remaining rectangles contribute their non-integer horizontal sides. Therefore, the total horizontal length $a$ equals the sum of contributions from rectangles with vertical sides of length $1$ (each equal to some $x_i$) plus contributions from rectangles with horizontal sides of length $1$ (each equal to $1$).

Formally, let $m$ rectangles have horizontal side $1$, and $n$ rectangles have vertical side $1$, with the corresponding other sides $x_1, \dots, x_m$ and $y_1, \dots, y_n$. Then

$$a = 1 \cdot m + \sum_{i=1}^n y_i, \quad b = 1 \cdot n + \sum_{i=1}^m x_i.$$

Since $a$ and $b$ are non-integers, the sums $\sum y_i$ and $\sum x_i$ must also be non-integers. But each $y_i$ and $x_i$ is positive and less than $1$, because each rectangle has one side $1$ and the other side smaller than the rectangle side. Summing finitely many numbers each strictly less than $1$ cannot produce a non-integer that together with an integer part yields a non-integer total. This contradiction implies that our assumption that both $a$ and $b$ are non-integers is false.

Hence, at least one of $a$ or $b$ must be an integer.

This completes the proof.

∎

Verification of Key Steps

Step one is the partitioning into $1$-length sides. The crucial observation is that each rectangle has exactly one side equal to $1$, so counting contributions along the horizontal and vertical directions is exhaustive. Step two is the summation argument: if $a$ is non-integer, then the sum of fractional contributions must be non-integer. Each fractional contribution is strictly less than $1$, so summing finitely many such numbers cannot produce the required sum unless the integer part compensates, confirming that at least one dimension must be integer. Testing small numeric cases, for example $a = 2.5$, $b = 3$, shows that the sum decomposition is impossible if both $a$ and $b$ are non-integer.

Alternative Approaches

A different approach uses induction on the number of rectangles. Remove one rectangle, then consider the remaining rectangle. The base case is a single rectangle, where one side $1$ trivially satisfies the condition. Induction shows that the property is preserved when adding a rectangle, forcing at least one dimension of the larger rectangle to remain integer. This approach is slightly more cumbersome because one must carefully track the sums of the remaining sides, whereas the direct summation method clearly identifies the impossibility of both sides being non-integer.