Putnam 1998, Problem A-5

Let \( \mathscr{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 \( \mathscr{F} \) such that
\[
E \subseteq \bigcup_{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 \).

Solution:
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 \bigcup_{j=1}^n D_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 \).