I still remember how unbelievably happy I was when I managed to solve this one a very long time ago . Let $\{A_i\}_{i=1}^n$ be our set of points. We count the pairs $(A_i,\{A_j,A_\ell\}),\ i\ne j\ne \ell\ne i$ such that $A_iA_j=A_iA_\ell$. There are $n$ choices for $A_i$, and for each $A_i$ there are $\ge\frac{k(k-1)}2$ choices for $\{A_j,A_\ell\}$, so the number of such pairs is $\ge\frac{nk(k-1)}2$. On the other hand, there are $\frac{n(n-1)}2$ choices for $\{A_j,A_\ell\}$, and for each $\{A_j,A_\ell\}$ there are at most two choices for $A_i$ (because we can't have $\ge 3$ points on the perpendicular bisector of $A_jA_\ell$). This means that the number of pairs is $\le n(n-1)$. We have thus found $n(n-1)\ge\frac{nk(k-1)}2\Rightarrow 2(n-1)\ge k(k-1)\ (*)$. If $k\ge \sqrt{2n}+\frac 12$, then $k(k-1)\ge 2n-\frac 14>2n-2$, contradicting the last inequality in $(*)$, so we're done.

I solved it yesterday when I was trying to sleep; two possible approaches came to my mind. First of all, I tried to get an upper bound for $k$ by counting $nk$ points (at least $k$ equidistant points for any of the $n$ points) and then subtracting $2\binom{n}{2}$, since two points may share exactly two other points, equidistant from both of them. But this yields a horrible bound for $k$, namely $k \leqslant n$, which is even worse than the obvious $k \leqslant n-1$. But this was actually not really surprising, since I haven't used the fact that no three points are collinear. So I tried to find another way of counting the $k$ equidistant points and then subtracting the possible "common" points, incorporating the fact that no three points are collinear. Due to my last observation (namely that two circles intersect in at most two points; imagine the $k$ equidistant points as a circle) I started to think of pairs of points, since this idea includes the fact that no three points are collinear (a pair of points belongs to at most two of these "circles"). The rest is the same as grobber did already more than 4 years ago. One could also visualise this by setting up an incidence matrix as follows. Let $A=(a_{i\mbox{,}j})$ be an $n\times n$ matrix, where every row and column represtents one of the $n$ points. An entry $a_{i\mbox{,}j}$ is $1$, if point $P_j$ is one of the $k$ (or more) equidistant points from $P_i$. \[\begin{pmatrix} 0 & 0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 & 0 & \cdots & 0 \\ 1 & 0 & 0 & 0 & \cdots & 1 \\ & \vdots & & & \ddots & \vdots \\ 1 & 0 & 0 & 1 & \cdots & 1 \\ 0 & 1 & 1 & 1& \cdots & 0 \end{pmatrix}\]To solve the problems, it's enough to count the pairs on $1$'s in each row in two different ways. Therefore, let $\mathcal{T}$ be the set of all unordered pairs of $1$'s that lie in the same row. Counting by rows: since there are at least $k$ equidistant points in each row, we have at least $n\binom{k}{2}$ pairs of ones in total. Hence $|\mathcal{T}| \geqslant n\binom{k}{2}$. Counting by columns: for any two columns $i$ and $j$, there are at most two pairs of $1$'s (since no three points are collinear). Thus, $|\mathcal{T}| \leqslant 2\binom{n}{2}$. The result follows.

The solution I found is just like grobber's except using expected values (since probability is more "natural" to think of in problems like these). However, the solution hinted at in the pdf attached here seems to use an approach that's only slightly different but avoids the noncollinearity condition altogether. So I'm wondering if the noncollinearity condition is used subtly in some way I'm not seeing, or if it's actually not necessary in this solution:

For comparison, here's my solution, which does use the noncollinear condition. I don't see how the first solution manages to do without it, since every inequality seems to be weaker here than there...

Maybe it's the fact that the first solution uses a (rather trivial) convexity argument (which can be explained geometrically), that the noncollinearity is given for the ease of a completely (safely) elementary solution? (Also... as a sidenote, notice how in the two solutions we basically switch the words "point" and "circle" (along with some minor changes to the basic inequalities)... combinatorial duality between circles and points... almost eerie, more strange than projective point-line duality or inversive line-circle duality.)

A very good point. To better understand what is happening here, let us first completely remove the problem from its intuitive geometrical setting, and re-state it in only terms of element/set incidence. Let $ n$ and $ k$ be positive integers, and let $ S$ be a set of $ n$ elements, such that to every element $ p$ of $ S$ there is associated a set $S_p \subseteq S\setminus \{p\}$ of at least $k$ elements. Of course this does not induce any restriction on the largest possible size of $k$, other than $k\leq n-1$. Let us make the notation $C_p = \{q \in S \mid p \in S_q\}$. The original problem introduced an extra requirement (non-collinearity $3$ by $3$), which in the course of the proof was used in the form Constraint 1. For any pair $p\neq q \in S$ we have $|C_p\cap C_q| \leq 2$. (that being because non-collinearity of any three points). However, the pure geometrical setting induces the following Constraint 2. For any pair $p\neq q \in S$ we have $|S_p\cap S_q| \leq 2$. (that being because non-identical circles meet at two points at most). This alone is also sufficient for a (similar) proof, due to the duality of the incidence relations, as shown just above. Now everything is clear. Any of the two constraints is equivalent in finding the required uper bound for $k$. The geometrical setting however fooled (?) the proposer into introducing Constraint 1., maybe because his mind was set on that proof, when Constraint 2. was in fact automatically fulfilled.

This is just an easier version of China TST 2011 #2 First consider $X$, the number of ordered triples $(P,Q,R) \in S$ where $PQ=PR$. For every pair $(Q,R)$ at most $2$ $P$'s exist by perpendicular bisector theorem. Thus, $X\le 2n(n-1)$. Now from (b), for every $P\in S$ there are at least $k(k-1)$ $(Q,R)$'s and thus $nk(k-1)\le X\le 2n(n-1) \Rightarrow k(k-1) \le 2(n-1)$. Now for the sake of contradiction suppose that $k \ge 1/2+\sqrt{2n}$. Then $(1/2+\sqrt{2n})(-1/2+\sqrt{2n})=2n-1/4 \le 2n-2$, a contradiction.

Ignore this.

Solution. We count the number of triples of the form $(center,\text{ a point on the circle}, \text{a point on the circle})$. For every center, there are at least $k$ points, so there are at least $n\binom{k}{2}$ triples. Note that for every two points on a circle there are at most $2$ points which can be the center since no three points are collinear (the two points lie on the perpendicular bisector). So there are at most $2 \binom{n}{2}$ triples. $$n\binom{k}{2}\leq 2\binom{n}{2}\implies k \leq \frac{1+\sqrt{8n-7}}{2} < \frac{1}{2}+\sqrt{2n}$$

Consider the segments joining every two points in the set $S$. Let the total number of these segments be $T$. Now clearly $T=\binom{n}{2}$. Now by the second condition we can say that for each point $P$ there at least $k$ points lying on the circumference of the circle with center $P$. Thus, we get at least $\binom{k}{2}$ segments on each circle. Now since, there are $n$ points $P$, we get that there are $n \cdot \binom{k}{2}$ segments in total, but observe that we have over counted the segments that lie on two circles. Now since, each circle can have only one chord in common and there are $n$ circles, we have over counted $\binom{n}{2}$ segments. This implies : $$ T \geq n \cdot \binom{k}{2}- \binom{n}{2} \implies \binom{n}{2} \geq n \cdot \binom{k}{2}- \binom{n}{2} \implies n \cdot \binom{k}{2} \leq 2 \cdot \binom{n}{2}$$. From this we get that : $$n(\frac{k!}{(k-2)! \cdot 2!})-2(\frac{n!}{(n-2)! \cdot 2!}) = \frac{nk(k-1)}{2}-n(n-1) \leq 0$$$$\implies nk(k-1)-2n(n-1)=n(k^2 - k - 2(n-1)) \leq 0$$$$\implies k^2 - k - 2(n-1) \leq 0$$Thus, $$k \leq \frac{1+\sqrt{1+8(n-1)}}{2}=\frac{1}{2}+\frac{\sqrt{8n-7}}{2}<\frac{1}{2}+\frac{\sqrt{8n}}{2}=\frac{1}{2}+\sqrt{2n}$$And we are done!