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$

193 Views Asked by At

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

enter image description here

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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<j$ 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.