96
$\begingroup$

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

$$\sum_{1 \leq k } \left(\frac{1}{k} \times \frac{1}{k+1}\right) = \sum_{1 \leq k } \left(\frac{1}{k} - \frac{1}{k+1}\right) = 1.$$

The product $\frac{1}{k} \times \frac{1}{k+1}$ is equal to the area of a $\frac{1}{k}$by$\frac{1}{k+1}$ rectangle. The sum of the areas of these rectangles is equal to 1, which is the area of a unit square. Can we use these rectangles to cover a unit square?

Is this problem still open?

What are the best results we know about this problem (or its relaxations)?

$\endgroup$
6
  • 2
    $\begingroup$ Please read “What about open problems?” in FAQ at mathoverflow.net/faq#openproblems $\endgroup$ Aug 1, 2010 at 20:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Aug 1, 2010 at 20:52
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 1, 2010 at 23:00
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 3, 2010 at 14:37
  • 2
    $\begingroup$ As a curiosity and rather extreme relaxation of the problem's constraints, the unit square can be tiled with rectangles of area $\frac 1k \times \frac{1}{k+1}$ but not necessarily with side lengths $\frac{1}{k}$ and $\frac{1}{k+1}$ here. $\endgroup$
    – Jimbo
    Sep 26, 2020 at 15:08

7 Answers 7

55
$\begingroup$

This problem actually goes back to Leo Moser.

The best result that I'm aware of is due to D. Jennings, who proved that all the rectangles of size $k^{-1} × (k + 1)^{-1}$, $k = 1, 2, 3 ...$, can be packed into a square of size $(133/132)^2$ (link).

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.

$\endgroup$
4
  • 23
    $\begingroup$ 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. $\endgroup$ Sep 10, 2010 at 16:22
  • 1
    $\begingroup$ Andrey, would you be able to repair the first link? I believe I repaired the second link correctly. $\endgroup$
    – Todd Trimble
    Oct 9, 2015 at 11:09
  • 1
    $\begingroup$ @Todd Trimble: Thank you so much! I have updated the first link. $\endgroup$ Oct 9, 2015 at 14:04
  • 3
    $\begingroup$ There is some discussion about the correctness of the proof of lemma 1 in the paper of Paulhus in this answer mathoverflow.net/a/278275 $\endgroup$
    – j.c.
    Sep 12, 2017 at 19:27
60
$\begingroup$

Edit: I've replaced the broken links with inline images -- apologies if this takes up more space than the answer deserves. As I mention in a reply, the Paulhus paper cited in a different answer is the good stuff.

As a bit of fun, I have written a program that attempts to fit the first n rectangles into the square. (I accept that this is not an obvious route to a proof.)

Initially, I planned to jumble the rectangles without any strategy, except that I constrained each new rectangle to share a vertex with at least one previous rectangle. Unfortunately, I quickly found that backtracking is extremely time-consuming. In retrospect, this makes sense: if a state is reached where there are only $N$ spaces big enough to accept the next $N+1$ rectangles, backtracking will probably need to try all $N!$ permutations before deciding to backtrack further. (And this is as it should be, because one of the permutations may free up a corner to allow progress.) So, without strategy, 255 rectangles go in and then there is no more progress for a long time in this algorithm: Dead end

So, I added a bit of strategy: try to make as many edge-to-edge joins as possible. With this algorithm, I have reached 40000 (and still going) without any need at all for backtracking. (In fact, it's quite rare to find an exact fit into a gap, where a new rectangle has edge-to-edge contact with three existing rectangles. Therefore, in retrospect, it would probably be roughly as good to insist that new rectangles have two or more edge-to-edge contacts -- which will effectively mean fitting into "corners" where the new rectangle fills the only remaining quadrant at a vertex.)

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.

For the squeamish, look away now: I have been using floating-point arithmetic. With the gcc compiler's somewhat lame "long double", this stores about 20 decimal places. So, I have insisted that an "exact" contact must have coordinates that match to at least 19 decimal places. A "clear" gap or overlap between non-contacts must be at least, say, $10^{-14}$ -- so there are 5 orders of magnitude between "presumably touching" and "presumably separate". You could regard this as having a probabilistic chance of a mistake, and I guess (without justification) the probability might be of order $10^{-5}$.

If gaps are required to be at least $10^{-12}$, then the algorithm is unsure whether $$ {1\over 3912} + {1\over 4124} - {1\over 4050} - {1\over 3981} = {1\over 3612702562200} $$ is zero or gap. If gaps are at least $10^{-13}$, the same happens with $$ {1\over 26981}+{1\over 29981}-{1\over 14201} = {1\over 11487435443561}.$$ These are real examples, and it's easy to concoct other situations that would challenge higher precision. For example, try $$ {1\over 30234}+{1\over 26811}-{1\over 28672}-{1\over 28172} = {1\over 27281801667907584}. $$ So far, no in-between gaps (between $10^{-19}$ and $10^{-14}$) have been encountered.

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.

It may seem pointless to press on beyond 1000, or 2000 or whatever, and it probably is. However, there is an exciting crunch point at about 17000: until this point, there has been a clear region of unfilled space, substantially larger than the incoming rectangles. Any rectangle that doesn't fit conveniently elsewhere can go in there. This is quite a luxurious position: you can tell at a glance that deadlock won't be reached in the next few placements. When that space is filled, are the remaining slivers large enough? -- the rectangles aren't small enough that remaining gaps look like wide-open spaces. Initial experience suggests that this crunch is survived, but of course there may be more crunches to come.

Here are images: Wide open space at 10000: Wide open space

and impending crunch at 15000: Impending crunch at 15000

Then crunch at 17000 (zoomed in): Crunch at 17000

Crunch averted so far, at 30000: Crunch averted so far, at 30000

@Kevin Buzzard: I hope this doesn't take the fun out of your interactive applet. I think you're right that a bit of insight comes out of this square-bashing: there is hope that there are enough small rectangles to more or less fill the gaps between medium rectangles, and enough really small rectangles to more or less fill the gaps between small rectangles, and so on. This seems to be the hope, rather than clever arrangements of exact matches.

I can be specific about the rarity of filling exact matches using this algorithm: 20 three-edge contacts in the first 1000 rectangles, 6 in the next, and 4 in the next. Presumably more could be arranged by thinking ahead. Also, a better algorithm could do a lot more to avoid small gaps (which must be the killer in the end, if there is a killer).

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ed Wynn
    Nov 25, 2013 at 19:57
  • 2
    $\begingroup$ It appears the link to the IMath package is now broken. However, it seems that the code is now on github here github.com/creachadair/imath $\endgroup$
    – j.c.
    Apr 17, 2018 at 10:28
14
$\begingroup$

I think the following result of Greg Martin related to this question deserves to be mentioned here. (It is already referenced in Chapter 3 of the book "Research Problems in Discrete Geometry" by P. Brass, W. O. J. Moser and J. Pach, which is mentioned in the accepted answer.)

Theorem: Let $\mathcal{A}$ be the countable collection of rectangles with dimensions $\frac{1}{1} \times \frac{1}{2}$, $\frac{1}{2} \times \frac{1}{3}$, $\frac{1}{3} \times \frac{1}{4}$, $\dots$ . If $\mathcal{A}$ can be packed into a square of area $1+\epsilon$ for every $\epsilon > 0$, then $\mathcal{A}$ can be packed into a square of area $1$.

The proof is a compactness argument. Under a suitable topology, valid packings (of various packing problems) form compact subsets of the space of all possible positionings of the tiles. If the weakened problem can be solved for every $\frac{1}{k} >0$, then one can extract a subsequence of the sequence of these solutions which converges to a solution of the problem.

$\endgroup$
11
$\begingroup$

It's been a long time since I considered this problem, so prompted by seeing this question I was intrigued to discover more on V. Bálint's bound of $(501/500)^ 2.$

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.

Please could someone with access to the paper lay my concern to rest?

I would very much like to have confidence in the later bound as its validity makes the problem yet more interesting. Can we get arbitrarily close to 1? I still see no good reason why this should be the case but it's a fascinating possibility that hints at the prospect of something quite deep going on.

$\endgroup$
9
  • 17
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Aug 9, 2010 at 16:26
  • 4
    $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Dec 10, 2014 at 2:09
  • 3
    $\begingroup$ The compactness argument seems to be previously known, see also mathoverflow.net/a/294567/3948 $\endgroup$ Mar 6, 2018 at 22:31
  • 2
    $\begingroup$ Well I guess Ed Wynn's computations improve the (501/500)^2 bound by quite a stretch. $\endgroup$
    – Jim Conant
    Dec 13, 2019 at 4:13
  • 5
    $\begingroup$ It's a little disappointing to realize that the (1+1/m)^2 bounds are really just a fancy way of saying somebody succeeded in fitting $m-1$ rectangles. $\endgroup$
    – Jim Conant
    Dec 14, 2019 at 1:25
4
$\begingroup$

Using an ad-hoc Mathematica program, I was able to pack the first $10.000$ rectangles into the unit square. I use no backtracking, but the next square is always placed in a way that the remaining $2 - 3$ rectangles (with sidelength $a$, $b$) minimize the square of their difference $(a-b)^2$. During placement I consider all of the up to $6$ possible placements for all rectangles in my list, where the new rectangle may fit in. Mathematica program available upon request at [email protected]

$\endgroup$
2
  • 4
    $\begingroup$ But Ed Wynn posted about packing 40,000 rectangles with no backtracking. $\endgroup$ Oct 9, 2015 at 10:23
  • 2
    $\begingroup$ If you give my program enough time, it succeeds in packing 50.000 tiles. Without an end in sight... $\endgroup$ Nov 3, 2015 at 20:34
2
$\begingroup$

it is hard to prove this problem directly, but it is not hard to prove (as someone mentioned in some comments) :

If (n-1) rectangles has been put into the 1x1 square, then all rectangles can be put into the square of length (1+1/n)

Proof:

we have put (n-1) rectangles into unit square

denote $P_n = \frac{1}{n} \times \frac{1}{n+1} \sim \frac{1}{n} \times \frac{1}{n}$ , put a rectangle into a square, it is ok

put rectangles from n to infinity in this way of rows and columns into a large rectangle

first row, $P_n \cdots P_{2n-1}$

second row, $P_{2n} \cdots P_{4n-1}$

third row, $P_{4n} \cdots P_{8n-1}$

.... as the following picture showing

enter image description here

the left vertical is the familiar geometric sequence , the length is : $\frac{1}{n} + \frac{1}{2n} + \frac{1}{4n} + \cdots = \frac{2}{n} $ ,

the first horizontal row is the sum of part of harmonic sequence ,$\frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n-1} $

it is easy to estimate the upper bound as : $$ \frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n-1} + \frac{1}{2n} - \frac{1}{2n} \\ = \frac{1}{n} +( \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n-1} + \frac{1}{2n}) - \frac{1}{2n} \\ < \frac{1}{n} +( \ln2) - \frac{1}{2n} = \ln 2 + \frac{1}{2n} $$ (the sum in bracket is easy to check, take $\frac{1}{x}$, the area of integral under the curve is larger than sum of rectanlges)

the length of first row is less than $\ln 2 + \frac{1}{2n}$ ,

the length of second row is less than $\ln 2 + \frac{1}{4n}$ , ...

the first row is longer than the above rows , when n takes big number, like n = 1000, this length $\ln 2 + \frac{1}{2n}$ is obviously less than 1,

for $\ln 2 < 0.7$ .

then rectangles from n to infinity are put into a rectangle of $\frac{2}{n} \times (\ln2 + \frac{1}{2n})$ , and divide this rectangle into two equal smaller rectangles $\frac{1}{n} \times (\ln2 + \frac{1}{2n}) $ along the unit square as following

then we prove all rectangles can be put into a square of length (1+1/n),

although in two stripes it is not efficient to pack them, and can be improved by some ways obviously.

Paulhus gave a graph of 1000 rectangles in unit sqaure in his paper (An Algorithm for Packing Squares) as

enter image description here

and I recovered a result of 1000 rectangle from an algorithm of Antal Joós in his paper (On packing of rectangles in a rectangle) similar to Paulhus' method, (took 2 seconds by a Mathematica program ) like

enter image description here

as Paulhus result, so at least the result (1+ 1/1000) is better than Balint's result in this tricky way , and it seems not hard to go further like 10000

and Paulhus even claimed that he had put 10^9 rectangles into unit sqaure by computer !!!???

if someone has proved the final problem or check results in computer in very large number, please tell me

$\endgroup$
1
$\begingroup$

I have written the following notes as an effort to understand the problem from one perspective.

In short, a function called packing efficiency(aka. packing density) is defined, the problem characterized as preimage of $1$ and two continuity properties proved.

The next step (not written in the notes above, pardon my laziness) would be combining these two properties to prove an infinite version of the first property and also of the second property (since both can be viewed as special cases) with the help of a theorem on interchange of limits, or by directly error estimates. It should be in $l^2$ norm. (if dimension $p$, should be in $l^p$ norm.) (Note carefully that the first property alone would not suffice for this purpose, because the estimates in the proof of the first property is not strong enough to deal with, say, boxes with sidelength $1/n$, whose sum of sidelengths diverge but sum of areas converge.)

The conclusion is, the continuity results would mean that, in a sense, the infinite problem is not so much different from the associated finite problem, which is NP-hard.

Maybe the continuity results have had already been known or at least intuitive, but I didn't find any previous references mentioning such results, anyway here's my two cents.

By the way, we can view continued fractions as perfect packing of maximal squares into rectangles.

There is also the following theory and stories on the related problem of dissecting a given square into squares: squaring

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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