Home ยป Covering a square with unit squares

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.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options