43
$\begingroup$

Can a disk of area $1$ be completely covered by six disks of areas $\frac12,\frac13,\frac14,\frac15,\frac16,\frac17$ ? The disks may overlap.

I made a Desmos graph where you can move the disks around.

So far this is my best effort (the equations can be seen when you open the Desmos graph):

enter image description here

Approximately 99.96% of the big disk is covered. There are small gaps near the perimeter.

No matter how I arrange the disks, there always seems to be gaps. It seems impossible to cover the big disk, but I don't know how to prove it.

(In the Desmos graph the disks all have their areas multipled by $\pi$ but that doesn't matter.)

Related fact: A square of area $1$ can be covered by six disks of areas $\frac12,\frac13,\frac14,\frac15,\frac16,\frac17$, but just barely.

This question was inspired by the question "What is the largest disk that will be completely covered by randomly placed disks of areas $1,\frac12,\frac13,\dots$ with probability $1$?".

$\endgroup$
4
  • 4
    $\begingroup$ I deleted the tag "covering-spaces" because it has nothing to do with your question. It is an algebraic topology tag. $\endgroup$
    – Paul Frost
    Jan 19 at 9:03
  • $\begingroup$ @PaulFrost OK, I misunderstood that tag. Thanks. $\endgroup$
    – Dan
    Jan 19 at 9:04
  • $\begingroup$ I presume that thr $7$ here is particular i.e., you have precisely these $6$ disks you get to place to cover, and you are not allowed in addition another disk of area $\frac{1}{8}$ $\endgroup$
    – Mike
    Jan 19 at 18:46
  • $\begingroup$ @Mike That's right. $\endgroup$
    – Dan
    Jan 19 at 19:37

2 Answers 2

16
$\begingroup$

It's impossible.

We'll show this by exhibiting a subset of the large disk that the smaller disks cannot cover more than $99.91\%$ of even if we count coverings with multiplicity, which is much easier to check. Specifically, we'll choose a set of four extremely thin rings centered around the origin, tuning their relative thicknesses to make the impossibility proof work out. We also renormalize so the central disk has radius $1$ and the smaller disks have radii in the set $R = \{1/\sqrt{2}, 1/\sqrt{3},\ldots,1/\sqrt{7}\}$.

By the Law of Cosines, the fraction of an origin-centered ring of radius $x$ covered by a disk of radius $r$ whose center is distance $d$ from the origin is

$$\frac{\arccos\left(\frac{d^2+x^2-r^2}{2dx}\right)}{\pi}$$

where we cap the output of $\arccos()$ if its input lies outside the range $[-1,1]$.

If we look at $x=1$, ie the perimeter of the disk, we can look at the fraction of perimeter covered by each disk as a function of $d$:

enter image description here

Adding up the maxima of these fractions for each $r\in R$ gives us a total covering fraction of $1.0173$, which doesn't rule things out as yet but suggests that we don't have much room to maneuver away from the perimeter.

Generalizing a bit, we'll add three more rings, so we look at $X =[x_1,x_2,x_3,x_4=1]$. We'll then weight these rings by $W = [w_1,w_2,w_3,w_4]$, where we normalize $W$ to sum to $1$. If we can find values of $X$ and $W$ such that

$$\sum_{r\in R}\max_{d\in[0,1+r]}\left(\sum_{i=1}^4\frac{w_i}{\pi}\arccos\left(\frac{d^2+x_i^2-r^2}{2dx_i}\right)\right) < 1$$

then we'll know the problem is impossible, since in any valid solution the sum of covered fractions along each ring (and hence any weighted sum thereof) would need to exceed 1. (We could also think of this as using an equally-weighted sum across a 2D region, where we each turn each ring into an annulus of thickness $\epsilon w_i/x_i$ - for small enough $\epsilon$, this will have behavior arbitrarily close to the above setting.)

I fed this function into scipy.optimize.minimize with the constraint that all weights be nonnegative and it spit out the solution $X=[0.05,0.2384,0.3932,1], W=[0.01785, 0.04577, 0.02912, 0.90725]$. With these parameters the maximum weighted sum is around $0.999005$. The weighted scores for each disk as a function of $d$ are graphed below:

enter image description here

$\endgroup$
5
  • $\begingroup$ Nice! Just a few comments about wording. Where you wrote "tuning their relative thicknesses" did you mean "tuning their radii"? Where you wrote "a disk of radius $r$ at distance $d$ from the origin" did you mean "a disk of radius $r$ whose centre is distance $d$ from the origin"? $\endgroup$
    – Dan
    Jan 25 at 12:37
  • $\begingroup$ Can you avoid the use of weights by using more rings? Do you have any references for simpler problems that use weights in a similar way? $\endgroup$ Jan 25 at 15:12
  • 1
    $\begingroup$ By fiddling I found that X = [0.05, 0.24, 0.4, 1] and W = [0.02, 0.049, 0.03, 0.901] also works with sum about 0.9999916. $\endgroup$ Jan 25 at 15:50
  • 1
    $\begingroup$ @Dan: Yes to your second question; for the first one, I was referring to tuning $W$, which can also be thought of as turning each 1D ring of radius $x_i$ and width $w_i$ into a very very thin 2D annulus with thickness $\epsilon w_i/x_i$ for some small epsilon and then weighting uniformly by area. I'll edit the post to make the wording clearer! $\endgroup$ Jan 25 at 18:57
  • 1
    $\begingroup$ @LewisBaxter yes; just choose some rational numbers very close to each $w_i$, then duplicate each ring so that the relative ratios work out. (If you want the rings to be distinct, you can of course add a very small perturbation to each ring by continuity.) $\endgroup$ Jan 25 at 18:57
3
$\begingroup$

Here are some numerical results that suggest that the covering is impossible.

I wrote a program to generate points $P_1$ and $P_2$ and then successively construct all other points and circles as shown. One small gap remains.

enter image description here

Circle $C_1$ is $x^2+y^2 = 1$. Circle $C_2$ has centre $ (0.5 \pm \delta, 0 )$ - with $ \delta = 0.01$ - from which $P_1$ is constructed. $P_2 (x_2,y_2)$ is constructed with $ x_2 = \pm \delta$. All other points and circles are constructed in the order: $(C_6, C_4, C_3, C_5$ and $C_7)$.

After $10^9$ random generations the smallest gap found has an area of 0.1754% of the area of $C_1$.

The corresponding circle centres are: $ C_1 (0,0), C_2 (0.5009,0.0000), C_3 (-0.6327,-0.0210), C_4 (-0.4046,0.7151), C_5 (-0.3917,-0.6770), C_6 (0.3779,0.8310) \text{ and } C_7 (0.2589,-0.8278).$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .