The corresponding covering problem has not been considered. What is the largest square that can be completely covered with untilted squares of side 1, 2, 3, . . . n ? How much do the answers change if the squares are allowed to be at any angle? In particular, what is the largest square that can be completely covered with squares of sides 1, 2, 3, and 4?
Philippe Fondanaiche found the best known values for C(n) for n≤22. Here is table of small values of C(n):
Trevor Green and I managed to prove that C(n) is always an integer. The proof: For any covering by untilted squares, there is a covering at least as good involving squares only placed at lattice points. To see this, shift squares not at lattice points upward and right until they are.
Trevor Green also found simple proofs for C(4)=4 and C(5)=6. Essentially, they show that any placement of the squares results in overlaps which are too large. He suggests that a computer could be used to prove optimality for higher values of C(n). He expects the answers to be very close to n(n+1)(2n+1)/6. Philippe Fondanaiche suspects that all such optimal packings use no more than 40 or 50 square units of overlap.
Recently, Sasha Ravsky sent me a proof that C(n)/n3/2 ≥ 2√3/9.
Trevor Green found this covering for D(4). Is this the best covering?
Trevor Green was also interested in using n squares of equal size to cover the largest square possible. Call the side of the largest square E(n). Here are his results:
Most of his optimal coverings look like this small example: