Track / Stage 7 / 216 of 300 #1616 of 2000

Problem 1616

National olympiad second round; IMO P1/P4

Algebra Difficulty 7.5 Prove it 13th Bay Area Mathematical Olympiad · United States

Problem:
Let $S$ be a finite, nonempty set of real numbers such that the distance between any two distinct points in $S$ is an element of $S$ . In other words, $|x-y|$ is in $S$ whenever $x \neq y$ and $x$ and $y$ are both in $S$ .
Prove that the elements of $S$ may be arranged in an arithmetic progression. This means that there are numbers $a$ and $d$ such that $S=\{a, a+d, a+2d, a+3d, \ldots, a+kd, \ldots\}$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solution:
If $S$ has just one element, then $S=\{a\}$ satisfies the given condition.

Let the elements of $S$ be $a_1 < a_2 < \cdots < a_n$ .

If $a_1 < 0$ , then $|a_n - a_1| \geq a_n - a_1 > a_n$ , so $|a_n - a_1|$ cannot be an element of $S$ —contradiction.

Now suppose $a_1 > 0$ . The numbers
$\begin{aligned} b_2 & = a_2 - a_1 \\ b_3 & = a_3 - a_1 \\ & \vdots \\ b_n & = a_n - a_1 \end{aligned}$
are all positive differences of members of $S$ , so each is in $S$ . But each $b_k$ is less than $a_k$ , and greater than $b_2, \ldots, b_{k-1}$ , so by induction we must have $b_k = a_{k-1}$ . Thus, $a_{k-1} = a_k - a_1$ for $k = 2, 3, \ldots, n$ , which gives $a_k = k a_1$ for each $k$ . Thus the members of $S$ form the arithmetic progression $a_1, 2a_1, 3a_1, \ldots, n a_1$ .

Finally, if $a_1 = 0$ , then we can remove $a_1$ and the remaining members of $S$ still satisfy the condition of the problem. Then, by the previous case, they are $a_2, 2a_2, \ldots, (n-1)a_2$ . Hence, the members of $S$ form the arithmetic progression $0, a_2, 2a_2, \ldots, (n-1)a_2$ .

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.