Problem of the Month (September 2000)

In the 1970's, Martin Gardner asked for the size of the smallest square into which squares of sizes 1, 2, 3, . . . n could be packed. This sequence is now sequence A005842 of the Encyclopedia of Integer Sequences.

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?


ANSWERS

Let C(n) be the largest square that can be completely covered with untilted squares of side 1, 2, 3, . . . n, and let D(n) be the same where tilted squares are allowed.

Philippe Fondanaiche found the best known values for C(n) for n 22. Here is table of small values of C(n):

Largest Square Covered by Untilted Squares

n123456 789101112131415161718 19202122
C(n)123469 111316182124273134384145 49535761

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 23/9.

Trevor Green found this covering for D(4). Is this the best covering?

He also found this covering of D(5).

Here is table of small values of D(n):

Largest Square Covered by Tilted Squares

n12345
D(n)1234.33346.2432

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:

Largest Square Covered by n Equal Squares

n12345 6789101112131415
E(n)111.27222 22.20712.414233333.12133.27613.3672

Most of his optimal coverings look like this small example:

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 12/15/02.