Can a finite collection of open discs cover a given set in two dimensions?

[Ackbach]

Here is this week's POTW:

-----

Let $\mathcal F$ be a finite collection of open discs in $\mathbb R^2$ whose union contains a set $E\subseteq \mathbb R^2$. Show that there is a pairwise disjoint subcollection $D_1,\ldots, D_n$ in $\mathcal F$ such that \[E\subseteq \cup_{j=1}^n 3D_j.\]
Here, if $D$ is the disc of radius $r$ and center $P$, then $3D$ is the disc of radius $3r$ and center $P$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 241 - Nov 18, 2016

This was Problem A-5 in the 1998 William Lowell Putnam Mathematical Competition.

Honorable mention to Kiwi for a good attempt, but not quite correct. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

Define the sequence $D_i$ by the following greedy algorithm: let $D_1$ be the disc of largest radius (breaking ties arbitrarily),
let $D_2$ be the disc of largest radius not meeting $D_1$, let $D_3$ be the disc of largest radius not meeting $D_1$ or $D_2$,
and so on, up to some final disc $D_n$. To see that $E \subseteq \cup_{j=1}^n 3D_j$, consider a point in $E$; if it lies in one of the $D_i$, we are done. Otherwise, it lies in a disc $D$ of radius $r$, which meets one of the $D_i$ having radius $s \geq r$ (this is the only reason a disc can be skipped in our algorithm). Thus the centers lie at a distance $t < s+r$, and so every point at distance less than $r$ from the center of $D$ lies at distance at most $r + t < 3s$ from the center of the corresponding $D_i$.