Problem of the Month (July 2004)

One of the most famous problems in recreational mathematics is to find s(n), the side of the smallest square that can contain non-overlapping squares of sides 1 through n. Clearly s(n) ≥ √(n(n+1)(2n+1)/6) from area considerations, and in most cases s(n) is the next largest integer. The values of s(n) are now known for n ≤ 25. The packing sequence 1, 3, 5, 7, 9, 11, 13, 15, 18, 21, 24, 27, 30, 33, 36, 39, 43, 47, 50, 54, 58, 62, 66, 71, 75, ... of s(n)'s is sequence A005842 of the Encyclopedia of Integer Sequences.

The smallest values of n for which s(n) is not known are n = 26, 28, 32, 33, 34, 38, and 40. It is barely possible that s(26)=79, s(28)=88, and s(40)=149. These were thought to be impossible until the s(37)=133 packing was found. Can you find one of these packings? It is known that s(32)≤108, s(33)≤113, s(34)≤118, and s(38)≤139, and because the amount of wasted space is so small, these are believed to be optimal, but they might be 1 smaller. Can you prove these?

This month's problem is to consider the same packing problem for other shapes: Given a shape P find its packing sequence, in which the n^th term is the smallest magnification of P that contains copies of size 1 through n of P. For example, the domino seems to have packing sequence 1, 3, 4, 6, 8, 10, 12, 15, 18, 20, 23, .... Can you verify or extend this sequence? What about the packing sequences of other small polyominoes? What about equilateral triangles? What about other triangles?

I'll give $10 to the first person who finds a shape with s(9) = 17.

ANSWERS

Matt Galati, an ex-student of mine, had some thoughts on how to find new packings: For each s, formulate the problem as a linear integer program, with decisions on where to place each square (sizes 1...n) on a board of size s. For a straightforward model, this leads to problems with O(n⁴) variables and O(n³) constraints. Then, use branch and bound with a subproblem tree. At the root, we solve the relaxed problem, fix a decision, then form 2 subproblems, fix another decision, solve 2 more subproblems, and so on. At some arbitrary point in the tree, if we can prove that each leaf contains a subproblem which is infeasible, we can show that the original problem is infeasible. To prove that a subproblem is infeasible means to show that there is a direction of improvement that would cause the dual to be unbounded.

Bill Clagett gave the sequences for the 2×3, 2×5, and 3×5 rectangles, as well as correcting a few of my sequences.

Maurizio Morandi extended several sequences.

Berend van der Zwaag sent solutions for the 3×4 rectangle. And he collected the $10 prize in 2011 for the packing below:

Here are the best known values of the packing sequences of various shapes, in lexigraphical order:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	3	4	6	8	10	12	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	4	6	8	10	12	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	21	24	26
1	3	5	6	8	11	13	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	23	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	26	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33
1	3	5	7	9	11	13	15	18	21	24	27	30
1	3	5	7	9	11	13	16	18	21	24	27
1	3	5	7	9	12	14	16	19	22	25
1	3	5	7	9	12	14	16		22
1	3	5	7	9	12	14	16	19	22
1	3	5	7	9	12	15	18	21	24	27	30	33	36
1	3	5	8	10	12	14	16	19	22
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24
1	4	6	8	10	12	14	17	19	22
1	4	6	8	10	12	15	18	21	24
1	4	6	9	12	15	18	21	24	27	30	33

Maurizio Morandi
Bill Clagett
Berend van der Zwaag

Here are the best known packings for squares:

And here are the best known packings for dominoes that are better:

Maurizio Morandi pointed out that the smallest multiples, especially for rectangles, are not necessarily integers. Here are the best multiples if fractions are allowed:

Shape 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 5/2 4 6 8 10 12 15 35/2 20 23 26 29 32 36 39 43 93/2 50 54 58 62 66 141/2 75
1 13/5 21/5 6 8 10 63/5 15 86/5 20 23 26 29 97/3 179/5 39 214/5 139/3 50 54 58 62 66 71 75
1 8/3 4 6 8 10 12 15 52/3 20 23 26 29 129/4 143/4 39 171/4 139/3 50 54 58 62 66 71 75
1 8/3 13/3 6 8 31/3 38/3 15 35/2 20 23 26 29 32 107/3 39 128/3 93/2 50 54 58 62 66 71 75

2×1 Rectangles

5×3 Rectangles

4×3 Rectangles

3×2 Rectangles

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

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	3	4	6	8	10	12	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	4	6	8	10	12	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	21	24	26
1	3	5	6	8	11	13	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	23	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	26	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33
1	3	5	7	9	11	13	15	18	21	24	27	30
1	3	5	7	9	11	13	16	18	21	24	27
1	3	5	7	9	12	14	16	19	22	25
1	3	5	7	9	12	14	16		22
1	3	5	7	9	12	14	16	19	22
1	3	5	7	9	12	15	18	21	24	27	30	33	36
1	3	5	8	10	12	14	16	19	22
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24
1	4	6	8	10	12	14	17	19	22
1	4	6	8	10	12	15	18	21	24
1	4	6	9	12	15	18	21	24	27	30	33

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	5/2	4	6	8	10	12	15	35/2	20	23	26	29	32	36	39	43	93/2	50	54	58	62	66	141/2	75
1	13/5	21/5	6	8	10	63/5	15	86/5	20	23	26	29	97/3	179/5	39	214/5	139/3	50	54	58	62	66	71	75
1	8/3	4	6	8	10	12	15	52/3	20	23	26	29	129/4	143/4	39	171/4	139/3	50	54	58	62	66	71	75
1	8/3	13/3	6	8	31/3	38/3	15	35/2	20	23	26	29	32	107/3	39	128/3	93/2	50	54	58	62	66	71	75

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	3	4	6	8	10	12	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	4	6	8	10	12	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	21	24	26
1	3	5	6	8	11	13	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	23	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	26	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33
1	3	5	7	9	11	13	15	18	21	24	27	30
1	3	5	7	9	11	13	16	18	21	24	27
1	3	5	7	9	12	14	16	19	22	25
1	3	5	7	9	12	14	16		22
1	3	5	7	9	12	14	16	19	22
1	3	5	7	9	12	15	18	21	24	27	30	33	36
1	3	5	8	10	12	14	16	19	22
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24
1	4	6	8	10	12	14	17	19	22
1	4	6	8	10	12	15	18	21	24
1	4	6	9	12	15	18	21	24	27	30	33

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	3	4	6	8	10	12	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	4	6	8	10	12	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	20	23	26	29	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	6	8	10	13	15	18	21	24	26
1	3	5	6	8	11	13	15	18	20	23	26	29	32	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	23	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	26	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33	36	39	43	47	50	54	58	62	66	71	75
1	3	5	7	9	11	13	15	18	21	24	27	30	33
1	3	5	7	9	11	13	15	18	21	24	27	30
1	3	5	7	9	11	13	16	18	21	24	27
1	3	5	7	9	12	14	16	19	22	25
1	3	5	7	9	12	14	16		22
1	3	5	7	9	12	14	16	19	22
1	3	5	7	9	12	15	18	21	24	27	30	33	36
1	3	5	8	10	12	14	16	19	22
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24	27
1	3	6	8	10	12	15	18	21	24
1	4	6	8	10	12	14	17	19	22
1	4	6	8	10	12	15	18	21	24
1	4	6	9	12	15	18	21	24	27	30	33