Open Problem Garden - Covering a square with unit squares - Comments

Correction (re: Covering a square with unit squares)

Anonymous — Mon, 01 Aug 2011 21:02:02 +0200

The first author's name is Karabash.

A lower bound of the upper bound from polyomino-covering in [S] (re: Covering a square with unit squares)

Carolus — Mon, 01 Aug 2011 20:40:15 +0200

(Using instead of )
In [S], Soifer derives .
As he mentioned, one can improve the covering construction. Holding the square of side length in the lower left corner, putting a square of side length in the upper right corner, covering the remaining uncovered area by 2 polyomino-coverings of rectangles of sides by , removing useless unit squares in polyominos, we get a lower bound for the rhs of that inequality:

Denote by the minimal value of this expression when varying from 2 to .
Results of computer calculations:
iff or .
For growing (checked up to ), for the lowest optimal , seems to converge to 1, and seems to converge to 3/4.

The author has removed the flaw (re: Covering a square with unit squares)

Anonymous — Mon, 01 Aug 2011 14:35:13 +0200

... by a small revision.

A flaw in the text of the conjecture (re: Covering a square with unit squares)

Anonymous — Mon, 01 Aug 2011 02:08:53 +0200

The square to cover is not a unit square.

Correction (re: Covering a square with unit squares)

Carolus — Fri, 29 Jul 2011 22:45:30 +0200

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 (re: Covering a square with unit squares)

Carolus — Fri, 29 Jul 2011 20:38:42 +0200

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

A simple upper bound for Pi(n) (re: Covering a square with unit squares)

Carolus — Fri, 29 Jul 2011 20:19:58 +0200

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 (re: Covering a square with unit squares)

Anonymous — Wed, 27 Jul 2011 19:58:38 +0200

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

Possibly further readings (re: Covering a square with unit squares)

Anonymous — Wed, 27 Jul 2011 19:38:35 +0200

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

A (currently) valid link to the referenced article (re: Covering a square with unit squares)

Anonymous — Wed, 27 Jul 2011 18:55:13 +0200

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

Covering a square with unit squares

Martin Erickson — Mon, 18 Jul 2011 16:30:01 +0200

Author(s):

Subject: Geometry

Conjecture For any integer , it is impossible to cover a square of side greater than with unit squares.