Problem 3

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. Suppose that for every point

P\in S

there are at least

k

points of

S

equidistant from

P

. Prove that

k<\frac12+\sqrt{2n}

Step 3 of 5: Compare with all unordered pairs

Previous step Next step

In plain words

There are only finitely many pair-lines available, so excess incidences must concentrate somewhere.

N>n(n-1)=2\binom n2

Detailed analysis

Combining Steps 1 and 2 yields $N>n(n-1)$ . But there are only $\binom n2$ unordered pairs $\{A,B\}$ in $S$ . Therefore the average number of points $P$ whose perpendicular-bisector incidence is attached to one pair exceeds $2$ .