Maths Olympiad Prep

Library / /5 of 6

Combinatorics Difficulty 6.8 National olympiad Prove it Romania

Determine all integers n3n \ge 3 satisfying the following condition: there exist pairwise distinct real numbers a1,a2,,ana_1, a_2, \dots, a_n such that the 12n(n1)\frac{1}{2}n(n-1) sums ai+aja_i+a_j, 1i<jn1 \le i < j \le n, ordered increasingly, form an arithmetic sequence (the difference of every two consecutive sums is the same).

Solution

The required integers are n=3n=3 and n=4n=4. In the former case, let (a1,a2,a3)=(1,2,3)(a_1, a_2, a_3) = (1, 2, 3); the sums of pairs form the arithmetic sequence 3,4,53, 4, 5. In the other case, let (a1,a2,a3,a4)=(1,3,4,5)(a_1, a_2, a_3, a_4) = (1, 3, 4, 5); the sums of pairs form the arithmetic sequence 4,5,6,7,8,94, 5, 6, 7, 8, 9.
Since the nn numbers are pairwise distinct, so are the 12n(n1)\frac{1}{2}n(n-1) sums of pairs — otherwise, the difference of the arithmetic sequence would be zero, so the first and the second smallest sums would be equal, hence the second and the third smallest numbers would be equal, and we would reach a contradiction.

Let now n5n \ge 5, and suppose, if possible, that a1,a2,,ana_1, a_2, \dots, a_n satisfy the condition in the statement. Without loss of generality, we may and will assume that a1<a2<<ana_1 < a_2 < \dots < a_n. Let dd be the difference of the corresponding arithmetic sequence of sums.
The smallest sum is a1+a2a_1 + a_2, and the second smallest sum is a1+a3a_1 + a_3, so a3a2=da_3 - a_2 = d. The largest sum is an1+ana_{n-1} + a_n, and the second largest sum is an2+ana_{n-2} + a_n, so an1an2=da_{n-1} - a_{n-2} = d. Consequently, a2+an1=(a3d)+(an2+d)=a3+an2a_2 + a_{n-1} = (a_3 - d) + (a_{n-2} + d) = a_3 + a_{n-2}. If n6n \ge 6, the leftmost sum and the rightmost sum correspond to distinct pairs, so they are at least dd distance apart. This contradiction forces n=5n=5.
Let n=5n=5. By the preceding, a3a2=da_3 - a_2 = d, and a4a3=da_4 - a_3 = d, so 2a3=a2+a42a_3 = a_2 + a_4. To reach a contradiction, we present two approaches.

1st Approach. Evaluate the sum s=1i<j5(ai+aj)s = \sum_{1 \le i < j \le 5} (a_i + a_j) in two different ways. On the one hand, s=5(a1+a2+a4+a5)s = 5(a_1 + a_2 + a_4 + a_5). On the other hand, s=4(a1+a2+a3+a4+a5)s = 4(a_1 + a_2 + a_3 + a_4 + a_5), since each aka_k occurs in exactly four sums ai+aja_i + a_j, i<ji < j. Equate the two and clear out like terms, to get a1+a2+a4+a5=4a3=2(a2+a4)a_1 + a_2 + a_4 + a_5 = 4a_3 = 2(a_2 + a_4). Consequently, a1+a5=a2+a4a_1 + a_5 = a_2 + a_4 which is the desired contradiction.

2nd Approach. Notice that the third smallest sum is a1+a4a_1 + a_4 which is dd larger than a1+a3a_1 + a_3, and the third largest sum is a2+a5a_2 + a_5. Between these lie a1+a5a_1 + a_5 and the consecutive sums a2+a3<a2+a4<a3+a4a_2 + a_3 < a_2 + a_4 < a_3 + a_4. Then a1+a5a_1 + a_5 is either the fourth smallest sum or the fourth largest.
Without loss of generality, we may and will assume that a1+a5a_1 + a_5 is the fourth smallest sum. The string of ten sums is then a1+a2<a1+a3<a1+a4<a1+a5<a2+a3<a2+a4<a3+a4<a2+a5<a3+a5<a4+a5a_1 + a_2 < a_1 + a_3 < a_1 + a_4 < a_1 + a_5 < a_2 + a_3 < a_2 + a_4 < a_3 + a_4 < a_2 + a_5 < a_3 + a_5 < a_4 + a_5.
Evaluate a5a4a_5 - a_4 in two different ways. On the one hand, a5a4=(a1+a5)(a1+a4)=da_5 - a_4 = (a_1 + a_5) - (a_1 + a_4) = d, by the third inequality from the left. On the other hand,
a5a4=((a2+a5)(a3+a4))+(a3a2)=d+d=2d, a_5 - a_4 = ((a_2 + a_5) - (a_3 + a_4)) + (a_3 - a_2) = d + d = 2d,
by the third inequality from the right and a3a2=da_3 - a_2 = d. This is the desired contradiction.

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 and solution reproduced as published; topic and difficulty added by this site.