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+ . . . +n²) / 2n ≈ n²/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

n	f(n)	Author
1	1	Trivial
2	2	Trivial
3	4	Trivial
4	5	Erich Friedman
5	8	Erich Friedman
6	9	Erich Friedman
7	12	Erich Friedman
8	13	Erich Friedman
9	18	Erich Friedman
10	20	Joe DeVincentis
11	24	Joe DeVincentis
12	29	Joe DeVincentis
13	32	Joe DeVincentis
14	39	Joe DeVincentis
15	47	Joe DeVincentis
16	51	Joe DeVincentis
17	57	Joe DeVincentis
18	63	Maurizio Morandi
19	64	Joe DeVincentis
20	81	Erich Friedman
21	81	Erich Friedman
22	90	Maurizio Morandi
23	95	Maurizio Morandi
24	99	Maurizio Morandi
25	113	Maurizio Morandi
26	120	Maurizio Morandi
27	130	Joe DeVincentis
28	130	Joe DeVincentis
29	140	Maurizio Morandi
30	147	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.