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?


ANSWERS

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
11Trivial
22Trivial
34Trivial
45Erich Friedman
58Erich Friedman
69Erich Friedman
712Erich Friedman
813Erich Friedman
918Erich Friedman
1020Joe DeVincentis
1124Joe DeVincentis
1229Joe DeVincentis
1332Joe DeVincentis
1439Joe DeVincentis
1547Joe DeVincentis
1651Joe DeVincentis
1757Joe DeVincentis
1859Joe DeVincentis
1964Joe DeVincentis
2081Erich Friedman
2181Erich Friedman
2284Joe DeVincentis
2387Joe DeVincentis
2495Joe DeVincentis
25107Joe DeVincentis
26118Joe DeVincentis
27130Joe DeVincentis
28130Joe DeVincentis
29135Joe DeVincentis
30147Joe 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.