# Fall 2016, problem 20

Suppose that the points $x_1,\dots,x_n$ are all distinct and lie on a line, with distance between any two pair of points given by $d_{ij}=|x_i-x_j|$. Suppose further that the number of times that each distance will occur is at most two, i.e. that any positive real number $r$ is equal to $d_{ij}$ for at most two $1\le i\lt j\le n$. Then what is the least number of distances that occur exactly once, i.e. what is the least number of positive real numbers $r$ such that $r=d_{ij}$ for one and only one choice of $1\le i\lt j\le n$?

lucianosantos
5 years ago

The answer is $\binom{n}{2}-2(n-2)$, where $n$ is the number of points and $\binom{n}{2}$ is the total number of pair of points, i.e, the total number of $d_{i,j}$. The number sought is the difference between $\binom{n}{2}$ and the maximum number of pairs of points where the distance associated with each pair is just shared only by another pair (2(n-2)).

Let us prove by induction. For $n=2$ it's easy to check. Now assume the validity of the assertion for $n$. Choose first a pair $x_{i},x_{j}$, such that $|x_{i}-x_{j}|$ is the smallest distance. Next choose the point $x_{n+1}$, such that $|x_{i}-x_{n+1}|=|x_{j}-x_{n+1}|$. So we have more two pairs of points with the same distance. Hence the number of pairs of points with this property is $2(n-2)+2 = 2(n-2+1)= 2((n+1)-2)$.

Then $\binom{n+1}{2}- 2((n+1)-2)$, is valid for $n+1$.

As rubs points out, the previous answer is wrong. I think the answer is as follows:

For $n$ even the answer is $\frac{n}{2}$.(For $n$ odd the answer is $\frac{n-1}{2}$. Justification similar to $n$ even).

Justification:

Now consider the points $x_{1},...,x_{n}$ (suppose the numbers are in ascending order) such that $x_{i}-x_{1}= x_{n}-x_{n-(i-1)}$, with $i\leq \frac{n}{2}$ and $|x_{i}-x_{j}|\neq |x_{m}-x_{s}| , i,j,m,s \leq\frac{n}{2}$.

Then, $(i,j\leq\frac{n}{2})$,

$x_{i}-x_{j}$ $=(x_{i}-x_{1})-(x_{ j}-x_{1})$

$=(x_{n}-x_{n-(i-1)})-(x_{n}-x_{n-(j-1)})$

$=x_{n-(j-1)}-x_{n-(i-1)}$.

These equalities we can still conclude that

$x_{n-(i-1)}-x_{j}= x_{n-(j-1)}-x_{i}$.

We obtain thus the largest number of pairs of points where the distance associated with each pair is just shared only by another pair.

And the distances that occur exactly once are $x_{n-(i-1)}-x_{i}$ whose total is $\frac{n}{2}$ which then is the least number of distances that occur exactly once.

The points 0 , 3 , 4 , 5 , 8 seem to provide a counterexample

rubs 5 years ago

Thanks rubs

lucianosantos 5 years ago