6
$\begingroup$

Let n distinct points in the plane be given.prove that fewer than $2n^\frac{3}{2}$ pairs of them are at unit distance apart

  • 1
    Discussion of past Putnam problems may be found at: http://www.artofproblemsolving.com/Forum/viewforum.php?f=802011-07-20
  • 0
    The more interesting question is in $m$ dimensions instead of the plane.2011-07-20
  • 0
    @GEdgar-How am i able to find it if i don't know which problem it is?2011-07-20
  • 0
    @Victor: It is A-6, 1978.2011-07-20
  • 0
    Eric, in my view the planar question is the most interesting2011-07-21

1 Answers 1

7

There is a rich history for this problem.

Let $U(n)$ denote the number of times a given distance can occur for $n$ points in the plane. In 1946 Erdos showed that $$n^{1+\frac{c}{\log \log n}} (Notice the upper bound is what you want to prove) Erdos also conjectured that the upper bound should have the same form as the lower bound.

Szemeredi improved the upper bound to $o\left(n^\frac{3}{2}\right)$ in 1975, and in 1982 Beck and Spencer gave the upper bound of $n^{1.499}$.

The best known result is $U(n) which was done by Spencer Szemeredi and Trotter in 1984.

The link to Erdos paper contains a proof of the question you are asking.

Edit: Here is the more accessible (not JStor) link to Erdos Paper, provided by Aryabhata)

  • 1
    A more recent result (I haven't read it, though): http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/2011-07-20
  • 3
    This link to the Erdos paper might be better: http://www.renyi.hu/~p_erdos/1946-03.pdf2011-07-20
  • 0
    @Aryabhata: Thanks, I just wrote the wrong thing at the top (not sure why), all the references are correct.2011-07-20
  • 0
    @Aryabhata: It does give the theorem two (on the next page). I get the document through my University's subscription so I forget that JStor can be annoying. Your link is definitely better, I'll edit the answer.2011-07-20
  • 1
    A more relevant blog post with the bound n^{4/3} is here http://gilkalai.wordpress.com/2008/07/17/extermal-combinatorics-ii-some-geometry-and-number-theory/2011-07-21