2
$\begingroup$

There are $N>1$ points in a plane. Consider the set of all distances between pairs of the points. Let $n$ be the number of elements of this set. We know that $$n \leq {N \choose 2}.$$ What is the lower bound estimate on $n$?

For the sake of clearity, if points are $A_1, A_2, \dots, A_N$, and $S = \{d(A_i, A_j)| 1\leq i < j \leq N \}$, then $n = |S|$.

  • 1
    -1: This looks like another olympiad question. It is not clear that you have put any thought into this or truly care about the answer. Please see [this meta thread](http://meta.math.stackexchange.com/questions/548/dealing-with-many-poorly-motivated-questions-from-a-single-user) and [this one](http://meta.math.stackexchange.com/questions/191/dissonance-of-purpose-what-kind-of-site-should-mu-be) and reconsider your question(s).2010-08-12
  • 0
    @Tom Stephens: Falagar's answer is exactly what I needed. I have managed to get only $n \geq \sqrt{N}-1$. I don't understand your negativity.2010-08-12
  • 1
    This is a beautiful _unsolved_ problem. Why the -1?2010-08-12
  • 0
    Fair enough, but what has the asker done in this direction? Further, the question is posed in the style of "Prove..."/"Solve..."/etc, and it is not the first one. Considering the rash of these questions recently, I am compelled to respond with the helpful suggestion to see [this meta thread](http://meta.math.stackexchange.com/questions/548/dealing-with-many-poorly-motivated-questions-from-a-single-user) and [this one](http://meta.math.stackexchange.com/questions/191/dissonance-of-purpose-what-kind-of-site-should-mu-be), and to reconsider the question.2010-08-12
  • 0
    @Tom Stephens: I really don't see a problem. Question aligns with both FAQ and a lot of comments in threads you linked to. Few comments above I wrote what I 'have done in this direction', but I don't see why I need to have _some_ decent result to be interested in an answer. I am passionate about math and were thrilled about this side, but this kind of comments make it elitist place and turn people off. Maybe for some people I'm not the audience for this site, but it didn't feel that way after reading what this site should be.2010-08-12
  • 0
    @n0vakovic and the community: I am backing off of this entire issue. Each of the contributions to the site that I have pointed out are indeed interesting pieces of math - I respectfully disagree with n0vakovic but it is not up to me to decide what does or does not belong here.2010-08-12

1 Answers 1

6

You might want to read this article.

The abstract of this article says:

A classical problem in combinatorial geometry is that of determining the minimum number $f(n)$ of different distances determined by $n$ points in the Euclidean plane. In 1952, L. Moser proved that $f(n) > \frac{n^{2/3}}{2\cdot3^{1/3}} - 1$ and this has remained for 30 years as the best lower bound known for f(n). It is shown that $f(n) > cn^{5/7}$ for some fixed constant c.