# Problem of the Month (October 1999)

This month we play with arrangements of squares of side 1, 2, 3, . . . n in the plane. We want all these squares to be non-overlapping, unrotated, and have vertices with integer corrdinates.

### Question #1:

If these squares are "stacked" on a flat surface, what is the longest flat surface that rests on some of these squares? Squares must be fully supported below. For example, f(5)=8: Let f(n) be the longest flat surface obtainable from the squares 1, 2, 3, . . . n. Can you find good bounds for f(n)? What can you prove about f(n)? Does f(n)/n → ∞ as n→ ∞?

### Question #2:

For which n does there exist an edge-connected arrangement of these n squares so that the area covered has some sort of symmetry?

### Question #3:

What is the smallest square that these n squares will fit into? This is an old question, dating back to Martin Gardner's column in Scientific American some 30 years ago. This sequence starts 1, 3, 5, 7, 9, 11, 13, 15, 18, 21, 24, 27, 30, 33, 36, 39, 43, 47, 51, 54, 58, 63, 67, 71, . . . and is A005842 of the Encyclopedia of Integer Sequences. Can anyone calculate the next term, involving squares of sides 1, 2, 3, . . . 25?

### Question #1:

Joseph DeVincentis found most of the best bounds on f(n) for n≤30. He also showed that f(99) ≥ 892. He made the following conjecture, which would imply that f(n)/n → ∞ as n→ ∞. This is based on a flat surface at height roughly 2n.

Conjecture: The optimal solutions for large n have two layers and f(n) ≈ (1+4+9+ . . . n2) / 2n ≈ n2/6.

Trevor Green showed f(9999) ≥ 165448. He also proved that f(n)/n → ∞ by showing

Theorem: Let G(n)= log(√3(2n - 6)/(1+√3)) / log(2+√3). Then f(n) ≥ n (G(n) - 2)/2.

Here are the best known lower bounds for f(n):

## Length of Longest Flat Surface

nf(n)PictureAuthor
11 Trivial
22 Trivial
34 Trivial
45 Erich Friedman
58 Erich Friedman
69 Erich Friedman
712 Erich Friedman
813 Erich Friedman
918 Erich Friedman
1020 Joe DeVincentis
1124 Joe DeVincentis
1229 Joe DeVincentis
1332 Joe DeVincentis
1439 Joe DeVincentis
1547 Joe DeVincentis
1651 Joe DeVincentis
1757 Joe DeVincentis
1859 Joe DeVincentis
1964 Joe DeVincentis
2081 Erich Friedman
2181 Erich Friedman
2284 Joe DeVincentis
2387 Joe DeVincentis
2495 Joe DeVincentis
25107 Joe DeVincentis
26118 Joe DeVincentis
27130 Joe DeVincentis
28130 Joe DeVincentis
29135 Joe DeVincentis
30147 Joe DeVincentis

### Question #2:

There were no responses, except to note that for n=1, 1 square is symmetric, and that there is a solution if the squares don't have to placed with lattice points as corners.

### Question #3:

There were no responses, though there was progress on this problem in 2004, 2009, and 2010. Here are the best known packings: s(1)=1 s(2)=3 s(3)=5 s(4)=7 s(5)=9 s(6)=11 s(7)=13 s(8)=15 s(9)=18 s(10)=21 s(11)=24 s(12)=27 s(13)=30 s(14)=33 s(15)=36 s(16)=39 s(17)=43 s(18)=47 s(19)=50 s(20)=54 s(21)=58 s(22)=62 s(23)=66 s(24)=71 s(25)=75 s(26)=80 s(27)=84 s(28)≤89 s(29)=93 s(30)=98 s(31)=103 s(32)=108 s(33)=113 s(34)=118 s(35)=123 s(36)=128 s(37)=133 s(38)≤139 s(39)=144 s(40)≤150 s(41)=155

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