Given n points in the plane, prove that less than 2n3/2 pairs of points are a distance 1 apart.
Solution
Label the points 1, 2, ... , n. Let ni be the number of points a distance 1 from point i. We wish to show that ∑ ni < 4 n3/2. We can assume that all ni ≥ 2. [Keep removing points until those that are left have ni ≥ 2. If we exhaust the points before this happens then the number of pairs ≤ n < 2n3/2. Otherwise, suppose we remove k points. Then the result follows from the result for n - k points since k + 2(n - k)3/2 < 2n3/2.
The points a distance 1 from point i must all lie on Ci the circle radius 1, center point i. Each pair of circles meets in 0, 1 or 2 points. So the total number of points of intersection of two circles is at most n(n - 1) (where a point of intersection arises in more than one way we count one for each way it arises). Some of these points of intersection will be members of the original set of n points. Point i has ni circles through it, so it arises as a point of intersection in 1/2 ni(ni - 1) ways. Thus all the points together give rise to ∑ 1/2 ni(ni - 1) points of intersection. Hence ∑ ni(ni - 1) ≤ 2n(n - 1). Since ni ≥ 2, ni ≤ 2(ni - 1), so we have that ∑ ni2 ≤ 2 ∑ ni(ni - 1) ≤ 4n(n - 1) < 4n2. Now Cauchy's inequality gives that n ∑ ni2 ≥ (∑ ni)2. So ∑ ni < 2 n3/2.
© John Scholes
jscholes@kalva.demon.co.uk
30 Nov 1999