Determine the highest possible value of: $$S = a_1a_2a_3 + a_4a_5a_6 +... + a_{2017}a_{2018}a_{2019} + a_{2020}$$where $(a_1, a_2, a_3,..., a_{2020})$ is a permutation of $(1,2,3,..., 2020)$. Clarification: In $S$, each term, except the last one, is the multiplication of three numbers.
Problem
Source: 2020 Argentina OMA L3 p5
Tags: inequalities, Sum, permutation, algebra
04.01.2021 18:25
bump.....
07.01.2021 03:53
any solution?
11.01.2021 15:30
Let be $m\in\mathbb{N}, m\ge2; x_1<x_2\dots<x_{3m-1}<x_{3m},\;3m$ distinct positive numbers and $S_{3m}$ the set $\{(y_1,y_2,\dots,y_{3m})\}$ of the permutations $\sigma$ of $(x_1,x_2,\dots,x_{3m})$. Then is true the property $\textbf{P}_m$: $\max_{\sigma\in S_{3m}}\{y_1y_2y_3+y_4y_5y_6+\dots+y_{3m-2}y_{3m-1}y_{3m}\}=x_1x_2x_3+x_4x_5x_6+\dots+x_{3m-2}x_{3m-1}x_{3m}$. Proof by induction: Step 1: The statement is true for $m=2$. a) $x_1x_2x_3+x_4x_5x_6-(x_6x_5x_3+x_4x_2x_1)=(x_4-x_3)(x_6x_5-x_2x_1)>0\Longrightarrow$ $\Longrightarrow x_1x_2x_3+x_4x_5x_6>x_6x_5x_3+x_4x_2x_1$. Similarly: $x_1x_2x_3+x_4x_5x_6>x_6x_5x_2+x_4x_3x_1$; $x_1x_2x_3+x_4x_5x_6>x_6x_5x_1+x_4x_3x_2$; $x_1x_2x_3+x_4x_5x_6>x_6x_4x_3+x_5x_2x_1$; $x_1x_2x_3+x_4x_5x_6>x_6x_4x_2+x_5x_3x_1$; $x_1x_2x_3+x_4x_5x_6>x_6x_4x_1+x_5x_3x_2$. b) $x_1x_2x_3+x_4x_5x_6-(x_6x_3x_2+x_5x_4x_1)=(x_6-x_1)(x_5x_4-x_3x_2)>0\Longrightarrow$ $\Longrightarrow x_1x_2x_3+x_4x_5x_6>x_6x_3x_2+x_5x_4x_1$. Similarly: $x_1x_2x_3+x_4x_5x_6>x_6x_3x_1+x_5x_4x_2$; $x_1x_2x_3+x_4x_5x_6>x_6x_2x_1+x_5x_4x_3$. We covered all possible combinations of the expression $y_1y_2y_3+y_4y_5y_6$, hence the property $\textbf{P}_2$ is true. Step 2: Assume the property $\textbf{P}_m$ is true for $m\in\mathbb{N}, m\ge2$. Consider the distinct positive numbers $x_1<x_2<\dots<x_{3m+1}<x_{3m+2}<x_{3m+3}$ and $(y_1,y_2,\dots,y_{3m+3})$ a permutation of $(x_1,x_2,\dots,x_{3m+3})$. We will prove: $x_1x_2x_3+x_4x_5x_6+\dots+x_{3m+1}x_{3m+2}x_{3m+3}\ge y_1y_2y_3+y_4y_5y_6+\dots+y_{3m+1}y_{3m+2}y_{3m+3},\;\forall (y_1,y_2,\dots,y_{3m+3})$ a permutation of $(x_1,x_2,\dots,x_{3m+3})$. Consider a fixed permutation $(y_1,y_2,\dots,y_{3m+3})$. 2.a) Let be $(z_1,z_2,\dots,z_{3m+3})$ the permutation of $(y_1,y_2,\dots,y_{3m+3})$ with the property $z_1=y_1;z_2=y_2;z_3=y_3;z_4<z_5<\dots<z_{3m+2}<z_{3m+3}$. Applying the property $\textbf{P}_m$ to the numbers $y_4,y_5,\dots,y_{3m+2},y_{3m+3}$ results: $y_4y_5y_6+\dots+y_{3m+1}y_{3m+2}y_{3m+3}\le z_4z_5z_6+\dots+z_{3m+1}z_{3m+2}z_{3m+3}\Longrightarrow$ $\Longrightarrow y_1y_2y_3+y_4y_5y_6+\dots+y_{3m+1}y_{3m+2}y_{3m+3}\le z_1z_2z_3+z_4z_5z_6+\dots+z_{3m+1}z_{3m+2}z_{3m+3}$. The set $\{z_1,z_2,z_3\}$ contains $p$ numbers from $\{x_1,x_2,x_3\}$ and $q$ numbers from $\{x_{3m+1},x_{3m+2},x_{3m+3}\}$, with $p,q\in\{0,1,2,3\};0\le p+q\le 3$. The first $3-p\le3$ elements of the set $\{z_4,z_5,z_6\}$ form the set $\{x_1,x_2,x_3\}\setminus\{z_1,z_2,z_3\}$. Results: $\{x_1,x_2,x_3\}\subset\{z_1,z_2,\dots,z_6\}\subset\{z_1,z_2,\dots,z_{3m}\}$. 2.b) Let be $(t_1,t_2,\dots,t_{3m+3})$ the permutation of $(z_1,z_2,\dots,z_{3m+3})$ with the property $t_{3m+1}=z_{3m+1},t_{3m+2}=z_{3m+2},t_{3m+3}=z_{3m+3}; t_1<t_2<t_3<\dots<t_{3m-1}<t_{3m}$. Applying the property $\textbf{P}_m$ to the numbers $z_1,z_2,\dots,z_{3m-1},z_{3m}$ results: $z_1z_2z_3+z_4z_5z_6+\dots+z_{3m-2}z_{3m-1}z_{3m}\le t_1t_2t_3+t_4t_5t_6+\dots+t_{3m-2}t_{3m-1}t_{3m}\Longrightarrow $ $\Longrightarrow z_1z_2z_3+z_4z_5z_6+\dots+z_{3m+1}z_{3m+2}z_{3m+3}\le t_1t_2t_3+t_4t_5t_6+\dots+t_{3m+1}t_{3m+2}t_{3m+3}$. After this step, $(t_1,t_2,t_3)=(x_1,x_2,x_3)$ and results $\{t_4,t_5,\dots,t_{3m+2},t_{3m+3}\}=\{x_4,x_5,\dots,x_{3m+2},x_{3m+3}\}$. 2.c) Applying the property $\textbf{P}_m$ to the numbers $t_4,t_5,\dots,t_{3m+2},t_{3m+3}$ results: $t_4t_5t_6+t_7t_8t_9+\dots+t_{3m+1}t_{3m+2}t_{3m+3}\le x_4x_5x_6+x_7x_8x_9+\dots+x_{3m+1}x_{3m+2}x_{3m+3}\Longrightarrow$ $\Longrightarrow t_1t_2t_3+t_4t_5t_6+\dots+t_{3m+1}t_{3m+2}t_{3m+3}\le x_1x_2x_3+ x_4x_5x_6+\dots+x_{3m+1}x_{3m+2}x_{3m+3}$. From the steps 2.a),2.b),2.c)results: $y_1y_2y_3+y_4y_5y_6+\dots+y_{3m+1}y_{3m+2}y_{3m+3}\le x_1x_2x_3+ x_4x_5x_6+\dots+x_{3m+1}x_{3m+2}x_{3m+3}$ and the induction is complete. Hence, the maximum of $y_1y_2y_3+y_4y_5y_6+\dots+y_{3m+1}y_{3m+2}y_{3m+3}$ occurs for the permutation of the numbers in increasing order. Return to our particular problem: Let be $(b_1,b_2,\dots,b_{2019})$ the permutation of $(a_1,a_2,\dots,a_{2019})$ with the property $b_1<b_2<\dots<b_{2018}<b_{2019}$. Using the previous paragraph, results for a fixed $a_{2020}$: $\max\{a_1a_2a_3+a_4a_5a_6+\dots+a_{2017}a_{2018}a_{2019}+a_{2020}\}=b_1b_2b_3+b_4b_5b_6+\dots+b_{2017}b_{2018}b_{2019}+a_{2020}$. If $a_{2020}=k\in\{1,2,\dots,2020\}$, results $b_i=\begin{cases}i,\text{ for }i\le k-1;\\i+1,\text{ for }i\ge k.\end{cases}, \; i\in\{1,2,\dots,2019\}$. We need to find the value of $k$ for which $b_1b_2b_3+b_4b_5b_6+\dots+b_{2017}b_{2018}b_{2019}+k$ is maximum. Denote $E(k)=b_1b_2b_3+b_4b_5b_6+\dots+b_{2017}b_{2018}b_{2019}+k$. For a fixed $k\le2019$, exist $n\in\{0,1,\dots,672\},r\in\{1,2,3\}$ such that $k=3n+r$. a) If $r=1$, then $E(k+1)-E(k)= [(3n+1)(3n+3)(3n+4)+(k+1)]-[(3n+2)(3n+3)(3n+4)+k]<0$; b) If $r=2$, then $E(k+1)-E(k)= [(3n+1)(3n+2)(3n+4)+(k+1)]-[(3n+1)(3n+3)(3n+4)+k]<0$; c) If $r=3$, then $E(k+1)-E(k)= [(3n+1)(3n+2)(3n+3)+(k+1)]-[(3n+1)(3n+2)(3n+4)+k]<0$. Results: $\max\{a_1a_2a_3+a_4a_5a_6+\dots+a_{2017}a_{2018}a_{2019}+a_{2020}\}=\max_{1\le k\le2020}{E(k)}=E(1)=$ $=1+2\cdot3\cdot4+5\cdot6\cdot7+\dots+2018\cdot2019\cdot2020=1+\sum_{n=1}^{673}(3n-1)\cdot 3n\cdot(3n+1)=$ $=1+\sum_{n=1}^{673}(27n^3-3n)=1+27\cdot\left(\dfrac{673\cdot674}{2}\right)^2-3\cdot\dfrac{673\cdot674}{2}=1388844046825$.