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 5 of 5: Contradict the no-three-collinear condition

Previous step Next step

In plain words

The contradiction closes the double count: too much equal-distance symmetry would force forbidden collinearity.

\text{Contradiction: }P_1,P_2,P_3\text{ are collinear, so }k<\frac12+\sqrt{2n}

Detailed analysis

The three witnessing points on one perpendicular bisector are collinear, contradicting the hypothesis that no three points of $S$ are collinear. Thus the contrary assumption is impossible, and $k<\frac12+\sqrt{2n}$ .