Covering a square with unit squares

Importance: Medium ✭✭

Author(s):

Subject:

Keywords:

Recomm. for undergrads: no

Posted	by:	Martin Erickson
	on:	July 18th, 2011

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.

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.

add new comment

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

On August 1st, 2011 Carolus says:

(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)<n^2+n+1$ iff $n=46, n=48,$ or $n \ge 50$ .
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

On August 1st, 2011 Anonymous says:

The square to cover is not a unit square.

The author has removed the flaw

On August 1st, 2011 Anonymous says:

... by a small revision.

A simple upper bound for Pi(n)

On July 29th, 2011 Carolus says:

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

On July 29th, 2011 Carolus says:

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

On July 29th, 2011 Carolus says:

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

On July 27th, 2011 Anonymous says:

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 ?)

Open Problem Garden

Covering a square with unit squares

Bibliography

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

A flaw in the text of the conjecture

The author has removed the flaw

A simple upper bound for Pi(n)

Correction

Resulting upper bounds for n from 1 to 3

Possibly further readings

Correction

A (currently) valid link to the referenced article

Correction

Comment viewing options

Navigate

Recent Activity