# Given $n$ circles of radii $r_1,r_2,…,r_n$ inseparable by straight lines, prove that they can be covered by a circle of radius $r_1+r_2+…+r_n$

Definition:

A subset $$A\subset\mathbb R^2$$ is inseparable by straight lines if there doesn't exist a straight line $$L$$ such that $$L \cap A=\emptyset$$ and $$L$$ divides $$A$$ into $$2$$ nonempty parts, lying on both sides of $$L$$.

Question:

Given $$n$$ circles of radii $$r_1,r_2,...,r_n$$ inseparable by straight lines, prove that they can be covered by a circle of radius $$r_1+r_2+...+r_n$$.

I'm thinking about induction, but removing one circle could potentially lead to $$n-1$$ circles separable by straight lines, like this

Any ideas?

Edit: The one who told me this problem said it's in a book written by L. Fejes Tóth, not sure which one.

• What's the context of the question? Why do you think the statement is true? – Greg Martin Mar 9 at 9:13

The key to this one is to start with the right point as the center. Looking at the case of two tangent circles of radius $$r_1$$ and $$r_2$$, I found the point on the segment between the centers, at distance $$r_2$$ from the first center and $$r_1$$ from the second, worked. How does this generalize? A weighted center of mass.

Proposition: Given $$n$$ circles $$C_1,C_2,\dots,C_n$$ of radius $$r_1,r_2,\dots,r_n$$ with centers $$O_1,O_2,\dots,O_n$$ that are inseparable by straight lines, the circle $$C$$ centered at the weighted center of mass $$\frac{r_1O_1+r_2O_2+\cdots+r_nO_n}{r_1+r_2+\cdots+r_n}$$ of radius $$R=r_1+r_2+\cdots+r_n$$ contains all of the other circles.

Proof: Choose a circle $$C_k$$, and choose coordinates so that $$x$$ is the unit in the direction of $$O-O_k$$. Let $$x_j$$ be the $$x$$-coordinate of $$O_j$$, and let $$u_j=x_j-r_j$$. Relabel the circles in order of increasing $$u$$, so that $$u_1\le u_2\le \cdots \le u_n$$. Also, note the new number $$k'$$ for the circle we chose at the start.

Since vertical lines don't separate the circles, we have that for each $$j>1$$, there is some $$i with $$x_i+r_i \ge u_j$$, and therefore $$u_j-u_i \le 2r_i$$. From this, it follows that $$u_j\le u_1+2r_1+2r_2+\cdots+2r_{j-1}$$ and $$x_j=u_j+r_j\le u_1+2r_1+2r_2+\cdots+2r_{j-1}+r_j=u_1+r_j+\sum_{i=1}^{j-1}2r_i$$ $$\sum_{j=1}^n r_jx_j \le u_1\sum_{j=1}^n r_i + \sum_{j=1}^n r_j\left(r_j+\sum_{i=1}^{j-1}2r_i\right)=u_1\sum_{j=1}^n r_i+\sum_{j=1}^nr_j^2+2\sum_{j=1}^n\sum_{i=1}^{j-1}r_ir_j$$ $$(X-u_1)\sum_{j=1}^n r_j \le \left(\sum_{j=1}^n r_j\right)^2$$ $$X-u_1 \le \sum_{j=1}^n r_j = R$$ In the above, $$X$$, is the $$x$$-coordinate of the center of mass $$O$$. Now, by hypothesis, the center $$O_{k'}$$ of the circle $$C_{k'}$$ we based this on lies on the ray in the negative $$x$$ direction from $$O$$. The distance from $$O_{k'}$$ to $$O$$ is therefore equal to $$X-x_{k'}$$. Since $$u_{k'}\ge u_1$$, we get $$X-x_{k'}=X-u_{k'}-r_{k'}\le X-u_1-r_{k'}=R-r_{k'}$$ If the distance between the centers of two circles is no more than the difference of their radii, the small circle lies within the larger circle. The circle $$C_{k'}$$ lies within $$C$$. But the choice of circle was arbitrary. As such, all of the small circles lie within the large one, and we're done.

• How do you obtain $u_j\le u_1+2r_1+2r_2+\cdots+2r_{j-1}$? I imagine a telescopic sum, but from the previous reasoning you don't have that $u_j-u_{j-1}\leq 2r_{j-1}$, but just that there exists some $i$ such that $u_j-u_i\leq 2r_i$. It could be the same $i$ for all $j$ right? – Del Mar 9 at 15:57
• It could be, yes. We have $u_j \le u_i+2r_i \le u_i+2r_i+2r_{i+1}+\cdots+2r_{j-1}$. Having a smaller $i$ gives us a smaller bound for $u_j$, and then we give that up immediately for the sake of that "telescopic" sum. – jmerry Mar 9 at 19:35

Let $$A \subseteq \mathbb{R}^2$$ be the union of the $$n$$ circles and consider the functions $$f,g \colon A \to \mathbb{R}$$ given by $$f(x,y) = x$$ and $$g(x,y) = y$$. Since $$A$$ is compact and $$f$$ and $$g$$ are continuous, $$a = \min_A(f), b = \max_A(f), \quad c = \min_A(g), d = \max_A(g)$$ exist. Note that then $$A \subseteq [a,b] \times [c,d]$$. Then for every $$x_0 \in (a,b)$$, there exists a point $$(x_0,y) \in A$$, or else the vertical line $$x = x_0$$ would separate $$A$$. Similarly, for every $$y_0 \in (c,d)$$, there exists a point $$(x,y_0) \in A$$. We see that then $$2\sum_{i=1}^n r_i \geq \max(b-a, d-c) =M.$$ Let $$P$$ be the center of $$R = [a,b] \times [c,d]$$. The distance between $$P$$ and any point in $$R$$ is at most $$\sqrt{\frac{(b - a)^2 + (d -c)^2}{4}} \leq \frac{M}{\sqrt{2}}.$$ Since $$r \geq M$$, it follows that the circle of radius $$\sqrt{2}\sum_{i=1}^nr_i$$ centered at $$P$$ contains $$R$$, hence it also contains $$A$$.

Perhaps one can argue further to eliminate the $$\sqrt{2}$$

• So, you're claiming that a circle of radius $(r_1+r_2+\cdots+r_n)/\sqrt{2}$ covers everything? Nope. That fails even the one-circle case. – jmerry Mar 9 at 10:10