k punten op gelijke afstand van iedere A

Zij $S=\{P_1,\dots,P_n\}$. Voor elke $1 \le i \le n$, zij $C_i$ een cirkel met middelpunt $P_i$ met $b_i \ge k$ punten van $S$ erop en $a_i=$ het aantal cirkels $C_j$ met punt $P_i$ erop. Het is duidelijk dat $\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^nb_i$ (het beroemde dubbeltellen). Aangezien er minstens $k$ punten op gelijke afstand van elke $P_i$ liggen, is $\sum\limits_{i=1}^nb_i\geq kn$ en bijgevolg is ook $\sum\limits_{i=1}^na_i \geq kn$ (noem dit $(1)$).

Zij $M$ de verzameling van alle drietallen $\{P_i,C_j,C_t\}$ met $j\neq t$ waarbij $P_i$ een snijpunt is van cirkels $C_j$ en $C_t$. Aangezien twee cirkels met een verschillend middelpunt op hoogstens twee punten snijden is $|M|\leq2\frac{n!}{2!(n-2)!}=n(n-1)$ (noem dit $(2)$).

Nu is ook duidelijk dat $|M|=\sum\limits_{i=1}^n\frac{a_i!}{2!(a_i-2)!}=\frac{1}{2}\cdot\sum\limits_{i=1}^na_i^2-\frac{1}{2}\cdot\sum\limits_{i=1}^na_i$. Vanwege de ongelijkheid van Cauchy-Schwarz is nu
\begin{align*}
|M|
&\geq\frac{1}{2}\cdot\frac{\Bigg(\sum\limits_{i=1}^na_i\Bigg)^2}{n}-\frac{1}{2}\cdot\sum\limits_{i=1}^na_i \\
\end{align*}
Uit $(1)$ volgt nu dat
\begin{align*}
|M|&\geq\frac{(kn)^2}{2n}-\frac{kn}{2} \\
&\geq\frac{k^2n-kn}{2} \\
\end{align*}
Waneer we dit combineren met $(2)$, krijgen we $n(n-1)\geq\frac{k^2n-kn}{2}$ ofwel $nk^2-nk+2n-2n^2\leq0$. Dit geeft de volgende oplossing
\begin{align*}
k&\leq\frac{n+\sqrt{n^2-4n(2n-2n^2)}}{2n} \\
&\leq\frac{n+\sqrt{8n^3-7n^2}}{2n} \\
&\leq\frac{1+2\sqrt{2n-\frac{7}{4}}}{2} \\
&<\frac{1}{2}+\sqrt{2n} \\
\end{align*}
Dit bewijst het gevraagde.