Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I meant to replace the original "any" with "some", which is done now. (Others may read the questioner's intent differently.) –  Steve Huntsman Jun 25 '10 at 16:46
    
Perhaps it should be stated for the record that this problem was originated by Alexander Soifer. –  Joseph O'Rourke Jun 27 '10 at 11:25
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Is there a proof that $\Pi(n) > n^2 + 1$? –  Ben Green Jun 25 '10 at 19:22
    
@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$. –  Joseph O'Rourke Jun 25 '10 at 20:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.