Suppose there are $2019$ distinct points in a plane and the distances between pairs of them attain $k$ different values. Prove that $k$ is at least $44$.
Problem
Source: 2020HKTST2 Q2
Tags: combinatorial geometry, combinatorics
26.10.2019 14:33
Hopefully this makes sense. The result follows from the following: if there are $k$ different distance values, there are at most $k^2 + 2$ points. We now prove this. Using Cartesian coordinates, let $A$ be the point with the lowest $y$, and $B$ the point such that the anti-clockwise angle $\vec{AB}$ makes with the $x$-axis is minimized. Then, for any distances $x$ and $y$, there can exist at most one point which is $x$ away from $A$ and $y$ away from $B$. This is because the circle with radius $x$ and center $A$ and the circle with radius $y$ and center $B$ meet at most twice, and one of these intersection points is either below $A$ or makes a smaller angle than $\vec{AB}$ with the $x$-axis and so can't be part of the point set. But there are only $k^2$ such pairs $(x,y)$ and so at most $k^2$ other points.
22.01.2020 09:52
There is a generalisation of this problem by P. Erdos. Lemma:Among any $n$ points in the plane there is at least $(n-(3/4))^{1/2}-1/2$ distinct distances . proof.Suppose $A_1$ is a point in the convex hull and $K$ be the number of distinct distances among the segments $A_1A_i$ $i=2,3,...n$ and $N$ be the maximum number of times same distance occurs so $KN\ge n-1$ Now as this $N$ points are on a semicircle centre at $A_1$[As $A_1$ is a Pont on convex hull] Let this points are $Q_1,Q_2,..Q_N$ in this order.So $Q_1Q_2<Q_1Q_3<...<Q_1Q_N$. So at least $N-1$ distinct distances. So if $f(n)$ denote the number of distinct distances among the $n$ points then $f(n)\ge max{(n-1)/N,N-1}$. It is minimum when $N(N-1)=n-1$ Solvig the equation for $N$ we get the required inequality.$\blacksquare$ Now for $n = 2019$ we get $f(n)\ge 44$.