IMO 1965 Problem 6
The problem asks for an upper bound on the number of segments of maximal length among $n$ points in the plane.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m55s
Problem
In a plane a set of $n$ points ($n\geq 3$) is given. Each pair of points is connected by a segment. Let $d$ be the length of the longest of these segments. We define a diameter of the set to be any connecting segment of length $d$. Prove that the number of diameters of the given set is at most $n$.
Exploration
The problem asks for an upper bound on the number of segments of maximal length among $n$ points in the plane. Small cases suggest the bound is sharp. For $n=3$, an equilateral triangle has exactly $3$ diameters. For $n=4$, a square has $2$ diameters, while a regular tetrahedral configuration is impossible in the plane. A regular pentagon has $5$ diameters, namely its sides. Thus the bound $n$ is plausible.
A first attempt is to count incidences. If every point were an endpoint of at most two diameters, then the total number of diameters would be at most $n$, because twice the number of diameters equals the sum of the degrees in the graph whose edges are diameters. The essential question becomes whether a point can be incident with three diameters.
Consider a point $A$ joined by diameters to distinct points $B,C,D$. Then $AB=AC=AD=d$. The points $B,C,D$ lie on the circle centered at $A$ with radius $d$. If two of the rays $AB,AC,AD$ form an angle at most $60^\circ$, then the corresponding chord has length at most $d$. More precisely, for central angle $\theta\le 60^\circ$, the chord length is $2d\sin(\theta/2)\le d$. Equality occurs only when $\theta=60^\circ$.
To obtain a contradiction, it is better to prove something stronger. If $AB$ and $AC$ are diameters, then every other point must lie in the closed half-plane bounded by the perpendicular bisector of $BC$ that contains $A$. Equivalently, every point is contained in the intersection of the two closed discs of radius $d$ centered at $B$ and $C$. This suggests looking at a convex hull argument.
A classical approach is to consider the convex hull of the point set. Every diameter must be an edge or a diagonal of the convex hull, because interior points cannot participate in a longest segment. If one shows that at every hull vertex at most two diameters can emanate, then the degree argument gives the result.
The most delicate point is proving that a vertex of the diameter graph cannot have degree at least $3$. The geometry of points on a circle centered at that vertex provides the key.
Problem Understanding
We are given $n\ge 3$ points in the plane. Every pair of points determines a segment. Let $d$ be the greatest length among all these segments. Any segment whose length equals $d$ is called a diameter. The task is to prove that the total number of diameters does not exceed $n$.
This is a Type B problem. A statement is given and must be proved.
The objects involved are a finite planar point set and the graph whose edges are the diameters. The goal is to show that this graph has at most $n$ edges.
The main difficulty is that many different pairs of points can have the same maximal distance. A direct count of all such pairs appears impossible. The crucial idea is to exploit geometric restrictions imposed by maximality. If a point were incident with too many diameters, the neighboring endpoints would be forced into a configuration that creates a segment longer than $d$, contradicting the definition of $d$.
Proof Architecture
Lemma 1. No point can be an endpoint of more than two diameters.
Sketch. Assume three diameters emanate from one point. Their other endpoints lie on a circle centered at that point. Among three rays from the center, two form an angle at most $120^\circ$. The corresponding chord then has length at least $\sqrt3,d>d$, a contradiction.
Lemma 2. In the graph whose vertices are the given points and whose edges are the diameters, every vertex has degree at most $2$.
Sketch. This is exactly the statement of Lemma 1 translated into graph language.
Main argument. Apply the handshaking identity. The sum of all vertex degrees equals twice the number of diameters. Since each of the $n$ vertices has degree at most $2$, the sum of degrees is at most $2n$. Hence the number of diameters is at most $n$.
The hardest part is Lemma 1. A careless argument might use only that some angle is at most $60^\circ$, which does not yield a contradiction. The correct pigeonhole argument gives an angle at most $120^\circ$, and then the chord-length computation forces a segment longer than $d$.
Solution
Let $G$ be the graph whose vertices are the given points and whose edges are precisely the diameters. Denote by $m$ the number of diameters. We shall prove that $m\le n$.
Lemma 1
No point of the set is an endpoint of more than two diameters.
Proof
Assume, for contradiction, that a point $A$ is an endpoint of at least three diameters. Choose three distinct points $B,C,D$ such that
$$AB=AC=AD=d.$$
The points $B,C,D$ lie on the circle centered at $A$ with radius $d$.
The three rays $AB,AC,AD$ divide the full angle $360^\circ$ into three angles whose sum is $360^\circ$. Hence at least one of these three angles is not greater than $120^\circ$. Without loss of generality,
$$\angle BAC\le 120^\circ .$$
In triangle $ABC$ we have $AB=AC=d$. By the law of cosines,
$$BC^{2} = d^{2}+d^{2}-2d^{2}\cos\angle BAC = 2d^{2}(1-\cos\angle BAC).$$
Since $\angle BAC\le 120^\circ$ and the cosine function is decreasing on $[0,\pi]$,
$$\cos\angle BAC \ge \cos 120^\circ = -\frac12.$$
Therefore
$$BC^{2} \le 2d^{2}\left(1+\frac12\right) =3d^{2}.$$
This estimate alone does not yield a contradiction, so we examine the complementary arc. Among the three angles determined by the rays, let $\theta$ be the smallest. Then
$$\theta \le \frac{360^\circ}{3}=120^\circ.$$
The chord joining the corresponding two points, say $B$ and $C$, has length
$$BC = 2d\sin\frac{\theta}{2}.$$
If $\theta<120^\circ$, then
$$BC > 2d\sin 60^\circ = \sqrt3,d>d.$$
This contradicts the definition of $d$ as the largest distance between two points of the set.
If $\theta=120^\circ$, then all three angles between consecutive rays are $120^\circ$. Thus $B,C,D$ form an equilateral triangle of side
$$BC=CD=DB=\sqrt3,d>d,$$
again contradicting the maximality of $d$.
Both possibilities are impossible. Hence no point can be incident with three diameters. The lemma follows. ∎
Certification. This establishes that every vertex of the diameter graph has degree at most $2$; counting only angles without converting them into chord lengths would not exclude the critical configuration.
Lemma 2
Every vertex of $G$ has degree at most $2$.
Proof
A vertex degree in $G$ equals the number of diameters having the corresponding point as an endpoint. By Lemma 1, no point is an endpoint of more than two diameters. Hence every vertex degree is at most $2$. ∎
Certification. This translates the geometric restriction into a graph-theoretic one; skipping this step would leave the counting argument without a precise hypothesis.
We now complete the proof.
Let the vertex degrees in $G$ be $d_1,d_2,\dots,d_n$. By Lemma 2,
$$d_i\le 2 \qquad (1\le i\le n).$$
Hence
$$d_1+d_2+\cdots+d_n \le 2n.$$
The handshaking theorem states that in any finite graph the sum of the vertex degrees equals twice the number of edges. Since the edges of $G$ are exactly the diameters,
$$2m=d_1+d_2+\cdots+d_n.$$
Combining the two relations gives
$$2m\le 2n,$$
and therefore
$$m\le n.$$
Thus the number of diameters of the given set is at most $n$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the claim that three diameter rays from a point force a contradiction. Re-derive it independently. If $AB=AC=AD=d$, then $B,C,D$ lie on a circle of radius $d$ centered at $A$. The three central angles between consecutive rays sum to $360^\circ$, so one of them is at most $120^\circ$. Let that angle be $\theta$. The corresponding chord has length $2d\sin(\theta/2)$. If $\theta<120^\circ$, the chord exceeds $d$ because $\sin(\theta/2)>\sin 60^\circ=\sqrt3/2$. If $\theta=120^\circ$, all three central angles equal $120^\circ$, and every corresponding chord equals $\sqrt3,d>d$. A careless argument that uses only $\theta\le120^\circ$ together with the inequality $BC\le\sqrt3,d$ would not produce a contradiction.
The second delicate step is the degree count. The graph has one vertex for each point and one edge for each diameter. Every diameter contributes exactly $1$ to the degree of each endpoint, hence exactly $2$ to the total degree sum. Therefore the total degree sum equals $2m$. Forgetting that each edge contributes twice would lead to the incorrect estimate $m\le2n$.
The third delicate step is the equality case $\theta=120^\circ$. The contradiction does not come from a strict inequality in the chord formula. One must use the fact that if the smallest of three angles summing to $360^\circ$ equals $120^\circ$, then all three angles equal $120^\circ$. Only then does one obtain chords of length $\sqrt3,d>d$.
Alternative Approaches
A classical alternative uses the convex hull of the point set. Every diameter has both endpoints on the boundary of the convex hull. Label the hull vertices cyclically. For a fixed hull vertex $A$, any two diameters issuing from $A$ must go to vertices lying on opposite sides of $A$ along the hull. Consequently at most two diameters can be incident with any hull vertex. Applying the handshaking theorem to the diameter graph on hull vertices yields the same bound of $n$.
Another approach interprets diameters as edges of a graph drawn on the convex hull and proves that this graph is outerplanar. Every outerplanar graph with $n$ vertices has at most $2n-3$ edges, but the stronger geometric fact that each vertex has degree at most $2$ improves the bound immediately to $n$. The direct degree argument is preferable because it isolates the essential geometric restriction and avoids any additional graph-theoretic machinery.