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 4 of 5: Apply the pigeonhole principle

Previous step Next step

In plain words

One line now carries three points from $S$ .

\exists\{A_0,B_0\}\text{ with at least 3 points of }S\text{ on its perpendicular bisector}

Detailed analysis

Since the average exceeds $2$ , some pair $\{A_0,B_0\}$ is witnessed by at least three distinct points $P\in S$ . Every such $P$ lies on the single perpendicular bisector of $A_0B_0$ .