15

Let $D$ be a disc of diameter 20, and suppose you are given 19 rectangles, each of which is $1 \times 20$. Can $D$ be covered completely by the rectangles? Note that the rectangles can be arranged "any which-way" for the covering.

Note: this was a popular poser in my grad student days; some of us came up with an answer, but had a hard time nailing down the proof. I'd like to hear from anyone with a good approach, or even a good reference, to this question.

Added note: the rectangles are not to be cut up. And the question may be posed differently in terms of 19 width 1 "strips", each infinitely long (i.e. copies of $[0,1] \times R$). In this form the question becomes: Can we cover the diameter-20 disk using 19 of these width 1 strips? [If one could cover via strips, then each strip could be trimmed to a 1X20 rectangle without uncovering any covered points in the disk.]

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • 2
    Are the rectangles permitted to overlap each other? – Michael Joyce Nov 05 '12 at 23:24
  • The sum of areas of rectangles are $19\times 20=380$ and the area of the disc is $10^2\times \pi=100\times\pi\approx 314$. So there are enough rectangles to cover it!! How to cover? – Sigur Nov 05 '12 at 23:26
  • For a disc of diameter $n \geq 2$, suppose you have $n-1$ rectangles of dimensions $1 \times n$. Covering the disc when $n = 2$ is clearly impossible, but heuristically likely as $n \rightarrow \infty$, since the area of the disc is $\pi n^2 /4$ and the area of the rectangles is $n^2 - n$, which means for large $n$, (rectangle area) - (disc area) tends to infinity, and we'll have more leeway in how to place the rectangles. This makes me wonder: what is the minimal $n$ for which such a covering is possible? (And will it be possible for all greater integers?) – Benjamin Dickman Nov 05 '12 at 23:54
  • Yes the rectangles are allowed to overlap each other. And certainly there's enough area to do it, provided we use rectangles which overlap near the center of the disk. In any case, the question is: can it be done, and why/why not. – coffeemath Nov 06 '12 at 00:45
  • Well, the area of a shape is the measure of the set of points that intersect it. But these thin rectangles are more like lines than like points. Perhaps the analogous measure on the set of lines which intersect the disk (something that is studied in integral geometry) is the relevant quantity here. –  Nov 06 '12 at 01:05
  • Rahul: But any type of "line" has no area in the plane, yet the rectangles do have positive area. Even a thin rectangle has area, and the rectangles of the problem each have area 20. – coffeemath Nov 06 '12 at 01:37
  • That is why we have to speak of the measure of the set of lines, which gives us something with the units of length, rather than worrying about the area of each line. Observe that in your problem, if we double the area of the rectangles by making their lengths 40, it makes absolutely no difference, so they are effectively infinitely long slabs of width 1. Hence the connection I saw (which nevertheless is little more than idle speculation at this point). –  Nov 06 '12 at 02:42
  • If I cut one rectangle into two $1 \times 10$ rectangles it is easy. – Ross Millikan Nov 07 '12 at 17:31
  • Then you would have 20 rectangles, but problem says 19. :-) If one desires, the rectangles can be viewed as 19 "strips", all of width 1 and infinite length (copies of $[0,1] \times R$). This is because given any configuration of 19 such strips which covered. one could trim each strip to be a $1 \times 20$ rectangle without uncovering anything. – coffeemath Nov 08 '12 at 14:02
  • For the case of infinite strips this is Tarski's plank problem which was solved by Bang // Bang, Thøger (1951), "A solution of the "plank problem"", Proc. Amer. Math. Soc., 2 (6): 990–993, doi:10.2307/2031721, JSTOR 2031721, MR 0046672 – MaxW Oct 13 '23 at 22:04

2 Answers2

14

I remember that problem from university! (But I didn't solve it, somebody gave me a big clue)

The answer is that it is impossible, you can't cover the circle of diameter 20 using only 19 strips $1\times 20$.

To see why, suppose you have such cover and imagine a sphere of diameter 20 cut in half by our circle. Find the orthogonal projection of each strip on the sphere, it is a ring, and it is easy to compute it's area $2\pi R x$, where $R$ is the radius of the sphere and $x$ the width of the strip.

But between all the rings, they cover the whole sphere so the total area must be at least $4\pi R^2$, so $$ N \times 2 \pi R x \ge 4 \pi R^2 $$ where $N$ is the number of strips. Letting $N=19, R=10$ and $x=1$ we obtain a contradiction.

Esteban Crespi
  • 4,007
  • Wow! When our little group "solved" this in grad school, we stayed in the plane to do it, and used the idea that in covering the circumference some strips had to get near the boundary of the disk, and that made their areas too small. We got a bit lost in the details, so I much appreciate your answer. +1. – coffeemath Nov 08 '12 at 17:41
  • 1
    If the disk is partitioned into 20 width one parts of the form $[x_i,x_i+1]$ for $x_i=-10..,9$, the projections on the sphere cover it exactly. And since the surface areas of the slices only depend on their width, this shows you need 20 to cover the surface area, but only have 19. [The surface area of a slice on the sphere being the same as that on a cylinder...] So even without a calculation I should have noticed this, if only I'd thought about the 3-d aspect! – coffeemath Nov 09 '12 at 12:46
1

What follows is an at-least-in-principle-slightly more motivated way to prove the key result. (In reality I came here to see the solution after failing to solve the problem on an exam.) I ignore all questions of convergence of the improper integrals that follow, but they shouldn't cause any real problems.

Let $\Omega\subseteq\mathbb{R}^{2}$ be the open unit disk. It suffices to find a continuous, nonnegative "weight distribution" $w\ \colon \Omega\to\mathbb{R}_{\geq 0}$ such that $$\int_{p\ \in\ \ell\ \cap\ \Omega} w\left(p\right)\text{d}\ell\ =\ \frac{1}{2}$$ for any line $\ell\subseteq\mathbb{R}^{2}$ intersecting $\Omega$ and (thus) that $$\int\int_{p\ \in\ \Omega} w\left(p\right)\text{d}\Omega\ =\ 1.$$ Naturally, we should expect $w$ to be invariant of the rotational symmetries of $\Omega$ (at the very least, the symmetrization of any such $w$ shares the relevant properties, so we might as well assume as much), so what we seek is concretely a continuous function $\widetilde{w}\ \colon\left[0,1\right)\to\mathbb{R}_{\geq 0}$ (i.e., $w$ evaluated at a given radius) such that $$\int_{0}^{1} \sqrt{1-h^{2}}\cdot\widetilde{w}\left(\sqrt{h^{2}+\left(1-h^{2}\right)t^{2}}\right)\text{d}t\ =\ \frac{1}{4}.$$ The most obvious way to make this happen is to choose $\widetilde{w}$ so that the integrand is already independent of $h$. It's not hard to see that taking $$\widetilde{w}\left(r\right)\ \propto\ \frac{1}{\sqrt{1-r^{2}}}$$ achieves this ($\sqrt{1-h^{2}}$ factoring out and cancelling), and in particular when $$\widetilde{w}\left(r\right)\ :=\ \frac{1}{2\pi\sqrt{1-r^{2}}}$$ we have that $$\int_{0}^{1} \sqrt{1-h^{2}}\cdot\widetilde{w}\left(\sqrt{h^{2}+\left(1-h^{2}\right)t^{2}}\right)\text{d}t\ =\ \int_{0}^{1}\frac{1}{2\pi\sqrt{1-t^{2}}}\text{d}t\ =\ \frac{1}{4},$$ as desired. (And in fact, this $\widetilde{w}$ is, up to a constant factor, exactly the weight that is implicitly used in the argument that proceeds by projection onto the surface of the sphere bisected by the disk being covered.)

Ps.: Our $w$ ought to be something like the inverse Radon transform of the function on the space of lines in $\mathbb{R}^{2}$ that is $\tfrac{1}{2}$ at the lines intersecting $\Omega$ and $0$ everywhere elese. Someone more proficient in the Radon transform than I might be able to make that concrete...

Rafi
  • 1,531
  • 6
  • 11