0
$\begingroup$

$n$ circles with total area A have been drawn on the plane (overlapping circles are not counted multiple times). Prove that we can select a disjoint union of circles that has area greater than $\frac{A}{9}$.

I'm thinking that if there is a circle that has an area that is greater than 1/9 then we're basically done. But if not AND the statement is false then we must be full of overlaps. More specifically a point has been covered by at least 9 circles.

$\endgroup$
  • 1
    $\begingroup$ Funny problem; I like it. Where does it come from? Why do you think it's true? What have you tried? $\endgroup$ – user228113 Feb 1 '16 at 3:25
  • 1
    $\begingroup$ @G.Sassatelli This is the same as being able to cover a table with 10 dots on it by 10 circles. See here very instructive. $\endgroup$ – Shailesh Feb 1 '16 at 3:54
  • 1
    $\begingroup$ Thank you for the reference, @Shailesh. $\endgroup$ – user228113 Feb 1 '16 at 3:57
  • $\begingroup$ @Shailesh Why is that the same? $\endgroup$ – Michael Biro Feb 1 '16 at 4:08
  • $\begingroup$ Updated the question $\endgroup$ – The Math Penguin Feb 1 '16 at 4:08
2
$\begingroup$

Consider the circles in order of decreasing radius. We greedily accept each circle if it does not overlap any previously accepted circle.

Now, if we accept a disk of radius $r$, we will disallow any disk that intersects it (which must have radius $\leq r$), all of which are completely covered by a disk of radius $3r$.

Therefore, we cover $\pi r^2$ with our chosen disk, while disallowing at most $\pi (3r)^2$ in area from $A$. In other words, we cumulatively cover a total area of at least $\frac{A}{9}$.

$\endgroup$

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.