IMO 1989 SL 20

Origin: NET

Problem

Given a set S in the plane containing n points and satis- fying the conditions: (i) no three points of S are collinear, (ii) for every point P of S there exist at least k points in S that have the same distance to P, prove that the following inequality holds: k < 1 2 + \sqrt 2n.

Solution

Suppose k \geq1/2 + \sqrt 2n. Consider a point P in S. There are at least k points in S having all the same distance to P, so there are at least
k  pairs of points A, B with AP = BP. Since this is true for every point P \inS, there are at least n
k  triples of points (A, B, P) for which AP = BP holds. However, n k  = nk(k −1) \geqn \sqrt 2n + 1  \sqrt 2n −1  = n  2n −1 

n(n −1) = 2 n  . Since
n  is the number of all possible pairs (A, B) with A, B \inS, there must exist a pair of points A, B with more than two points Pi such that APi = BPi. These points Pi are collinear (they lie on the perpendicular bisector of AB), contradicting condition (1).