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$?

Comments

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

Kornrade

5 years ago

Hello,

I would argue that the least number of unmatched distances is [n/2], where [x] is the gratest integer lower than or equal to x. Examples: N = 3, X = {-1,0,1}, distances between all pairs are: 1,2,1, of which only 2 is unmatched. N = 4, X = {-2,-1,1,2}, distances between all pairs are: 1,3,4,2,3,1, of which only 4 and 2 are unmatched. N = 5, X = {-3,-2,0,2,3}, distances between all pairs are: 1,3,5,6,2,4,5,2,3,1, of which only 6 and 4 are unmatched. N = 6, X = {-5,-4,-2,2,4,5}, unmatched distances between all pairs are: 4, 8, 10.

(1) General positioning of the points is symmetric, because the number of unmatched distances for non-symmetric positionings is greater than for symmetric positionings. (2) The distance between any two consecutive points on the same side of the origin is a power of 2, with lower distances being further away from the origin. For odd N, point 0 is in the set X. For even N, the distance between the middle points is 2^(N/2 - 1). Proof that distances match only for symmetric-lying pairs of points can be done by writing the distances in binary. (Thus no distance can appear more than twice) (3) The only unmatched distances are distances between pairs of symmetric points with regards to the origin, and there are [N/2] such pairs.

Proof that this is the lowest number of unmatched distances comes from combining (1) and (3), while (2) is there only to ensure that there are no triplet distances. From (1) we know that X must be symmetric, from (3) we know that any symmetric set must have exactly [n/2] unmatched distances.