We have $n$ points in a plane. Show that there is at least $\lfloor {\sqrt{n\over 2}} \rfloor $ different distances between them.

Question

We have $n$ points in a plane. Show that there are at least $\lfloor \sqrt{n\over 2} \rfloor $ different distances between them.

Answer 1

I won't worry about floors. You can if you want.

Suppose otherwise. Let $m = \sqrt{n/2}- 1$. Fix any point $P$ in the collection. Then there are at most $m$ distances from other points to $P$, say $d_1,\dots,d_{m'}$, $m' \le m$. I.e., all other points lie on a circle of radius $d_1,\dots,d_{m'-1}$, or $d_{m'}$ centered at $P$. By pigeonhole, there is some $j \in \{1,\dots,m'\}$ such that there are at least $\frac{n-1}{m'} \ge \frac{n-1}{m} \ge \sqrt{2n}$ points on the circle of radius $d_j$. Take any point $Q$ on that circle. Then each distance $|Q-Q'|$ for $Q'$ on that circle is repeated at most once (i.e. it appears at most twice), so we get at least $\frac{1}{2}\sqrt{2n} = \sqrt{n/2}$ distances.