# Covering a square with unit squares

 Importance: Medium ✭✭
 Author(s):
 Subject: Geometry
 Keywords:
 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).

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.