Let S be a set of n points in the plane such that the greatest distance between two points of S is 1. Show that at most n pairs of points of S are a distance 1 apart.
Solution
Induction on n. Obviously true for n ≤ 3. Suppose it is true for n. Take n+1 points. If no point is a distance 1 from more than 2 points, then we are done. So assume that A, B and C are all a distance 1 from P. wlog the largest of the three angles APB, APC, BPC is APB. It must be at most 60o, since AB ≤ 1. So the ray PC lies between the rays PA and PB.
Now suppose there is another point D (apart from P) such that CD = 1. Then CD must intersect PA, because otherwise one of CP, CA, DP and DA would exceed 1. Similarly, it must intersect PB. But that is impossible. So there is no such point D. Hence if we remove C we lose only one realisation of the distance 1. But the remaining n points have at most n realisations, so the result is established.
© John Scholes
jscholes@kalva.demon.co.uk
25 Feb 2002