Prove that in a plane, arbitrary $ n$ points can be overlapped by discs that the sum of all the diameters is less than $ n$, and the distances between arbitrary two are greater than $ 1$. (where the distances between two discs that have no common points are defined as that the distances between its centers subtract the sum of its radii; the distances between two discs that have common points are zero)
Problem
Source: Chinese TST
Tags: algorithm, induction, geometry proposed, geometry
The QuattoMaster 6000
26.06.2009 02:14
Let any set of $ n$ points and $ k$ circles, with the property that the $ k$ circles cover all $ n$ points, and that the sum of the diameters of the $ k$ circles is less than $ n - k + 1$, be an "$ (n, k)$ covering." Let a "complete $ (n,k)$ covering" be an $ (n, k)$ covering so that none of the $ k$ circles have a distance of $ x\le 1$. We will prove that for any set of $ n$ points, there exists a $ k$ so that the set has an $ (n, k)$ complete covering. Consider a set of $ n$ points. Cover each of the $ n$ points with a circle of diameter $ \epsilon < \frac {1}{n}$. These $ n$ circles form an $ (n,n)$ covering since the sum of the diameters is less than $ 1$. We now present an algorithm that makes this covering complete:
Step 1: Say that there are two circles that have a distance of $ x\le 1$.
Let these circles be $ (P)$ and $ (Q)$, having diameters $ D_P$ and $ D_Q$ respectively. Let $ PQ$ hit $ (P)$ at $ P_1$ and $ P_2$ and $ (Q)$ at $ Q_1$ and $ Q_2$ so that $ PQ_2 > PQ$ and $ QP_2 > QP$. Then, take the midpoint, $ R$ of $ P_2Q_2$ and draw the circle, $ (R)$, centered at $ R$ with radius $ P_2R = Q_2R$. $ (R)$ has diameter $ D_R = D_P + D_Q + x \le D_P + D_Q + 1$. Now, since $ (R)$ is internally tangent to $ (P)$ and $ (Q)$ (indeed, $ P$, $ Q$, and $ R$ are collinear and $ D_R > D_P, D_Q$),$ (R)$ contains any point that is either in $ (P)$ or $ (Q)$. Furthermore, this step increases the sum of the diameters of the circles by at most one, but decreases the number of circles by precisely one. Therefore, if the input into this step is a covering, the output of this step is also complete a covering.
Step 2: Repeat Step 1 until it is impossble to do so anymore.
It is clear that we cannot do step one indefinitely since step one decreases the number of circles by precisely one each time.
By induction, repeating step 1 always yields coverings. Yet, after doing step 2, there are no circles that have a distance of $ x\le 1$, implying that the covering produced after step 2 is complete, which means that our algorithm works. Since there is at least one circle, the total sum of the diameters is less than $ n$.
Garygogogo
02.08.2022 03:49
The process is simple. We can provide an algorithm to construct the circles. The algorithm start by $n$ circles, whose centres are the original $n$ points and diameters are sufficently small. If the distance of two circles is smaller than 1, then "combine" them together. When the algorithm is done, we get a proper constructio !