IMO 1989 · Problem 3

Let \(n\) and \(k\) be positive integers and let \(S\) be a set of \(n\) points in the plane such that

(i) No three points of \(S\) are collinear, and

(ii) For any point \(P\) of \(S\) there are at least \(k\) points of \(S\) equidistant from \(P\).

Prove that: \[ k<\frac12+\sqrt{2n}. \]

Official text of the problem. Official problem paper (PDF)

Solution

If \(k=1\), the required inequality follows immediately from \(n\ge1\). Hence assume \(k\ge2\).

Count the configurations \((P,\{Q,R\})\), where \(P,Q,R\) are distinct points of \(S\), the pair \(\{Q,R\}\) is unordered, and \[ PQ=PR. \] Let their number be \(N\).

For every \(P\in S\), there are at least \(k\) distinct points at a common distance from \(P\). This distance is positive because \(k\ge2\), so none of these points is \(P\). Each pair among them gives a configuration. Consequently, \[ N\ge n\binom{k}{2}. \]

On the other hand, fix an unordered pair \(\{Q,R\}\subset S\). Every point \(P\) satisfying \(PQ=PR\) lies on the perpendicular bisector of \(QR\). By condition (i), this line contains at most two points of \(S\). Thus each pair \(\{Q,R\}\) occurs in at most two configurations, giving \[ N\le2\binom{n}{2}. \]

Combining these inequalities and dividing by \(n>0\), we obtain \[ \frac{k(k-1)}2\le n-1. \] Therefore \[ \left(k-\frac12\right)^2 =k(k-1)+\frac14 \le2n-\frac74 <2n. \] Since \(k-\frac12>0\), taking square roots yields \[ \boxed{k<\frac12+\sqrt{2n}}. \]

The solution was checked against John Scholes' IMO solution archive (Kalva).