Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I meant to replace the original "any" with "some", which is done now. (Others may read the questioner's intent differently.) $\endgroup$– Steve HuntsmanCommented Jun 25, 2010 at 16:46
-
1$\begingroup$ Perhaps it should be stated for the record that this problem was originated by Alexander Soifer. $\endgroup$– Joseph O'RourkeCommented Jun 27, 2010 at 11:25
-
$\begingroup$ Friedman and Paterson provide some results and figures at erich-friedman.github.io/papers/covering.pdf. The first of their proofs shows for $n=1$ that $n^2+1$ squares can cover a square of side length at most $n$, and they say the proofs for $n=2$ and $n=3$ are similar. So the first open subquestion of the OP here is how large a square you can cover with $17$ squares $\endgroup$– user44143Commented Jul 27, 2021 at 14:57
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
This reference is certainly pertinent, being the second Google hit for "covering a square with squares" (after your question). Just reading it now...
http://www.uccs.edu/~faculty/asoifer/docs/untitled.pdf
UPDATE: so far as I can tell from looking at this article, the author regards your question as an unsolved problem. There is a further article by him and Karabash, apparently in (his) journal Geombinatorics, vol. 18, which I cannot access online and which has not been reviewed on MathSciNet.
answered Jun 25, 2010 at 16:44
$\begingroup$
$\endgroup$
2
To supplement Ben Green's key reference (to "Covering a square of side n + ε with unit squares"), there is some follow-on work: Karabash & Soifer, "A sharp upper bound for cover-up squares," Geombinatorics, v16, 219-226, 2006; "Note on covering square with equal squares," Geombinatorics, v18, 13-17, 2008; Chung & Graham, "Note: Packing equal squares into a large square," Journal of Combinatorial Theory Series A, Volume 116, Issue 6 (August 2009), 1167-1175.
Addendum in response to Ben Green's remark: I do have the 2008 Geombinatorics paper (but not the 2006 one). They define $\Pi(n)$ as the number of unit squares that can cover a square of side length $n+\epsilon$. It appears that the status as of this 2008 paper was that $\Pi(n)=n^2+O(n^{2/3})$ has been established, and they conjecture that $\Pi(n)=n^2+ \Omega(n^{1/2})$.
answered Jun 25, 2010 at 17:03
-
$\begingroup$ Is there a proof that $\Pi(n) > n^2 + 1$? $\endgroup$ Commented Jun 25, 2010 at 19:22
-
$\begingroup$ @Ben G.: Not that I can see, but then I have not scoured all this literature. $\Pi(1)=3$, but already for $n=2$ and $n=3$, the known lower bound is $n^2+1$. $\endgroup$ Commented Jun 25, 2010 at 20:09
$\begingroup$
$\endgroup$
$\Pi(3)>10$ according to "A note on covering a square with equal squares", Januszweski, The American Mathematical Monthly Vol. 116, No. 2 (Feb., 2009), pp. 174-178.
