Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
Are those solutions up to 32 all proved to be best, or just the best found so far? –  Noam D. Elkies Oct 3 '11 at 3:18
3  
In 2004, Shigeyoshi Kamakura found a packing for squares 1-23 in a 66x66 square, which went against a longstanding impossibility proof. Many of these proofs are programmatic, and at least one program is known to have failed. That said, I mostly trust the programs and handwork that has gone over smaller results. –  Ed Pegg Jr Oct 3 '11 at 12:20

1 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 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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.