Given n points in the plane, prove that less than 2n^{3/2} pairs of points are a distance 1 apart.

**Solution**

Label the points 1, 2, ... , n. Let n_{i} be the number of points a distance 1 from point i. We wish to show that ∑ n_{i} < 4 n^{3/2}. We can assume that all n_{i} ≥ 2. [Keep removing points until those that are left have n_{i} ≥ 2. If we exhaust the points before this happens then the number of pairs ≤ n < 2n^{3/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} < 2n^{3/2}.

The points a distance 1 from point i must all lie on C_{i} 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 n_{i} circles through it, so it arises as a point of intersection in 1/2 n_{i}(n_{i} - 1) ways. Thus all the points together give rise to ∑ 1/2 n_{i}(n_{i} - 1) points of intersection. Hence ∑ n_{i}(n_{i} - 1) ≤ 2n(n - 1). Since n_{i} ≥ 2, n_{i} ≤ 2(n_{i} - 1), so we have that ∑ n_{i}^{2} ≤ 2 ∑ n_{i}(n_{i} - 1) ≤ 4n(n - 1) < 4n^{2}. Now Cauchy's inequality gives that n ∑ n_{i}^{2} ≥ (∑ n_{i})^{2}. So ∑ n_{i} < 2 n^{3/2}.

© John Scholes

jscholes@kalva.demon.co.uk

30 Nov 1999