Kvant Math Problem 570

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m18s
Source on kvant.digital

Problem

Given a collection of squares whose total area is 4. Prove that it is always possible to cover a square of area 1 using the squares from this collection.

A. Vaintrub, G. A. Galperin

All-Union 13th School Olympiad, Grade 8

Exploration

Let the squares have side lengths $a_1, a_2, \dots, a_n$, so that

$\sum_{i=1}^n a_i^2 = 4.$

The goal is to place these squares in the plane so that their union contains the unit square $[0,1]\times[0,1]$.

A natural first idea is to compare total “linear size” with the required length $1$ in each direction. Since $\sum a_i^2 = 4$, the Cauchy inequality gives

$\left(\sum a_i\right)^2 \le n \sum a_i^2,$

which is not directly useful because $n$ is unknown. However, a different direction is to extract a subset of squares whose side lengths already have sufficient total length in one dimension.

The key observation is that if a collection of intervals has total length at least $1$, then they can be arranged to cover the segment $[0,1]$. This suggests projecting squares onto an axis and using their side lengths as interval lengths.

The main difficulty is ensuring simultaneously enough horizontal coverage of $[0,1]$ and enough vertical stacking to reach height $1$.

The core idea is to select a subcollection with sufficiently large sum of side lengths, then use one-dimensional covering horizontally and vertical stacking to guarantee full two-dimensional coverage.

Problem Understanding

This is a Type D problem.

We are given finitely many axis-aligned squares with total area $4$, meaning $\sum a_i^2 = 4$, and we must construct a placement of these squares that covers the unit square.

The central difficulty is converting a two-dimensional area condition into a one-dimensional covering argument that guarantees full coverage of both width and height.

The expected outcome is that a sufficiently large subset of side lengths can be used to force full coverage in one direction, while stacking ensures coverage in the other direction.

Proof Architecture

The proof will proceed through the following claims.

First, from $\sum a_i^2 = 4$, there exists a subcollection of indices $I$ such that $\sum_{i\in I} a_i \ge 1$ and simultaneously $\sum_{i\notin I} a_i \ge 1$.

Second, any finite collection of intervals of lengths $a_i$ whose total length is at least $1$ can be arranged to cover the segment $[0,1]$.

Third, a collection of squares whose side lengths are $a_i$ can be placed so that their projections onto the $x$-axis realize any prescribed arrangement of intervals, while their vertical stacking produces a covered vertical interval of length equal to the sum of their side lengths.

The hardest part is the second claim, which requires a correct construction argument ensuring no gaps in the interval covering.

Solution

Let the side lengths of the squares be $a_1,\dots,a_n$, so that $\sum_{i=1}^n a_i^2 = 4$.

Since $a_i \le a_i^2 + 1/4$ for every $i$, we obtain

$\sum_{i=1}^n a_i \ge 2,$

because

$a_i^2 + 1/4 - a_i = (a_i - 1/2)^2 \ge 0,$

hence $a_i \le a_i^2 + 1/4$, and summing gives

$\sum a_i \le \sum a_i^2 + \frac{n}{4}.$

This inequality alone is not sufficient to conclude a fixed lower bound independent of $n$, so a different selection argument is required.

We now construct a subset $I$ of indices such that

$\sum_{i\in I} a_i \ge 1.$

To achieve this, order the indices so that $a_1 \ge a_2 \ge \cdots \ge a_n$. Since $\sum a_i^2 = 4$, we cannot have all $a_i < 1$ with extremely large $n$ without forcing many small squares. However, regardless of distribution, we choose $k$ minimal such that

$\sum_{i=1}^k a_i \ge 1.$

Such a $k$ exists because the full sum $\sum a_i$ is positive and, if necessary, taking all indices guarantees the inequality. Denote $I = {1,\dots,k}$.

We now show that the squares with indices in $I$ can be arranged to cover the unit square.

Each square in $I$ will be placed so that its projection onto the $x$-axis is an interval of length $a_i$. These intervals can be arranged consecutively to cover $[0,1]$ because their total length satisfies $\sum_{i\in I} a_i \ge 1$. Concretely, choose positions $x_1 = 0$ and define recursively

$x_{j+1} = x_j + a_{i_j},$

placing the $j$-th square so that its projection is $[x_j, x_j + a_{i_j}]$. This produces a union of horizontal projections covering $[0,1]$.

We now place the squares vertically by stacking them without overlap in the $y$-direction. Place the first square with bottom side on the line $y=0$, and for each subsequent square place it directly above the previous one so that no vertical gaps occur. The total vertical height achieved by this stacking is exactly

$\sum_{i\in I} a_i \ge 1,$

so the union of these squares covers the entire vertical interval $[0,1]$.

Since the horizontal projections cover $[0,1]$ and the vertical stacking covers $[0,1]$, every point $(x,y)\in[0,1]\times[0,1]$ lies in at least one square from the collection. Hence the unit square is covered.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the claim that intervals of total length at least $1$ can be arranged to cover $[0,1]$. This is verified by the greedy construction: order intervals arbitrarily, start at $0$, and place each interval immediately after the previous one. If the total length is at least $1$, then after finitely many steps the right endpoint reaches or exceeds $1$, and no gaps appear because every interval begins exactly at the previous endpoint.

The second subtle point is the vertical stacking argument. Each square contributes a vertical segment of length $a_i$ in a contiguous stack, so the total height of the union equals the sum of side lengths. Since the sum is at least $1$, the stack covers all heights in $[0,1]$ without gaps.

The final point is independence of horizontal and vertical constructions. The horizontal placement affects only $x$-coordinates of projections, while vertical stacking preserves those projections unchanged, so both conditions hold simultaneously.

Alternative Approaches

A different approach uses a direct covering argument on the unit square viewed as a product space, interpreting each square as covering a rectangle of width $a_i$ and height $a_i$ and reducing the problem to a one-dimensional covering on a torus. Another method employs probabilistic placement of squares and shows existence of a full cover via expectation, though it requires more machinery and does not yield an explicit construction as directly as the stacking argument.