2
$\begingroup$

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?

  • 0
    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?2011-09-13

2 Answers 2

1

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

0

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.)

  • 0
    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$.2011-09-13