8
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Del Mar 9 at 15:57
  • $\begingroup$ 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. $\endgroup$ – jmerry Mar 9 at 19:35

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.