1000 points with distinct pairwise distances

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

12 users

TOPICS

No tags match your search

M

No tags match your search

M

1000 points with distinct pairwise distances

G H J

Reveal topic tags

pigeonhole principle

perpendicular bisector

binomial theorem

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran 3rd round 2012-Special Lesson exam-Part1-P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

#1 h Jul 27, 2012, 2:42 AM • 5 Y

Y by Amir Hossein, hadikh, mahanmath, Adventure10, and 1 other user

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$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hyperbolictangent

961 posts

hyperbolictangent

#2 h Dec 20, 2012, 5:30 AM • 3 Y

Y by math114, Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

147 posts

#3 h May 30, 2025, 11:57 AM

Y by

First Part: The key lemma is the following:

Lemma: Given a fixed integer $k$ and a fixed circle $C$ is a fixed circle, then given sufficiently many points on $C$ , there exist $k$ points with pairwise distinct distances.
Proof of lemma: Induct on $k$ , with base cases being easy to check. Say we need $N$ points to get $k$ points with pairwise distinct distances. Now say we have some number $N'>>>N$ points. Take $N$ points from these and choose the $k$ points that give pairwise distinct distances. From the $\binom{k}{2}$ distances that these form, consider the set of points on $C$ that are one of these $\binom{k}{2}$ distances away from atleast one of the $k$ points. Its not so hard to see that this number is finite, so after adding the $N'-N$ new points for a sufficiently large $N$ , we get that some new point is not one of these points of which I established a finite number. Choosing a point like this finishes.

To finish, we use an approach similar to the proof of the lemma. Replace 1000 by $k$ and induct on $k$ . Base cases are not so hard. Say we have $N$ such that any $N$ points give $k$ with pairwise distinct distances. Take some $X>>N$ points, and consider $N$ out of the $X$ points. Take the $k$ points from these with pairwise distinct distances by induction hypothesis, say $p_1, p_2,\dots, p_k$ .

From these $k$ points, consider the $\binom{k}{2}$ possible distances, $d_1,d_2,\dots , d_k$ , and draw $\binom{k}{2}$ circles at each of the $k$ points with this radius. Now from our $X-N$ remaining points, if any of these points are not on any of these circles, we get $k+1$ points with pairwise distinct distances. Otherwise, all the $X-N$ remaining points lie on one of these circles so if $X$ is sufficiently large, we get there are sufficiently many points on one of these circles to apply our lemma. This finishes $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a