Maths Olympiad Prep

Library / /14 of 31

Algebra Difficulty 6.0 National olympiad Prove it Belarus

The numbers 1011,1010,,1,1,2,,1010,1011-1011, -1010, \dots, -1, 1, 2, \dots, 1010, 1011 are arranged as a1,a2,,a2022a_1, a_2, \dots, a_{2022} in some order.
Find the maximal possible value of
a1+a1+a2+a1+a2+a3++a1+a2++a2022.|a_1| + |a_1 + a_2| + |a_1 + a_2 + a_3| + \dots + |a_1 + a_2 + \dots + a_{2022}|. (Yahor Dubovik)

Solution

Note that the sum of all numbers is 00, so the required sum can be presented as the sum of the following two sums:
A1=a1+a1+a2++a1+a2++a1011 A_1 = |a_1| + |a_1 + a_2| + \dots + |a_1 + a_2 + \dots + a_{1011}|
and
A2=a2022+a2022+a2021++a2022++a1013. A_2 = |a_{2022}| + |a_{2022} + a_{2021}| + \dots + |a_{2022} + \dots + a_{1013}|.
Let's bound each term of each sum separately. If ai1,ai2,,aika_{i_1}, a_{i_2}, \dots, a_{i_k} are k<1012k < 1012 pairwise distinct elements of the sequence given in the problem statement, then
ai1+ai2++aik1011+1010++1012k |a_{i_1} + a_{i_2} + \dots + a_{i_k}| \le |1011 + 1010 + \dots + 1012 - k|
Moreover, this estimate is reached when ai=1012ia_i = 1012 - i or ai=1012+ia_i = -1012 + i. Hence
A11011+(1011+1010)++(1+2++1011) A_1 \le 1011 + (1011 + 1010) + \dots + (1 + 2 + \dots + 1011)
A21011+(1011+1010)++(1+2++1011) A_2 \le 1011 + (1011 + 1010) + \dots + (1 + 2 + \dots + 1011)
So, the maximal possible value of the original sum is equal to
21011+2(1011+1010)++2(1011++2)+(1011++1)==2(12+22++10112)(1+2++1011)=210111012202361011101236=1011101240436. 2 \cdot 1011 + 2 \cdot (1011 + 1010) + \dots + 2 \cdot (1011 + \dots + 2) + (1011 + \dots + 1) = \\ = 2 \cdot (1^2 + 2^2 + \dots + 1011^2) - (1+2+\dots+1011) = \\ 2 \cdot \frac{1011 \cdot 1012 \cdot 2023}{6} - \frac{1011 \cdot 1012 \cdot 3}{6} = \frac{1011 \cdot 1012 \cdot 4043}{6}.

This sum is reachable if the numbers are arranged in ascending or descending order.

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.