Maths Olympiad Prep

Library / Belarus competition problems /14 of 30

Belarus competition problems

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+⋯+aik∣≤∣1011+1010+⋯+1012−k∣ |a_{i_1} + a_{i_2} + \dots + a_{i_k}| \le |1011 + 1010 + \dots + 1012 - k|
Moreover, this estimate is reached when ai=1012−ia_i = 1012 - i or ai=−1012+ia_i = -1012 + i. Hence
A1≤1011+(1011+1010)+⋯+(1+2+⋯+1011) A_1 \le 1011 + (1011 + 1010) + \dots + (1 + 2 + \dots + 1011)
A2≤1011+(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
2⋅1011+2⋅(1011+1010)+⋯+2⋅(1011+⋯+2)+(1011+⋯+1)==2⋅(12+22+⋯+10112)−(1+2+⋯+1011)=2⋅1011⋅1012⋅20236−1011⋅1012⋅36=1011⋅1012⋅40436. 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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