In a plane a set of $n\geq 3$ points 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$.
Problem
Source: IMO 1965, Day 2, Problem 6
Tags: geometry, diameter, point set, combinatorial geometry, IMO, IMO 1965
15.10.2005 00:09
See this. There's a proof there that if we give our set of points a graph structure by connecting two vertices iff the distance between them is the diameter, then this graph has at most one cycle. Every graph on $n$ vertices with $\ge n+1$ edges, on the other hand, has at least $2$ cycles, so we're done.
17.12.2013 03:51
Alternatively, in the graph where two points are connected if and only if they have a diameter, it is not hard to see that any two edges must intersect because otherwise a segment with length over $d$ could be formed. Then we go by induction. For $n=3$ it is trivial, and we can assume no vertices have degree under $2$, lest we cut them out and reduce it to the $n-1$ case. If $A$ has $3$ neighbors in this graph $B$, $C$, $D$, with $C$ is the middle (surely $B$, $C$, $D$ lie in some $60$ degree angle), then it is impossible to have an edge with an endpoint at $C$ that meets both $AB$ and $AD$, contradiction. So we can assume all vertices have degree at most $2$ and then we get the desired result.
10.11.2020 02:15
Iam really stuck in this problem , Can anyone expalain it simply, please ?
29.07.2024 18:21
Here's my attempt at the problem. We proceed by induction for $n \geq 3$. The base case when $n=3$ is obvious. For the inductive step, suppose that there exists an $n \geq 4$ such that for every set of $n-1$ points in the plane, the number of diagonals is less than or equal to $n-1$. Now consider $n$ points in the plane. We claim that the number of diagonals is less than or equal to $n$. Suppose for the sake of contradiction that the claim is false, ie., there exist at least $n+1$ diagonals, with length $d$. Translate the set of points and diagonals to the graph $G=(V,E)$, where $V$ and $E$ is the set of vertices and edges respectively, such that point in the plane is a vertex and every diagonal is an edge in $G$. Hence $|E| \geq n+1$. Claim 1. For every $v \in V$ we have $\deg v \geq 2$. Proof. Assume the contrary, ie., there exist a veretx $v \in V$ with $\deg v \leq 1$. Removing $v$, we get a new graph with $n-1$ vertices and $n$ edges. This contradicts our assumption in the inductive step. This contradiction proves our first claim. Claim 2. In fact, there is a $v \in V$ such that $\deg v \geq 3$. Proof. Suppose for the sake of contradiction that for every $v \in V$ we have $\deg v \leq 2$. Applying the well-known Handshaking Lemma we have that $$ 2(n+1) \leq 2|E| = \sum_{v \in V} \deg v \leq 2n,$$contradiction! Again, this contradiction proves our second claim. Finish. We are now ready to use our results to finish the inductive step. Translate the problem back to Euclidean geometry. By our second claim, we know the existence of a point $O$, a circle centred at $O$ and of radius $d$, and three points $A$, $B$ and $C$ on this circle. By the law of cosines, we can deduce that the angle between every pair of lines $\overline{OA}$, $\overline{OB}$ and $\overline{OC}$ has to be less than or equal to $60^{\circ}$. This means that the points $A$, $B$ and $C$ must lie in the interior of an angle of $60^{\circ}$. Without loss of generality, assume that $B$ lies inside $\angle AOC \leq 60^{\circ}$. By our first claim, there must exist a second point $D$ such that $BD=d$. But $D \notin \{A,C\}$ because $AB<d$ and $BC < d$. Now, segment $BD$ must intersect exactly one of the segments $OA$ and $OC$. Without loss of generality, assume that $BD$ intersect $OC$. Then $AD$ must intersect $OB$ at some point, $Q$ say. But by the triangle inequality, $$OB + AD = (OQ + QB) + (AQ + QD) = (AQ + QO) + (BQ + QD) >OA + BD = 2d,$$and since $OB=d$ we have $AD>d$, contradiction the definition of $d$. This contradiction finishes our inductive step. Hence we are done by the principle of induction.