Prove that if $n$ is large enough, among any $n$ points of plane we can find $1000$ points such that these $1000$ points have pairwise distinct distances. Can you prove the assertion for $n^{\alpha}$ where $\alpha$ is a positive real number instead of $1000$?
Problem
Source: Iran 3rd round 2012-Special Lesson exam-Part1-P3
Tags: induction, pigeonhole principle, geometry, perpendicular bisector, algebra, binomial theorem, combinatorics proposed
20.12.2012 07:30
First, we prove a lemma. Lemma : Suppose $n$ is a fixed positive integer, and $\mathcal{C}$ is a fixed circle. Given sufficiently many points on $\mathcal{C}$, there exists a set $S$ containing $n$ of them such that all pairwise distances between the elements of $S$ are distinct. Proof. We use induction. For $n = 2$ the conclusion is obvious. Suppose we have chosen a set $S$ of $k$ points on $\mathcal{C}$ such that all pairwise distances between them are distinct. Let $D = \{d_1, d_2, \dots, d_{\binom{k}{2}}\}$ be the set of distinct distances. Call a point forbidden if it is not in $S$ but either i) its distance to some member of $S$ is in $D$ or ii) it is equidistant from two members of $S$. All we need to do is show that there are finitely many forbidden points, from which it follows we can add finitely many points and be guaranteed a new point to include in $S$. The number of points that are at distance $d_i$ from some member of $S$ is at most $2k_kC_2$, since for each $d_i$ and each point among the $k$ chosen on $\mathcal{C}$, there are at most two other points on $\mathcal{C}$ at distance $d_i$ from that point and we can sum over all points and distances. The number of points equidistant from two members of $S$ is at most $2(_kC_2)$ since for each pair of points in $S$, their perpendicular bisector intersects $\mathcal{C}$ in at most $2$ new points. Then the number of forbidden points is finite, as desired. $\blacksquare$ Returning to the original problem, we will prove (once again by induction) that for a fixed $T$ and an $n$ sufficiently large, among any $n$ points in the plane we can find a set $S$ containing $T$ of them such that the pairwise distances between the members of $S$ are distinct. Again, the base case $T = 2$ is trivial, so suppose the result holds for $T = k$. By hypothesis, there are exactly $_kC_2$ distinct distances between the $k$ points in $S$; let them be $d_1, d_2, \dots, d_{\binom{k}{2}}$. For all $1 \le i \le _kC_2$ and all points $P$ in $S$, draw a circle of radius $d_i$ centered at $P$. Go on adding points: if some point is not on one of these circles, it's distance to each of the elements of $S$ is new, so we can safely add it. Otherwise, all points we add are on one of these circles; since there are finitely many circles, by Pigeonhole principle some particular circle contains as many added points as we like. We can simply take enough that there are $k + 1$ points on that circle with all their pairwise distances distinct (which is guaranteed by the Lemma), and we are done. In fact, we can improve this bound to $n^{\alpha}$ if $\alpha$ is small enough. Suppose we have chosen $k$ valid points out of the $n$ to include in $S$. Running the above argument in reverse, if we add at least \[(x - 1)k\binom{k}{2} + 1\] new points, we are guaranteed that $x$ lie on some circle. If we take $x = 2k_kC_2 + 2_kC_2 + 1$, the first half of our argument assures us that there are $k + 1$ points with all their pairwise distances distinct. Then by adding at most \[(2k\binom{k}{2} + 2\binom{k}{2})k\binom{k}{2} + 1 < k^6\] points we can guarantee the possibility of adding a new point to $S$. Replacing $k$ with $n^{\alpha}$, we need \[n + n^{6\alpha} \le (n^{\alpha} + 1)^{\frac{1}{\alpha}}\] Approximating $\alpha$ with $1/r$, \[(n + n^{\frac{6}{r}}) \le (n^{\frac{1}{r}} + 1)^r\] which by the binomial theorem holds for $r \ge 7$, or $\alpha \le 1/7$