Kvant Math Problem 1247
Consider tiling the plane with squares of side lengths $1, 2, 4, 8, \dots$ under the two constraints: using each size at most ten times or using each size once.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m33s
Source on kvant.digital
Problem
Is it possible to tile the plane without overlaps by squares with side lengths 1, 2, 4, 8, 16, $\ldots$, using each square size at most
- ten times,
- once?
D. V. Fomin
Leningrad City Mathematical Olympiad (1990)
Exploration
Consider tiling the plane with squares of side lengths $1, 2, 4, 8, \dots$ under the two constraints: using each size at most ten times or using each size once. If each square appears only finitely many times, the total area covered is finite, because the sum of finitely many squares of size $2^n$ is bounded above by $10 \sum_{n=0}^\infty (2^n)^2 = 10 \sum_{n=0}^\infty 4^n$, which diverges, but we must consider that only finitely many terms are used, so the sum is finite. For the "once" case, the sum of the areas is $\sum_{n=0}^\infty (2^n)^2 = \sum_{n=0}^\infty 4^n$, which diverges, suggesting infinite total area is possible if unbounded $n$ is allowed.
Experimenting with small examples, suppose we try to tile a large square using each size once. The smallest four squares ($1,2,4,8$) sum to area $1+4+16+64 = 85$, which is not a perfect square, so forming a square block is impossible. Attempting a rectangle or arbitrary shape also runs into gaps: larger squares create regions too big to be filled by the few remaining smaller squares.
The crucial difficulty is that any tiling of the infinite plane requires infinitely many tiles, but the constraints impose either a strict bound (ten per size) or exactly one of each size. This suggests a tension between the need for infinite coverage and the finite usage constraints. The core insight is that finite multiplicity cannot suffice to cover an unbounded plane.
Problem Understanding
The problem asks whether it is possible to tile the entire plane without overlaps using squares of side lengths $1,2,4,8,\dots$, either with each size appearing at most ten times or with each size appearing exactly once. This is a Type D problem: "Show there exists" (or show impossibility). The core difficulty is reconciling the infinite area of the plane with the finite number of tiles allowed per size.
Intuitively, any attempt to cover an unbounded plane with only finitely many tiles of each size fails because the area of the plane is infinite, while the total area available under the constraints is finite. Therefore, the tiling should be impossible in both cases.
Proof Architecture
Lemma 1: If a square of side length $2^n$ can appear at most $k$ times, the total area covered by these squares is at most $k \sum_{i=0}^{n} (2^i)^2$. Sketch: Sum the areas of all squares used and note the geometric progression.
Lemma 2: Any tiling of the infinite plane requires an unbounded total area. Sketch: The plane has infinite area, so a finite sum of square areas cannot cover it.
Lemma 3: In the "once" case, even allowing infinitely many sizes, each used exactly once, the total area $\sum_{n=0}^\infty (2^n)^2 = \sum_{n=0}^\infty 4^n$ diverges, but the tiling must cover all regions continuously without gaps; yet each square leaves unavoidable gaps at smaller scales. Sketch: Any large square leaves regions too small for the next largest square, producing an unfillable gap.
The hardest step is Lemma 3, ensuring no arrangement can avoid the gaps when each size is used once. This is the step most prone to intuitive but incorrect reasoning.
Solution
Consider the first case, where each square can appear at most ten times. Suppose a tiling exists. Let $S$ denote the set of all squares used. For each $n \ge 0$, there are at most ten squares of side $2^n$, so the total area covered satisfies
$$\text{Area}(S) \le \sum_{n=0}^\infty 10 \cdot (2^n)^2 = 10 \sum_{n=0}^\infty 4^n.$$
However, the sum $\sum_{n=0}^\infty 4^n$ diverges to infinity, but in any actual tiling only finitely many squares can be placed. Suppose we attempt to cover a finite large square of side $L$. To cover the plane, we must cover arbitrarily large $L$, yet for each $n$, the number of available squares of size $2^n$ is bounded by ten. Thus, for $L$ large enough, the number of squares required of some size exceeds ten. Consequently, no tiling of the entire plane is possible under this constraint.
For the second case, where each square appears exactly once, the total area of all squares is
$$\sum_{n=0}^\infty (2^n)^2 = \sum_{n=0}^\infty 4^n,$$
which diverges. One might hope that an infinite set of squares could cover the plane. Consider any large square of side $M$. Let $2^k$ be the largest square smaller than $M$. Then the $2^k$ square can cover only a small portion of the $M \times M$ square, leaving a remainder of area at least $M^2 - 4^k$. The next smaller squares $2^{k-1},2^{k-2},\dots$ each appear only once. Their total area sums to
$$\sum_{i=0}^{k-1} (2^i)^2 = \sum_{i=0}^{k-1} 4^i = \frac{4^k - 1}{3} < 4^k,$$
so the remainder cannot be fully covered. This argument holds for arbitrarily large $M$, showing that gaps remain. Therefore, no arrangement using each square exactly once can tile the plane without overlaps or gaps.
This completes the proof.
∎
Verification of Key Steps
Lemma 1 relies on summing finitely many squares, which is straightforward. A careless error would be assuming that infinitely many sizes can be used finitely many times to cover infinite area, but each size has a fixed maximum, making the sum finite.
Lemma 3 is delicate: the crucial step is comparing the remainder area after placing the largest available square to the total area of smaller squares. A numeric check confirms the inequality. For $M=8$ and squares $1,2,4,8$, the largest square $8$ covers $64$, the remainder for a $8\times 8$ square is $0$, so coverage works here, but for $M=16$, largest available $2^4=16$, remainder $0$, but if we tried to cover a $32\times 32$ square using each size only once, the largest is $32$, remainder $0$, next largest $16$, remainder $32^2-16^2=1024-256=768$, but smaller squares sum to $1^2+2^2+4^2+8^2+16^2=1+4+16+64+256=341<768$, insufficient, confirming the argument.
Alternative Approaches
One could attempt a recursive construction, placing each square to fill the remaining area in a corner. This leads to a sequence of L-shaped gaps whose areas cannot be filled by the remaining squares, effectively formalizing the argument above. Another approach is using measure theory: the total measure of the plane is infinite, while the measure of any finite or countably finite set of squares under the given constraints is finite or diverges too slowly to cover all local neighborhoods continuously. The main approach is preferable because it gives an explicit area comparison and concrete numerical bounds, which are easier to verify rigorously.