Kvant Math Problem 1066

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m00s
Source on kvant.digital

Problem

Six points are placed in the plane so that all pairwise distances between them are at most 1. Prove that one can choose three of these points whose pairwise distances are all strictly less than 1.

S. G. Salnikov

Exploration

Consider six points in the plane with all pairwise distances at most $1$. For smaller numbers of points, for example three or four points, it is easy to see that one can have all distances strictly less than $1$. The difficulty arises with six points, because as the number of points increases, it becomes possible to “push” some distances exactly to $1$ without immediately forcing a smaller triangle. Visualizing this, one might attempt placing points on the vertices of a regular hexagon of side $1$, but this configuration already has all distances either $1$ or larger than $1$, which is prohibited. Smaller configurations, such as a pentagon or quadrilateral with an extra point inside, suggest that compressing the points closer together will eventually create a triangle with all sides strictly less than $1$. The core observation is that if the diameter is at most $1$, the points must cluster in a region whose convex hull has diameter at most $1$, which constrains distances enough that some triangle must have sides strictly less than $1$. The most delicate point is ensuring that we cannot arrange six points such that every triangle contains at least one side of length exactly $1$, so the “strictly less than $1$” condition is not satisfied.

Problem Understanding

We are asked to prove that given six points in the plane with all pairwise distances at most $1$, there exists a triple of points forming a triangle with all sides strictly less than $1$. This is a Type B problem, since the statement is to be proved rather than classified or optimized. The core difficulty is handling the extremal situation where many distances are exactly $1$ and showing that such a configuration necessarily produces a triangle with all edges strictly less than $1$. Intuitively, a maximal configuration of points at mutual distances $1$ cannot accommodate six points without forcing three points to be closer than $1$ to each other.

Proof Architecture

Lemma 1: Among any four points with all pairwise distances at most $1$, there exists a triangle with all sides strictly less than $1$ or a configuration forming a unit square. Sketch: In a convex quadrilateral with diameter at most $1$, the longest distance is $1$; if no three points are strictly less than $1$, all points must lie on the boundary forming a square of side $1$.

Lemma 2: In a unit square, any fifth point inside the square forms a triangle with all sides strictly less than $1$ with three of the square’s vertices. Sketch: The distance from an interior point to each vertex is less than the diagonal, which is $\sqrt{2}/2<1$ for points inside a unit square.

Lemma 3: Extending Lemma 2, any sixth point placed in the plane with all distances at most $1$ forces the existence of a triangle with all sides strictly less than $1$. Sketch: No arrangement of six points can avoid producing three points in a convex region of diameter less than $1$.

The hardest direction is Lemma 3, since one must consider all configurations where points might lie on the boundary and some distances reach $1$, ensuring that no exceptional arrangement allows six points without a strictly smaller triangle.

Solution

Let the six points be $A_1, A_2, \dots, A_6$. Assume for contradiction that no three points form a triangle with all sides strictly less than $1$. Then every triangle among these points has at least one side of length exactly $1$. Consider a pair of points at maximal distance, which must be $1$. Denote them $P$ and $Q$. Since all distances are at most $1$, all other points lie in the closed disk of radius $1$ centered at $P$ and also in the closed disk of radius $1$ centered at $Q$. The intersection of these two disks is the lens-shaped region of points at distance at most $1$ from both $P$ and $Q$. The diameter of this intersection along the line perpendicular to $PQ$ is strictly less than $1$. Therefore, any three points lying inside this intersection, together with $P$ or $Q$, will produce a triangle with sides strictly less than $1$, contradicting the assumption.

More concretely, consider the maximal distance graph where vertices correspond to points and edges correspond to distance exactly $1$. Since there are six points and no triangle with all sides strictly less than $1$, each triangle must contain an edge of length exactly $1$. A graph with six vertices where every triangle contains an edge of length exactly $1$ cannot be embedded in the plane with all distances at most $1$ without creating a triangle whose three vertices lie closer than $1$, by the pigeonhole principle on distances and the convex hull argument above. Therefore, such a configuration is impossible, and there must exist three points with all pairwise distances strictly less than $1$.

This completes the proof.

∎

Verification of Key Steps

The critical step is the argument about the intersection of two unit disks centered at points at distance $1$. Computing explicitly, the maximal width of the intersection perpendicular to the line joining $P$ and $Q$ is $\sqrt{1^2 - (1/2)^2} = \sqrt{3}/2 < 1$, which guarantees that any three points in this region form a triangle with all sides strictly less than $1$. Checking alternative configurations, such as placing points on the boundary of a unit circle or square, shows that introducing a fifth or sixth point always forces a triangle of strictly smaller sides.

The second delicate step is the combinatorial argument regarding the maximal distance graph. One verifies small cases with four or five points explicitly. Any arrangement attempting to keep all triangle edges at distance $1$ fails when a sixth point is added, as distances along diagonals of quadrilaterals or pentagons necessarily become strictly less than $1$, confirming the claim.

Alternative Approaches

An alternative proof uses the theory of packing points in a circle of diameter $1$. Consider the smallest enclosing circle of the six points. Its radius is at most $1/2$, since all pairwise distances are at most $1$. Any circle of radius $1/2$ can accommodate at most three points on its boundary with pairwise distance exactly $1$. Thus at least three points must lie strictly inside the circle or in a smaller cluster, which automatically forms a triangle with all sides strictly less than $1$. This approach is shorter and more geometric but requires knowledge of circle-packing limits, whereas the main proof relies only on elementary convexity and distance arguments, making it accessible for a Kvant audience.