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 magnifcation 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, was the only one who contributed this month. He didn't find any new packings, but had some thoughts on how to do so: 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. I used Ilog-Cplex (http://www.ilog.com/products/cplex/) to solve the ILPs. I used COIN-or (www.coin-or.org) to interface to Cplex.
Bill Clagett gave the sequences for the 2x3, 2x5, and 3x5 rectangles, as well as correcting a few of my sequences.
Here are the best known values of the packing sequences of various shapes, in lexigraphical order:
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
3
4
6
8
10
12
15
18
20
23
26
29
32
36
39
43
1
3
5
6
8
10
13
15
18
21
24
26
1
3
5
6
8
10
13
15
1
3
5
6
8
11
13
15
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
36
39
43
47
50
54
58
62
66
71
75
1
3
5
7
9
1
3
5
7
9
11
13
15
18
21
24
27
1
3
5
7
9
11
13
15
18
21
1
3
5
7
9
11
13
16
18
1
3
5
7
9
12
14
16
19
1
3
5
7
9
12
14
1
3
5
7
9
12
14
1
3
5
7
9
12
15
18
21
24
27
30
33
36
1
3
5
8
10
12
14
16
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
1
4
6
8
10
12
14
17
19
22
1
4
6
8
10
12
15
1
4
6
9
12
15
18
21
24
27
30
33
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 8/6/04.
