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=741

n=14
area=1127
n=16
area=1664

k=2

n=3
area=15
n=4
area=40
n=5
area=63
n=6
area=99
n=7
area=156
n=8
area=224
(Claudio Baiocchi)
n=9
area=315

n=10
area=425
n=11
area=546
n=12
area=704

n=13
area=896
n=14
area=1092

n=15
area=1325
n=16
area=1612


n=17
area=1904
n=18
area=2236

Claudio Baiocchi found these packings for k=2, which are superior if connectedness is relaxed. He conjectures there are no such packings for k≥3.


(Claudio Baiocchi)
(Claudio Baiocchi)

(Claudio Baiocchi)

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=1344
n=15
area=1496
(Andrew Bayly)


n=16
area=2009
n=17
area=2405


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 12/23/07.