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 nth 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(n4) variables and O(n3) 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 2x3, 2x5, and 3x5 rectangles, as well as correcting a few of my sequences.

Maurizio Morandi extended the sequence for the 2x5 rectangle.

Berend van der Zwaag sent solutions for the 3x4 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:

Shape12345678910111213141516171819202122232425
13468101215182023262932363943
1346810121518202326
1356810131518212426
13568101315
13568111315
135791113151821242730333639434750545862667175
135791113151821242730333639434750545862667175
135791113151821242730333639434750545862667175
135791113151821242730333639434750545862667175
1357911131518
1357911131518212427
135791113151821
1357911131618
1357912141619
135791214
135791214
13579121518212427303336
135810121416
136810121518212427
136810121518212427
136810121518
1468101214171922
1468101215
14691215182124273033

Here are the best known packings for squares:








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


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