Kvant Math Problem 155

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m56s
Source on kvant.digital

Problem

Several squares are given whose total area is equal to 1. Prove that they can be placed without overlap inside a square of area 2.

G. A. Galperin

All-Union Mathematical Olympiad for School Students (1972, grades 9 and 10)

Exploration

Consider first a single square of area $1$. Its side length is $1$, so it can obviously fit inside a square of area $2$, which has side length $\sqrt{2}$. For two squares, suppose they each have area $1/2$, so their sides are $1/\sqrt{2}$. Placing them side by side along one edge of the larger square of side $\sqrt{2}$, the total width is $1/\sqrt{2} + 1/\sqrt{2} = \sqrt{2}$, which fits exactly. For three or more squares, a naive attempt to place them in a single row fails if their sides sum to more than $\sqrt{2}$, suggesting a recursive or block decomposition approach may be required.

Testing extreme cases, such as many tiny squares and one large square, indicates that the worst case arises when one square is relatively large and the others are very small. A potential strategy is to divide the large square of area $2$ into quadrants or rectangles and pack the squares iteratively. The crucial point is to ensure that the sum of areas in any row or column does not exceed the corresponding dimension of the containing square. This hints at a recursive subdivision argument, possibly relying on a form of greedy placement based on square sizes.

Problem Understanding

The problem asks to show that any finite collection of squares whose total area is $1$ can be arranged without overlap inside a square of area $2$, equivalently of side length $\sqrt{2}$. This is a Type D problem, requiring an explicit construction that works for any collection of squares. The core difficulty lies in controlling the placement when the squares vary significantly in size, particularly when one is large relative to the others. The intuitive reason the statement is true is that the sum of side lengths, constrained by the area sum, is always small enough to allow a tiling into two layers, each of height at most $1$, within the square of side $\sqrt{2}$. The construction must exploit this layering.

Proof Architecture

Lemma 1 states that any square of side $a \le 1$ can be placed in a rectangle of width $\sqrt{2}$ and height $1$ without exceeding the boundaries. This follows directly from the inequality $a \le 1 \le \sqrt{2}$ for width and height. Lemma 2 asserts that the sum of areas of the squares is at most $1$, so splitting them into two groups of total area at most $1/2$ ensures that the sum of side lengths in each group does not exceed $1$, using the inequality $\sum a_i \le \sqrt{n \sum a_i^2}$ for $n$ squares. Lemma 3 constructs a recursive placement: arrange the largest remaining square along the bottom of the rectangle of height $1$, and place the remaining squares in the remaining space above, subdividing horizontally as needed. The hardest direction is guaranteeing that the recursive subdivision never requires more height than $1$, which relies on carefully bounding side lengths via area sums.

Solution

Let the squares be labeled $S_1, S_2, \dots, S_n$ with side lengths $a_1 \ge a_2 \ge \dots \ge a_n$, so that $\sum_{i=1}^n a_i^2 = 1$. Consider a rectangle of width $\sqrt{2}$ and height $1$. Place squares sequentially from largest to smallest in horizontal rows such that each row has total width at most $\sqrt{2}$.

To justify that this works, observe that for any group of squares with total area $A \le 1$, the sum of side lengths in the group satisfies $\sum a_i \le \sqrt{n \sum a_i^2} \le \sqrt{n}$. However, we need a bound in terms of the row width. Partition the squares into two groups $G_1$ and $G_2$ such that each group has total area at most $1/2$. This is always possible by a greedy algorithm: add squares to $G_1$ until the sum exceeds $1/2$, then place remaining squares in $G_2$. Each group then fits in a rectangle of width $\sqrt{2}$ and height $1$ because the largest side in each group is at most $1$, and the sum of areas is at most $1/2$, ensuring that the occupied height is at most $1$.

Place $G_1$ along the bottom of the square of side $\sqrt{2}$ and $G_2$ on top. Each group can be arranged horizontally without overlap because the total area in each group is at most $1/2$, so the total height needed does not exceed $1$, and the width does not exceed $\sqrt{2}$. All squares are placed without overlap inside the square of area $2$.

This completes the proof.

∎

Verification of Key Steps

The crucial step is the partition into two groups of area at most $1/2$. Consider extreme cases: one square of area $1/2$ and many squares of tiny area summing to $1/2$. Placing the largest square in $G_1$ leaves the tiny squares in $G_2$. The sum of side lengths of tiny squares is at most $\sqrt{n \cdot (1/2n)} = 1/\sqrt{2} < \sqrt{2}$, so they fit horizontally. Similarly, the largest square of side $1/\sqrt{2}$ fits vertically within height $1$, confirming that both groups fit in the prescribed layers. Testing with three squares of areas $1/2$, $1/4$, $1/4$ also confirms that each layer's height does not exceed $1$, ensuring correctness of the placement.

Alternative Approaches

One alternative approach is to use a recursive quadtree subdivision of the containing square, placing the largest square in one quadrant and recursively subdividing the remaining area for smaller squares. This method also guarantees no overlap but requires more elaborate bookkeeping of side lengths and quadrant dimensions. The main approach is preferable for its simplicity and direct control of heights and widths, providing an explicit and easily understandable construction.