27
$\begingroup$

My question is prompted by this illustration from Eugenia Cheng’s book Beyond Infinity, where it appears in reference to the Basel problem.

Illustration of squares of side 1/2, …, 1/11 in three quarters of a unit square

Is it known whether the infinite set of squares of side $\frac{1}{2}, \frac{1}{3}, \frac{1}{4},...$ can be packed into three quarters of a unit square?

(It doesn't seem obvious that the illustrated packing could be continued to infinity.)

$\endgroup$
  • 3
    $\begingroup$ Answers regarding this similar problem might suggest some possible approaches: mathoverflow.net/questions/34145/… $\endgroup$ – Yoav Kallus Aug 8 '17 at 14:41
  • $\begingroup$ @YoavKallus Thanks! The comment by Timothy Chow referencing Marc Paulus's paper An algorithm for packing squares seems particularly relevant. sciencedirect.com/science/article/pii/S0097316597928363 $\endgroup$ – Robin Houston Aug 8 '17 at 14:53
  • 5
    $\begingroup$ I think this actually should be much easier than the other problem, just because $\frac{\pi^2}{6}-1<\frac{3}{4},$ which gives you a chance of reducing this to a finite computation. In particular if there is an $n$ so that you can pack squares of side lengths $1/2\cdots, 1/(n-1)$ and $n$ right triangles of side length $2/n$, then you can also pack the squares in the question. This is because you can pack squares of side length $1,1/2,\cdots$ in a right triangle of side length $2$. $\endgroup$ – dhy Aug 8 '17 at 15:04
21
$\begingroup$

The standard simple proof that $\sum_{n=1}^\infty \frac1{n^2}$ converges is to round each $n$ down to the nearest $2^k$; this rounds each $\frac1{n^2}$ up to the nearest $\frac1{2^{2k}}$. In fact, one gets $2^k$ copies of $\frac1{2^{2k}}$ for each $k$; hence $$\sum_{n=1}^\infty n^{-2} < \sum_{k=0}^\infty 2^k\frac1{2^{2k}} = \sum_{k=0}^\infty \frac1{2^{k}} = 2.$$

This is a sloppy estimate, and one way of improving it is to round each $n$ down to the nearest $2^k$ OR $3\cdot2^{k}$. The first cluster of $\frac1{2^{2k}}$s, comprising a single $\frac1{2^0}$, is unaffected; all subsequent clusters cleave into $2^{k-1}$ copies of $\frac1{2^{2k}}$ and $2^{k-1}$ copies of $\frac1{(3\cdot2^{k-1})^2}$. In this way, we get $$\sum_{n=1}^\infty n^{-2} < 1+\sum_{k=1}^\infty 2^{k-1}\frac1{2^{2k}} + \sum_{k=1}^\infty 2^{k-1}\frac1{(3\cdot2^{k-1})^2} \\ = 1+\sum_{k=1}^\infty \frac1{2^{k+1}} + \frac19\sum_{k=1}^\infty \frac1{2^{k-1}} = 1 + \frac12+\frac29.$$

This sum (minus the irrelevant first term) can be represented geometrically as in the following image, which is reasonably similar to the one you posted. (But the shaded region has area $\frac16+\frac19=\frac5{18}>\frac14$.)

enter image description here

$\endgroup$
  • 4
    $\begingroup$ That's a nice solution. I might add that the rows that start with 1/12, 1/24, 1/48, and so on can be rotated to columns and moved into the shaded region between 1/2 and 1/3 to obtain a solution to the problem in the original post. $\endgroup$ – Yoav Kallus Aug 8 '17 at 19:55
  • 1
    $\begingroup$ You might observe that the "packing area" in your image can be dissected and rearranged (without cutting any interior squares) into (a continuation of) the image in the question. Gerhard "This Makes 'Yes' Appropriately Explicit" Paseman, 2017.08.08. $\endgroup$ – Gerhard Paseman Aug 8 '17 at 19:58
  • $\begingroup$ Thank you! You are, of course, both correct---my main excuse is that I drew what was easiest for me to draw. (Note how the paper has been strategically folded.) I also wanted to emphasise the two geometric series (one up the left-hand side, the other up the right-hand side). If I weren't a dunce at computer graphics, I'd make an animation to show how the various pieces can be rearranged. $\endgroup$ – Jeff Egger Aug 8 '17 at 20:53
  • $\begingroup$ Instead of an animation, cut your square in half and rotate the right half. Then take the part that "sticks out" of the unit square and duplicate it to the appropriate place in the unit square, and draw an arrow showing the correspondence. Gerhard "We Can Imagine The Motion" Paseman, 2017.08.08. $\endgroup$ – Gerhard Paseman Aug 8 '17 at 21:51
  • $\begingroup$ If I didn't overlook anything, this does prove that total area is less than 3/4, but how does this prove that it is actually possible to put the squares? Perhaps there might be some "leftover space between squares" that can't be dealt with... Although my intuition says it is indeed possible, I think this part should also be explicitly addressed in an answer to this question. For example, I doubt this could be done with circles of areas $\frac{1}{n^2}$. $\endgroup$ – Pedro A Aug 9 '17 at 10:36
15
$\begingroup$

Note: This answer is wrong. There are two problems:

  1. The claim of Lemma 1 should presumably be read in the context of the global assumption in Paulhus's paper that $w\leq l$. This assumption invalidates the instance I wanted to use (i.e. $l=\frac12$, $w=1$).

  2. The proof of the lemma seems flawed, as mentioned below and succinctly summarised in Yoav Kallus’s comment. Another example where the packing constructed for the proof does not fit is $l = \frac{9}{5}$, $w = \frac{7}{9}$, $n=2$, which I mention only since (unlike the example below) it has $w<l$.

The answer as written is next, followed by the note of doubt I added after trying to understand the proof.


The answer is yes.

Thanks to the comment by Yoav Kallus above, and a comment by Timothy Chow on the question he linked to, I found the paper An algorithm for packing squares by Marc M. Paulhus. (Journal of Combinatorial Theory, Series A, Volume 82, Issue 2, 1998, Pages 147-157)

Lemma 1 of that paper shows: All the reciprocal squares from n to infinity can be packed in a rectangle of length $l$ and width $w$ provided $$n\geq \frac{1+l}{wl}$$

With $l=1/2$ and $w=1$, this shows that we could place the square of side 1/2 in such a way that the remaining space is a rectangle of dimensions 1 x 1/2, and then pack the remaining squares into that rectangle using Paulhus's procedure.

It doesn't obviously answer the question of whether the packing could be completed if started as shown. In particular, can the squares of side 1/3, 1/4, etc. be packed into two unconnected squares of side 1/2?


Added previously: I am not convinced that the proof of Lemma 1 used above is correct. As I understand it (specialising to the case $l=\frac 12$, $w=1$ for concreteness) the idea is to pack the squares in rows like this:

packing squares of side 1/3, 1/4, … into a rectangle of dimensions 1/2 x 1

If the first square in row $i$ has side $1/{n_i}$, then $n_0=3$ and $n_{i+1}=\lfloor \frac{3}{2}n_i\rfloor$.

But then the total height of the first seven rows is already $$\frac 13 + \frac 14 + \frac 16 + \frac 19 + \frac 1{13} + \frac 1{19} + \frac 1 {28} > 1.$$

On the other hand this arrangement is not optimal, since the sixth row has squares $\frac 1{19}, \dots, \frac 1{27}$ but we could fit up to $\frac 1{30}$. So perhaps the claim is still true, notwithstanding the unconvincing proof?

$\endgroup$
  • 3
    $\begingroup$ The top-left square in the illustration in the question includes a free rectangle of dimensions $1/4\times3/8$. By Lemma 1, this should be enough to hold reciprocal squares for $n\ge14$. I believe 12 and 13 comfortably fit in the free space in the bottom-right square, next to the 11. $\endgroup$ – Emil Jeřábek Aug 8 '17 at 16:26
  • 4
    $\begingroup$ You seem to be correct that the proof is in error. Particularly, I see a false deduction in the last set of inequalities: the proof claims that if $w\ge(1+l)/(n_0 l)$ ($=(1/n_0)\sum_{i=0}^\infty (1/(1+l))^i$), then $w\ge \sum_{i=0}^{\infty} 1/n_i$ follows. That would make sense if we had $n_i\ge n_0 (1+l)^i$, but the inequality shown earlier is actually reversed. $\endgroup$ – Yoav Kallus Aug 8 '17 at 19:48
  • 5
    $\begingroup$ Perhaps this could also be due to an assumption in the paper earlier that width is considered smaller (i.e., $l\geq w$)? $\endgroup$ – LegionMammal978 Aug 8 '17 at 21:12
  • 5
    $\begingroup$ I think your argument is somewhat useful, though. $\endgroup$ – Takahiro Waki Aug 8 '17 at 23:42
  • 2
    $\begingroup$ @RobinHouston Even if you put as many squares as possible into each row, the height of the first seven rows will be $\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{9}+\frac{1}{14}+\frac{1}{22}+\frac{1}{35}>1$. $\endgroup$ – Peter Mueller Aug 9 '17 at 7:29
0
$\begingroup$

Using Clive Tooth's heuristic for this similar (but more difficult) problem https://math.stackexchange.com/questions/2645195/can-the-squares-with-side-1-n-be-packed-into-a-1-times-zeta2-rectangle

I was able to pack the first 10^9 squares into the 3/4 unit square. Not a proof, of course, but evidence, at least, that no "bottleneck" occurs when placing the smallest sized squares.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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