Putnam 1998

Problem A5

A finite collection of disks covers a subset X of the plane. Show that we can find a pairwise disjoint subcollection S, such that X ⊆ ∪{3D : D ∈ S}, where 3D denotes the disk with the same center as D and 3 times the radius.




The key observation is that if disk D has larger radius than any disk intersecting it, then 3D covers D and any disks intersecting it.

So take D1 to be the largest disk. Remove D1 and those intersecting it. Now take D2 to be the largest disk remaining. And so on.



Putnam 1998

© John Scholes
12 Dec 1998