Covering a square with unit squares

Covering a square with unit squares

Definitions and mathematical statement

For $s>0$, let $Q_s=[0,s]^2\subset\mathbb R^2$. A unit square is any set congruent to $[0,1]^2$ under a Euclidean isometry; its sides need not be parallel to those of $Q_s$ or to those of the other squares. A family $U_1,\ldots,U_m$ covers $Q_s$ when $Q_s\subseteq\bigcup_{i=1}^m U_i$. Squares may overlap each other and may extend beyond the boundary of $Q_s$.

The conjecture says that for every integer $n\ge1$ and every real $s>n$, no family of $n^2+1$ unit squares covers $Q_s$. Equivalently, \[ Q_s\subseteq\bigcup_{i=1}^{n^2+1}U_i \quad\Longrightarrow\quad s\le n. \] Allowing fewer squares gives the same nonexistence assertion, since any smaller cover can be augmented by unused or repeated squares. All boundaries are included in the covering condition; covering almost every point by area alone is not its definition.

The integer threshold is sharp at side length $n$ in the elementary sense that an $n$ by $n$ array of unit squares covers $Q_n$ using only $n^2$ squares. The question asks whether one additional square can enable any positive increase in side length, however small. A pure area estimate only yields $s^2\le n^2+1$, leaving a nonempty interval of possible side lengths above $n$; controlling this interval requires the geometry of covering rather than the sum of areas alone.

Short English statement

Can adding just one square to an $n$ by $n$ collection of unit squares ever cover a square with side strictly larger than $n$?

Research attempt

Scope and literature check.

The original question [S2], checked 1 October 2026, allows rotations and outward protrusion. This attempt proves the stronger counting obstruction when all covering squares are axis-parallel, and quantifies precisely which part of that obstruction survives when rotations are allowed. The geometric certificate below does not rely on area or on assuming a tiling.

Separated-point certificate.

Fix $s>n$ and put $\delta=s/n>1$. The set \[ T=\{(i\delta,j\delta):0\le i,j\le n\}\subseteq[0,s]^2 \] has $(n+1)^2$ points. An axis-parallel unit square cannot contain two distinct points of $T$: some coordinate of any such pair differs by at least $\delta>1$, whereas each coordinate interval of the square has length one. A cover must cover every point of $T$, including the boundary points. It therefore needs at least $(n+1)^2>n^2+1$ squares. This proof allows arbitrary overlaps, arbitrary translations, and arbitrary extension beyond the target.

A quantitative rotation obstruction.

For a unit square rotated through angle $\theta$, reduce by its symmetries to $0\le\theta\le\pi/4$. Both coordinate projections have length $w(\theta)=\cos\theta+\sin\theta$. This follows by projecting its two edge vectors: the width of their Minkowski sum is the sum of the projected widths. If every covering square satisfies $w(\theta)<\delta$, the same point-count argument still applies, using the squares' bounding boxes. Thus any cover with only $n^2+1$ squares must have at least one square with \[ \cos\theta+\sin\theta\ge s/n. \] For $1<s/n\le\sqrt2$ this forces \[ \theta\ge\arcsin\!\left(\frac{s}{n\sqrt2}\right)-\frac\pi4. \] If $s/n>\sqrt2$, the projection test excludes the cover with no restriction on angles. At equality the strict separation argument ceases to apply; it is not legitimate to replace its strict inequalities by weak ones. For small excess $s=n+\varepsilon$, the forced angle tends to zero with $\varepsilon$, so this result provides no fixed positive angle barrier.

Failure of a rotation-invariant version.

One might try to say that a unit square covers at most one of these grid points regardless of orientation. That is false. A square rotated by $\pi/4$ is a diamond whose horizontal diagonal has length $\sqrt2$. It contains two points at horizontal separation $1+\varepsilon$ whenever $0<\varepsilon\le\sqrt2-1$, after translation to their midpoint. Thus the very local property needed by the discrete certificate fails in the difficult interval near $s=n$. Replacing coordinate separation by Euclidean separation greater than $\sqrt2$ restores the property but loses the required $(n+1)^2$ points near this threshold.

Verification and first remaining gap.

The obstruction counts exact points, not sampled uncovered area, so it is unaffected by measure-zero cracks or boundary conventions. The projection formula is checked at $\theta=0$ and $\pi/4$. The construction at $s=n$ by $n^2$ squares is consistent: then grid separation is one and a single square can contain several grid vertices. A general proof would need a certificate that accounts simultaneously for the orientations of different squares, not just a common bound on their coordinate widths. This attempt gives no such certificate, nor a rotated cover contradicting the conjecture.

Final status.

UNRESOLVED. The axis-parallel case and the stated bounded-projection extension are proved; the unrestricted rotation case remains outside the argument. No historical novelty is claimed. Completion estimate: 5%.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3086 (OPG-37327), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Covering a square with unit squares. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/covering_a_square_with_unit_squares.