Covering a square with unit squares

Importance: Medium ✭✭
Author(s):
Subject: Geometry
Keywords:
Recomm. for undergrads: no
Posted by: Martin Erickson
on: July 18th, 2011

\begin{conjecture} For any integer $n \geq 1$, it is impossible to cover a square of side greater than $n$ with $n^2+1$ unit squares. \end{conjecture}

Alexander Soifer in [S] raises the question of the smallest number $\Pi (n)$ of unit squares that can cover a square of side $n+\epsilon$. He shows the asymptotic upper bound $n^2+o(1)n+O(1)$, and the small values $\Pi (1)=3$, $5 \leq \Pi (2) \leq 7$, and $10 \leq \Pi (3) \leq 14$. He conjectures the asymptotic lower bound $n^2+O(1)$.

Bibliography

[S] Soifer, Alexander, "Covering a square of side n+epsilon with unit squares," J. of Combinatorial Theory, Series A 113 (2006):380-383.


* indicates original appearance(s) of problem.

A lower bound of the upper bound from polyomino-covering in [S]

(Using $e$ instead of $\epsilon$)
In [S], Soifer derives $\Pi(n) < (n-k)^2+2(k+1)[[\frac{k^2-1}{k^2+k-\sqrt{2k+2}} n]]$ .
As he mentioned, one can improve the covering construction. Holding the square of side length $n-k$ in the lower left corner, putting a square of side length $k$ in the upper right corner, covering the remaining uncovered area by 2 polyomino-coverings of rectangles of sides $n-k+e$ by $k+e$, removing useless unit squares in polyominos, we get a lower bound for the rhs of that inequality:
$(n-k)^2+k^2+2[[(k+1)(n-k)\frac{k^2-1}{k^2+k-\sqrt{2k+2}} ]]$
Denote by $U(n)$ the minimal value of this expression when varying $k$ from 2 to $n-2$.
Results of computer calculations:
$U(n) For growing $n$ (checked up to $2\times 10^9$), for the lowest optimal $k$, $\sqrt{2\times k^3}/n$ seems to converge to 1, and $(\ln(U(n)-n^2))/(\ln n)$ seems to converge to 3/4.

A flaw in the text of the conjecture

The square to cover is not a unit square.

The author has removed the flaw

... by a small revision.

A simple upper bound for Pi(n)

For any positive integer n: Pi(n) does not exceed sqr(n)+n+1 .
(Sketchy) proof, using e instead of epsilon:
To cover the square of side length n+e :
Place n by n unit squares as a square of side length n in the lower left corner. Move those unit squares on the upper-right side of the diagonal running from the upper left to the lower right corner by e up and right.
Now we have one set of unit squares in the lower left and one in the upper right corner. The remaining uncovered area is a Zigzag-path of width e consisting of n+1 horizontal lines of length 1+e and n vertical lines of length 1-e. If e is small enough, it is possible to cover that area with a regular array of n+1 non-overlapping unit squares such that each of them covers one horizontal line and parts of the one or two connected vertical lines.

Correction

Sorry; please replace the last part by this:
The remaining uncovered area is a Zigzag-path of width e consisting of n horizontal lines of length 1+e, n-1 vertical lines of length 1-e, and one vertical line of length 1. If e is small enough, it is possible to cover that area with a regular array of n+1 touching but not (2-dimensional) overlapping unit squares such that each of the first n of them covers one horizontal line and parts of the one or two connected vertical lines and the remaining square covers the remaining part of the (lower) vertical line.

Resulting upper bounds for n from 1 to 3

The given bound confirms the bounds for n=1 (3) and for n=2 (7) given by Soifer in [S] but improves the bound for n=3 (13 instead of 14).

Possibly further readings

The two articles listed below may be on the same topic but I can't get access even to the abstracts: [1] Title: A Sharper Upper Bound for Cover-Up Squared Authors: Dmytro Karabsh and Alexander Soifer Publication: Geombinatorics Quarterly Vol XVI, Issue 1, July 2006 Pages: 219 ff. (to 226 ?) [2] Title: Note on Covering Square with Equal Squares Authors: Dmytro Karabsh and Alexander Soifer Publication: Geombinatorics Quarterly Vol XVIII, Issue 1, July 2008 Pages: 13 ff. (to 17 ?)

Correction

The first author's name is Karabash.

A (currently) valid link to the referenced article

www.uccs.edu/~faculty/asoifer/docs/untitled.pdf

Correction

In the URL there has to be a tilde (ASCII code 126) between 'edu/' and 'faculty' instead of the visible blank.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.