Take the 2-minute tour ×

The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.

It is easy to show that



Is this problem still open?


share|improve this question
Please read “What about open problems?” in FAQ at mathoverflow.net/faq#openproblems –  Tsuyoshi Ito Aug 1 '10 at 20:05
Thank you. I will rephrase the question to make it more compatible to the FAQ and will flag it so moderators can check if this is now an appropriate MO question. –  Kaveh Aug 1 '10 at 20:52
Thanks for rephrasing the question. –  Tsuyoshi Ito Aug 1 '10 at 20:54
This is not an answer, but the not-widely-read journal Geombinatorics has a lot of problems related to this. It's reviewed only by Alexander Soifer, as far as I can tell, but a lot of very interesting math flows through it, including tiling problems. –  Eric Tressler Aug 1 '10 at 23:00
I certainly don't know how to do this question, but I could really envisage spending a lot of time trying if I found an applet where you could drag and drop rectangles into a square, and the applet would do precise arithmetic and allow you to zoom in to various regions, and made intelligent choices about how to label lengths and so on. You kind of feel that it might be one of those problems that you can get a feel for an algorithm if you're allowed to play with examples. –  Kevin Buzzard Aug 3 '10 at 14:37

3 Answers 3

up vote 23 down vote accepted

This problem actually goes back to Leo Moser.


Edit 1. A web search via Google Scholar gave a reference to this article by V. Bálint, which claims that the rectangles can be packed into a square of size $(501/500)^2$.

Edit 2. The state of art of this and related packing problems due to Leo Moser is discussed in Chapter 3 of "Research Problems in Discrete Geometry" by P.Brass, W. O. J. Moser and J. Pach. The problem was still unsettled as of 2005.

share|improve this answer
I think any discussion of this problem should explicitly mention the paper by Marc M. Paulhus, "An algorithm for packing squares," J. Combin. Theory Ser. A 82 (1998), 147-157. In a certain precise sense, Paulhus's results are millions of times better than any previous results, including Balint's. Paulhus's method also adapts readily to a number of other related packing problems. –  Timothy Chow Sep 10 '10 at 16:22




Here's an image of the situation after 10000 rectangles: Maximized_contact. There is a different pattern, arguably just as good, if the first position with 2 edge-to-edge contacts is selected: Two_contacts (after 1000 rectangles). This is quicker.



I have recently started checking the results using arbitrary-length rational numbers (using the IMath package). This is slower, of course. The size of the denominator could be excessive (see A003418), but only 138 base-10 digits were required up to 4800 rectangles. This took about 5 hours on a desktop. The code isn't designed for efficiency, and gets progressively slower in a variety of ways.


Here are images: Wide open space at 10000 and Impending crunch at 15000, Crunch at 17000 (zoomed in) and Crunch averted so far, at 30000



share|improve this answer
Unfortunately your links don't work at my computer. Can you put images/programs on some free hosting? –  Fiktor Oct 15 '10 at 13:34
Alas, images are now gone. –  I. J. Kennedy Feb 23 '12 at 17:35
Please reupload the images. –  pts Oct 21 '13 at 10:31
Yes, I'll reup the images when I can find them. In the meantime, the Paulhus paper referenced in a different comment is miles, miles better. –  Ed Wynn Nov 25 '13 at 19:57


A quick search revealed Bálint's paper A Packing Problem and Geometrical Series. In this article it is only stated that with some patience one can pack the first 499 rectangles into the unit square. However, the main difficulty of the problem is to pack the larger rectangles and so it would have been nice to see a demonstration.

Bálint addresses the question in Two Packing Problems but I do not have easy access to this and so now I'm concerned that a similar claim, without a demonstration, may have been made in this paper too.



share|improve this answer
V. Bálint didn't give a proof of his claim in "Two packing problems" either. I can send you this paper if you're interested. My email is name.surname@gmail.com (just substitute my real name and surname). –  Andrey Rekalo Aug 3 '10 at 13:32
Yes Andrey, I'm interested, so please send me a copy of the paper. My email is namesurname@ntlworld.com (as with your email, just substitute my real name and surname, and note the lack of a dot separating them). –  Derek Jennings Aug 3 '10 at 19:20
If you can get arbitrarily close to 1, can't you achieve 1? Consider a sequence of packings which converges to size 1. Next, find a subsequence in which the packing of the first $k$ rectangles converges to some fixed configuration (such a subsequence must exist by compatctness). Now, in this subsequence, find a subsubsequence in which the packing of the first $2k$ rectangles converges ... and so on. Now, this set of subsequences gives you a set of packings for any number $n$ of rectangles, and the earlier rectangles don't change position after they've been placed. –  Peter Shor Aug 9 '10 at 16:26
@PeterShor, is this a rigorous argument? You say that "the earlier rectangles don't change position after they've been placed", but, if I understand the argument correctly, they just don't change position *much*—but a small change can dramatically affect where and whether a tiny rectangle can fit! –  L Spice Dec 9 at 22:42
@L Spice: It's rigorous. You find a subsequence in which the packing of the first $k$ rectangles converges to a fixed configuration. This fixed configuration (the one to which the first $k$ rectangles converges) is the one that doesn't change position when you take a subsubsequence of this subsequence. –  Peter Shor Dec 10 at 2:09

Your Answer


