Let $S$ be a set of 1980 points in the plane such that the distance between every pair of them is at least 1. Prove that $S$ has a subset of 220 points such that the distance between every pair of them is at least $\sqrt{3}.$
Problem
Source: IMO 1980 Austria-Poland, problem 8
Tags: induction, combinatorial geometry, geometry, euclidean distance, IMO Shortlist
09.05.2004 13:57
Ok...it is a very nice problem. After spending almost three years on a graph theoretic approach, i've finally seen that $1980 = 9 \times 220$. It leads me to the idea that we may group the points by $9$ and choose one in each group. But after 2 more years I've seen that the number of points which can be contained in a disk with radius $ \sqrt3$ with one as the center and with mutual distances at least $1$ is more that 9....(aaargh). But now, i've got a solution : We will prove by induction on $k$ that for each set of $9k$ points in the plane with mutual distances at least $1$, we may select a subset of $k$ points with mutual distances at least $ \sqrt3$. - The result is easy for $k=1$, so let's assume it holds for a given $k \geq 1$. Let's consider a set $S$ of $9k+9$ points of the plane with mutual distances at least $1$. Let $C$ be the convex hull of $S$. Let $A$ ve a vertex of $C$. Let $A_1,...,A_8$ be the nearest points of $S$ from $A$. Suppose, for a contradiction, that each of the $A_i$'s are in the disk of center $A$ and radius $ \sqrt 3$. Since $A$ is a vertex of the convex hull, it follows that each of the $A_i$'s are in the same half-disk (that's the point....). Now divides the disk into seven equal angular sectors from $A$ (thus with angle $ \frac {\pi} {7}$). Then from the pigeon-hole principle, at least two of the $A_i$'s are in the same sector, say $A_1$ and $A_2$. Since $AA_1$ and $AA_2$ are not less than $1$, it follows that $A_1$ and $A_2$ are in the common part of the annulus with radii $1$ and $ \sqrt 3$ and the angular sector. It is not difficult to verify that the distance $A_1A_2$ is then less than or equal to the maximum distance between two of the 'vertices' of that common region, which is in turn less than $1$. This contradicts that $A_1A_2 \geq 1$. Thus, at least one of the $A_i$ is such that $AA_i > \sqrt3$. Since these points are the nearest from $A$, it follows that each other points of $S$ is at distance more than $ \sqrt3$ from $A$. Now select a set of $k$ points from $S \setminus \{A,A_1,...,A_8 \}$ with pairwise distances at least $ \sqrt3$ as given by the induction hypothesis and add $A$, it will leads to the desired set with $k+1$ elements, and we are done.... Pierre.