8

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

mathworker21
  • 34,399
nonuser
  • 90,026

1 Answers1

6

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.

mathworker21
  • 34,399
  • 1
    I think that considering floor in this case is actually trivial-- all it does is to guarantee that the number of distances is an integer. – Hello Apr 03 '20 at 10:18
  • @ONGSEEHAIHCI huh? you need to work with inequalities throughout the proof. $\frac{n-1}{m} \ge \sqrt{2n}$, etc., which become more annoying. – mathworker21 Apr 03 '20 at 10:23
  • oh, I see what you mean now. – Hello Apr 03 '20 at 10:25
  • But isn't it obvious that the result you have is stronger? Especially because: \begin{equation} \lfloor \sqrt{\frac{n}{2}} \rfloor \leq \sqrt{\frac{n}{2}} \end{equation} – Hello Apr 03 '20 at 10:36
  • Where we have equality iff $n$ is an even integer. – Hello Apr 03 '20 at 10:36
  • @ONGSEEHAIHCI you're wrong about many, many things. I did not prove the number of distances is at least $\sqrt{n/2}$, since I started by assuming the number of distances is at most $\sqrt{n/2}-1$ (if $\sqrt{n/2} = 2.43\dots$, then there could be $2$ distances, which would be less). You have to work through my proof correctly if you want a valid proof of what Aqua asked for (I'm just lazy). Also, it's not true that $\lfloor \sqrt{n/2} \rfloor = \sqrt{n/2}$ if $n$ is an integer. – mathworker21 Apr 03 '20 at 10:39
  • What's wrong with having $2$ distances? The floor of $2.43...$ returns $2$, right? Anyways the number of distances must always be discrete. – Hello Apr 03 '20 at 10:54
  • you should take some time to think about my comments. I don't mean to be rude, but I don't want to continue this conversation – mathworker21 Apr 03 '20 at 10:55
  • No problem at all! – Hello Apr 03 '20 at 10:59
  • 1
    On an unrelated note, upon reading your solution again, I think it is necessary to consider floor in the first place, else from the way $m$ is defined, it is not necessarily an integer? – Hello Apr 03 '20 at 11:34