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 2 of 5: Assume the contrary bound

Previous step Next step

In plain words

The proposed upper bound would make each center generate too many pair-witnesses.

k\ge\frac12+\sqrt{2n}\ \Longrightarrow\ k(k-1)\ge2n-\frac14>2(n-1)

Detailed analysis

Assume, for contradiction, that $k\ge\frac12+\sqrt{2n}$ . Squaring $(k-\frac12)^2\ge2n$ gives $k^2-k\ge2n-\frac14$ , and since $n\ge1$ , this is strictly larger than $2(n-1)$ .