Maths Olympiad Prep

Library / /73 of 86

Algebra Difficulty 7.5 National Olympiad, round 2 Prove it United States

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

Solution

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

Let the elements of SS be a1<a2<<ana_1 < a_2 < \cdots < a_n.

If a1<0a_1 < 0, then ana1ana1>an|a_n - a_1| \geq a_n - a_1 > a_n, so ana1|a_n - a_1| cannot be an element of SS—contradiction.

Now suppose a1>0a_1 > 0. The numbers
b2=a2a1b3=a3a1bn=ana1 \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 SS, so each is in SS. But each bkb_k is less than aka_k, and greater than b2,,bk1b_2, \ldots, b_{k-1}, so by induction we must have bk=ak1b_k = a_{k-1}. Thus, ak1=aka1a_{k-1} = a_k - a_1 for k=2,3,,nk = 2, 3, \ldots, n, which gives ak=ka1a_k = k a_1 for each kk. Thus the members of SS form the arithmetic progression a1,2a1,3a1,,na1a_1, 2a_1, 3a_1, \ldots, n a_1.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.