Problem of the Month (December 2007)

The problem of packing squares of sides 1, 2, 3, . . . n into the smallest rectangle possible is well-known. This month we wish to consider only packings of such squares where each square touches exactly k other squares, and the squares are in one connected group. We assume each square has vertices at lattice points.

When k = 2, this becomes the problem of packing of squares in a loop. What are the smallest rectangles you can find for various n? When k ≥ 3, we need the squares to form the vertices of a k-regular graph. Can you find small packings for k=3? Can you find any packings for k=4 or k=5? Can you see why packings are impossible for k ≥ 6?

Andrew Bayly and Joe DeVincentis pointed out that since no more than 4 squares could touch the unit square, no solutions for k ≥ 5 were possible. Andrew Bayly found the first solution for k=4, and the smallest solution for n=4.

Claudio Baiocchi noted that kn must be even to form a n-vertex k-regular graph.

Claudio Baiocchi also noted that when k=3, an n=4 solution and an n=6 solution exist when corner contacts are allowed.

If we relax the condition that the squares form a connected group, there are solutions for k=0 and k=1 as well. The k=0 solutions are related to the solutions with no connectivity constraints.

Below are the smallest known packings:

k=1 n=2area=6 n=4area=40 n=6area=108 n=8area=240 n=10area=435 n=12area=735(Maurizio Morandi) n=14area=1125 n=16area=1647(Maurizio Morandi) n=18area=2294(Maurizio Morandi) n=20area=3102(Maurizio Morandi)

k=2 n=3area=15 n=4area=35(Maurizio Morandi) n=5area=63 n=6area=99 n=7area=154(Maurizio Morandi) n=8area=224(Claudio Baiocchi) n=9area=315 n=10area=425 n=11area=546 n=12area=690(Maurizio Morandi) n=13area=874(Maurizio Morandi) n=14area=1081(Maurizio Morandi) n=15area=1320(Maurizio Morandi) n=16area=1581(Maurizio Morandi) n=17area=1890(Maurizio Morandi) n=18area=2220(Maurizio Morandi)

k=3 n=8area=221 n=10area=425 n=12area=693

k=4 n=12area=899(Andrew Bayly) n=14area=1254(Maurizio Morandi) n=15area=1452(Maurizio Morandi) n=16area=1768(Maurizio Morandi) n=17area=1972(Maurizio Morandi) n=18area=2457(Maurizio Morandi) n=20area=3116(Maurizio Morandi) n=24area=5428(Maurizio Morandi)

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