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 1 of 5: Count incidences from each center

Previous step Next step

In plain words

Every pair of equal-radius neighbors supplies one perpendicular-bisector witness.

N\ge n\binom{k}{2}=\frac{nk(k-1)}2

Detailed analysis

For each $P\in S$ , select $k$ points at the common distance from $P$ . Any two selected points $A,B$ satisfy $PA=PB$ , so $P$ lies on the perpendicular bisector of $AB$ . Thus $P$ contributes at least $\binom{k}{2}$ incidences $(P,\{A,B\})$ , and over all $n$ points $N\ge n\binom{k}{2}=\frac{nk(k-1)}2$ .