Question

At Tightly Packed Squares, best solutions for square packings for 1 to 32 squares are given.

What would the best packing for 33 squares be? Here are various rectangles that might work, preceeded by the excess squares.

0 -- $67\times187$, 1 -- $70\times179$, 4 -- $83\times151$, 6 -- $109\times115$, 11 -- $110\times114$, 14 -- $111\times113$, 15 -- $112\times112$, 16 -- $65\times193$, 17 -- $102\times123$, 20 -- $89\times141$, 22 -- $77\times163$, 26 -- $93\times135$, 27 -- $86\times146$, 29 -- $91\times138$, 31 -- $80\times157$, 32 -- $79\times159$, 37 -- $103\times122$, 38 -- $71\times177$, 44 -- $99\times127$, 47 -- $96\times131$, 51 -- $85\times148$, 55 -- $104\times121$.

For 34 squares, possible best rectangles are

0 -- $115\times119$, 3 -- $116\times118$, 4 -- $117\times117$, 5 -- $74\times185$, 7 -- $84\times163$, 9 -- $82\times167$, 10 -- $83\times165$, 11 -- $107\times128$, 14 -- $103\times133$, 15 -- $100\times137$, 18 -- $71\times193$, 21 -- $89\times154$, 23 -- $92\times149$, 31 -- $108\times127$, 35 -- $98\times140$, 39 -- $94\times146$, 40 -- $75\times183$, 43 -- $104\times132$, 46 -- $69\times199$, 49 -- $109\times126$, 51 -- $101\times136$, 56 -- $91\times151$, 61 -- $87\times158$, 65 -- $110\times125$, 67 -- $72\times191$

Ironically, human minds seem to be very good at these problems. Most of the higher order square-packing results for 50+ differently sized squares were solved by hand. Can anyone bring a new methodology for solving this problem?

Answer 1

I don't have an answer.

I do have a suggestion, as well as a weak link to work done by Gerry Myerson et. al, and to some work of mine. Check out the comments to the question http://mathoverflow.net/questions/61744/has-anyone-seen-this-version-of-ring-toss-combinatorial-object-before for the references.

The suggestion is to use short arithmetic progressions to build subcomponents. For example, (squares of sides) 23,22,21 and 20 can be packed around a square of side 1 to give a tightly packed configuration, and that can be extended by placing a square of side 2 adjacent to 23 and 20, and then adding squares of sides 18 and 25, leaving a 9x18 hole to be filled if I did the picture right. Perhaps two or three of these subconfigurations can be chained together to acheive a very tight packing, and then computer search or other heuristics can be used to pack tightly the remaining squares. This suggestion may already be present in the literature on the Perkins quilt.

The weak link is that I am studying Jacobsthal's function, one approximation to which is covering an integer interval by arithmetic progressions (with minimal overlap) where the common differences are primes. Here you will need (as large as possible of) an exact cover of [1,...,33] by shorter progressions (plus their common difference) where the common differences are not necessarily prime. There may be other ways to translate your two-dimensional packing problem into a one-dimensional version; I thought you might like this perspective.

Gerhard "Ask Me About System Design" Paseman, 2011.10.02