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?


ANSWERS

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=2
area=6

n=4
area=40

n=6
area=108

n=8
area=240

n=10
area=435

n=12
area=735
(Maurizio Morandi)

n=14
area=1125

n=16
area=1647
(Maurizio Morandi)

n=18
area=2294
(Maurizio Morandi)

n=20
area=3102
(Maurizio Morandi)

k=2

n=3
area=15

n=4
area=35
(Maurizio Morandi)

n=5
area=63

n=6
area=99

n=7
area=154
(Maurizio Morandi)

n=8
area=224
(Claudio Baiocchi)

n=9
area=315

n=10
area=425

n=11
area=546

n=12
area=690
(Maurizio Morandi)

n=13
area=874
(Maurizio Morandi)

n=14
area=1081
(Maurizio Morandi)

n=15
area=1320
(Maurizio Morandi)

n=16
area=1590
(Maurizio Morandi)


n=17
area=1890
(Maurizio Morandi)

n=18
area=2220
(Maurizio Morandi)


k=3

n=8
area=221

n=10
area=425

n=12
area=693


k=4

n=12
area=899
(Andrew Bayly)

n=14
area=1295
(Maurizio Morandi)

n=15
area=1496
(Andrew Bayly)


n=16
area=2009

n=17
area=2220
(Maurizio Morandi)


n=18
area=2627

n=24
area=6125
(Andrew Bayly)


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