Kvant Math Problem 30

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m54s
Source on kvant.digital

Problem

Prove that $N$ points in the plane can always be covered by several pairwise disjoint circles whose total sum of diameters is less than $N$ and the distance between any two of them is greater than 1. (The distance between two circles is understood to be the distance between their nearest points.)

V. I. Arnold

Exploration

For $N=1$, a single circle of diameter $0$ centered at the point covers it, and the sum of diameters is $0<1$.

For $N=2$, if the points are at distance greater than $1$, two circles of diameter $0$ work. If the distance is at most $1$, one circle containing both points has diameter at most $1$. The statement requires the sum of diameters to be strictly less than $2$, which is then satisfied.

The condition about distances between circles suggests building clusters of points whose mutual separations are controlled. A natural graph appears: connect two points when their distance is at most $1$. The connected components of this graph are separated from each other by distances greater than $1$, because any pair of points belonging to different components cannot be joined by an edge.

The main issue is then to cover each component by a circle and estimate the sum of the resulting diameters.

Suppose a component contains $k$ points. Since the component is connected, it contains a spanning tree with $k-1$ edges, each of length at most $1$. Along the unique path in the tree between any two vertices, the distance between the corresponding points is at most the number of edges in the path. Hence every two points of the component are at distance at most $k-1$.

A set of diameter at most $k-1$ can be covered by a circle of diameter at most $k-1$, namely the circle having as diameter a segment realizing the set diameter. Thus a component with $k$ points can be covered by a circle of diameter at most $k-1$.

If the component sizes are $k_1,\dots,k_m$, then $\sum k_i=N$, and the total diameter does not exceed

$$\sum (k_i-1)=N-m.$$

Since $m\ge1$, this is strictly less than $N$.

The step most likely to hide an error is the passage from connectedness to the estimate that the diameter of a component is at most $k-1$. It must be justified carefully through a spanning tree and the triangle inequality.

Problem Understanding

We are given $N$ points in the plane. We must show that there exists a collection of pairwise disjoint circles such that every point lies in one of the circles, the distance between any two circles is greater than $1$, and the sum of all circle diameters is less than $N$.

This is a Type B problem: we must prove the stated assertion.

The core difficulty is obtaining a global bound on the total sum of diameters. The separation condition suggests partitioning the points into clusters determined by the threshold distance $1$. The challenge is then to show that a cluster containing $k$ points can always be covered by a circle whose diameter does not exceed $k-1$.

Proof Architecture

Lemma 1. Let $G$ be the graph on the given points in which two vertices are adjacent whenever the corresponding points are at distance at most $1$; then points belonging to different connected components of $G$ are at distance greater than $1$ from each other. This follows directly from the definition of connected components.

Lemma 2. If a connected component of $G$ contains $k$ vertices, then every two points of that component are at distance at most $k-1$. Take a spanning tree of the component and use the triangle inequality along the unique tree path.

Lemma 3. Any finite set of points whose diameter is at most $D$ can be covered by a circle of diameter $D$. Choose two points realizing the diameter and use the circle with that segment as diameter.

Lemma 4. A connected component with $k$ points can be covered by a circle of diameter at most $k-1$. Combine Lemmas 2 and 3.

The hardest part is Lemma 2, because the estimate on the component diameter is the ingredient that ultimately yields the bound $N-m$ for the total sum of diameters.

Solution

Construct a graph $G$ whose vertices are the given $N$ points. Join two vertices by an edge whenever the distance between the corresponding points is at most $1$.

Let the connected components of $G$ contain $k_1,k_2,\dots,k_m$ vertices, so that

$$k_1+k_2+\cdots+k_m=N.$$

First we verify the separation property.

Take two points belonging to different connected components. If their distance were at most $1$, then by the definition of $G$ they would be joined by an edge. The two components would then be connected to each other, contradicting the maximality of connected components. Hence every point of one component is at distance greater than $1$ from every point of another component.

Now fix one connected component containing $k$ vertices.

Choose a spanning tree $T$ of this component. The tree has $k$ vertices and $k-1$ edges. Every edge of $T$ has length at most $1$.

Let $A$ and $B$ be any two vertices of the component. In the tree $T$ there is a unique path from $A$ to $B$. If this path contains $r$ edges, then $r\le k-1$. By the triangle inequality,

$$AB\le r\le k-1.$$

Since $A$ and $B$ were arbitrary, the diameter of the whole component is at most $k-1$.

Let $D$ denote the diameter of the component. Choose points $P,Q$ in the component such that

$$PQ=D.$$

Consider the circle having segment $PQ$ as a diameter. Let $X$ be any point of the component. Since $D$ is the diameter of the set,

$$XP\le D,\qquad XQ\le D.$$

Hence

$$XP^{2}+XQ^{2}\le 2D^{2}.$$

Because $PQ=D$, we have

$$XP^{2}+XQ^{2}\le 2PQ^{2}.$$

A standard form of Apollonius' theorem gives

$$XP^{2}+XQ^{2} =2XM^{2}+\frac{PQ^{2}}{2},$$

where $M$ is the midpoint of $PQ$. Therefore

$$2XM^{2}+\frac{PQ^{2}}{2}\le 2PQ^{2},$$

which implies

$$XM^{2}\le \frac{3}{4}PQ^{2}.$$

Thus

$$XM\le \frac{PQ}{2}.$$

Every point of the component lies inside the circle centered at $M$ with radius $PQ/2$. This circle has diameter $PQ=D$.

Since $D\le k-1$, the component can be covered by a circle of diameter at most $k-1$.

Perform this construction for every connected component. The resulting circles cover all given points.

Because every point of one component is at distance greater than $1$ from every point of another component, the distance between any two constructed circles is also greater than $1$. Indeed, each circle is contained in the set of points whose distance from its component is $0$, so the minimum distance between two circles cannot be smaller than the minimum distance between the two components.

For the total sum of diameters we obtain

$$\sum_{i=1}^{m}(k_i-1) = \left(\sum_{i=1}^{m}k_i\right)-m = N-m.$$

Since $m\ge1$,

$$N-m<N.$$

Hence the $N$ points can be covered by pairwise disjoint circles whose mutual distances are greater than $1$ and whose total sum of diameters is less than $N$.

This completes the proof.

∎

Verification of Key Steps

The estimate $AB\le k-1$ requires care. Connectedness alone does not bound distances geometrically. The argument uses a spanning tree. The path from $A$ to $B$ in the tree contains at most $k-1$ edges, each of length at most $1$. Applying the triangle inequality along that path yields

$$AB\le (\text{number of edges})\le k-1.$$

Without introducing the spanning tree, one could mistakenly assume a direct geometric bound that need not exist.

The covering-circle argument must show that a set of diameter $D$ fits into a circle of diameter $D$. Let $P,Q$ realize the diameter. For any point $X$,

$$XP\le D,\qquad XQ\le D.$$

Using Apollonius' theorem gives

$$2XM^{2}+\frac{D^{2}}{2} = XP^{2}+XQ^{2} \le 2D^{2},$$

hence

$$XM\le \frac D2.$$

Thus every point lies in the circle centered at the midpoint of $PQ$ with radius $D/2$. Omitting this computation would leave a genuine gap.

For the final estimate,

$$\sum (k_i-1)=N-m.$$

The strict inequality is obtained from $m\ge1$. If one wrote only $\sum (k_i-1)\le N$, the required strict bound would not follow.

Alternative Approaches

Instead of using the circle whose diameter equals the component diameter, one may invoke Jung's theorem. A planar set of diameter $D$ is contained in a circle of radius at most $D/\sqrt3$, hence of diameter at most $2D/\sqrt3$. Combined with the estimate $D\le k-1$, this yields a stronger bound on the total diameter. However, Jung's theorem is substantially deeper than needed.

Another route is to build the connected components incrementally. Starting from isolated points, whenever two clusters contain points at distance at most $1$, merge them. One can track a quantity equal to the covering diameter minus the number of points in the cluster and show that it never becomes positive. This method is more technical and obscures the simple combinatorial estimate arising from a spanning tree. The graph-theoretic proof isolates the essential idea in the shortest way.