IMO 1989/A3 solution

IMO 1989

Problem A3

Let n and k be positive integers, and let S be a set of n points in the plane such that no three points of S are collinear, and for any point P of S there are at least k points of S equidistant from P. Prove that k < 1/2 + √(2n).

Solution

Three variants on a theme, all kindly supplied by others (I spent 2 hours failing to solve it). My favorite first.

By Eli Bachmutsky

Consider the pairs P, {A, B}, where P, A, B are points of S, and P lies on the perpendicular bisector of AB. There are at least n k(k - 1)/2 such pairs, because for each point P, there are at least k points equidistant from P and hence at least k(k - 1)/2 pairs of points equidistant from P.

If k ≥ 1/2 + √(2n), then k(k - 1) ≥ 2n - 1/4 > 2(n - 1), and so there are more than n(n - 1) pairs P, {A, B}. But there are only n(n - 1)/2 possible pairs {A, B}, so for some {A₀, B₀} we must be able to find at least 3 points P on the perpendicular bisector of A₀B₀. But these points are collinear, contradicting the assumption in the question.

From an anonymous source

Let the points be P₁, P₂, ... , P_n. Let C_i be a circle center P_i containing at least k points of S. There are at least nk pairs (C_i,P_j), where P_j lies on C_i. Hence there must a point P lying on at least k circles. Take k such circles C_α. For each such circle C_α, take a subset S_α comprising exactly k points of S ∩ C_α.

We now count the points in ∪ S_α. Apart from P, there are k-1 points in each S_α. So we start with 1 + k(k-1). But this counts some points more than once. Each pair (S_α, S_β) (with α ≠ β) has at most one common point apart from P (because distinct circles have at most two common points). So we deduct 1 for each of the 1/2 k(k - 1) pairs (S_α, S_β), giving 1 + k(k - 1) - 1/2 k(k - 1) (*).

If Q (≠ P) is in exactly r sets S_α, then it is counted r times in the second term k(k - 1), and subtracted 1/2 r(r - 1) times in the third term. So it is counted 1/2 r(3 - r) times in all. That is correct for r = 0, 1 or 2 and too low for r > 2. So (*) is ≤ |∪ S_α|. Clearly |∪ S_α| ≤ n, so n ≥ 1 + k(k - 1)/2 = (k - 1/2)²/2 + 7/8 > (k - 1/2)²/2. Hence √(2n) + 1/2 > k.

By Thomas Jäger

Define P_i and S_i as above. Let g(i) be the number of S_a containing P_i, and let f(i, j) be |S_i ∩ S_j|. Let h(x) = x(x - 1)/2. We count the number N of pairs i, {a, b}, where point i is in S_a and S_b.

Point i is in g(i) sets S_j, from which we can choose S_a,S_b in h(g(i)) ways. Hence N = ∑ h(g(i)). But f(a, b) points are in S_a and S_b, so N = ∑ f(a, b). But, since distinct circles intersect in at most 2 points, f(a, b) ≤ 2, so ∑ f(a, b) ≤ h(n) 2. We conclude that 2 h(n) ≥ ∑ h(g(i)).

h is a convex function, so 1/n ∑ h(g(i)) ≥ h(1/n ∑ g(i)) = n h(1/n nk) = n h(k). Hence n - 1 ≥ h(k), which gives the result, as above.

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

30th IMO 1989