Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it possible to select 1000 points in a plane so that at least 6000 distances between two of them are equal?

How to even start with this? I have no clue. any help?

share|cite|improve this question
I often misinterpret questions, so let me ask: would putting the points along a circle K, centered at (x,y) and one point in the center (x,y) of the circle be allowed? – gary Sep 13 '11 at 11:09
up vote 1 down vote accepted

A search for the Erdos distance problem will bring up many discussions of this question, for example, Wikipedia.

share|cite|improve this answer

My guess is that it is not possible. Taking the most regular pattern with equilateral triangles, you get only $3+2(n-3)$ equal distances, which gives 1997 for 1000 points. While I am not able to prove it, more complicated patterns intuitively yield less than 2 points for one point added (in average), so equilateral triangles maximizes the number of equal distances.

(I suppose you mean that 6000 distances are all the same, not that there is 6000 couples of distances which are equal, but not necessarily all the same.)

share|cite|improve this answer
It seems to me that the triangular lattice should get you close to $3n$, not $2n$, as most of the points have degree 6 (so there are nearly $3n$ edges). – Gerry Myerson Sep 13 '11 at 9:19
I started with equilateral triangle, which has 3 same distances; each additional lattice point added somewhere at the boundary adds two more edges, so in total $3+2(n-3)$. Why do you think it is $3n$? – eudoxos Sep 13 '11 at 11:01
If you actually carry out that procedure, you will find that sometimes an additional lattice point adds three more edges; moreover, as the configuration grows, three becomes the rule, two, the exception. – Gerry Myerson Sep 13 '11 at 13:07
This is not optimal. As stated in the Wikipedia article Gerry linked to, the hypercube graph provides a straightforward lower bound for the maximal number of unit distances. A hypercube graph with $2^{10}=1024$ points has $5\cdot1024=5120$ unit distances, and removing $24$ points removes at most $10\cdot24=240$ of them. – joriki Sep 13 '11 at 16:18
The hypercube graph renders the question moot, but the triangular lattice lattice with $n$ points on a side has $\frac{n(n+1)}{2}$ vertices and $\frac{3n(n-1)}{2}$ edges, for a ratio of $3-\frac{6}{n+1}$. In particular, with $n=45$ there are $1035$ vertices; removing triangles of $15,10$, and $10$ vertices costs $56$ edges, leaving $2914$. – Brian M. Scott Sep 13 '11 at 18:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.