if $ \{ a_1 , a_2 , \cdots, a_{10} \} = \{ 1, 2, \cdots , 10 \} $ . Find the maximum value of $I= \sum_{n=1}^{10}(na_n ^2 - n^2 a_n ) $

Let $ \{ a_1 , a_2 , \cdots, a_{10} \} = \{ 1, 2, \cdots , 10 \} $ . Find the maximum value of $$I= \sum_{n=1}^{10}(na_n ^2 - n^2 a_n ) $$

I try: since $(a-b)^3=a^3-3a^2b+3ab^2-b^3$,and $\sum_{n=1}^{10}n^3=\sum_{n=1}^{10}a^3_{n}$so we have $$3I=\sum_{n=1}^{10}(3na_{n}^2-3n^2a_{n})=\sum_{n=1}^{10}(n-a_{n})^3$$ take $b_{n}=n-a_{n}$,and we need to maxumize $\sum_{n=1}^{10}b^3_{n}$ with the constraint $\sum_{i=1}^{10}b_{i}=0$ and $-9\le b_{i}\le 9$,and I can't,somedays ago,it is said can use the Karamata inequality to found it,and to day said the reslut is $336$,But I consider sometimes,can find it,Thank you for your help

Solution 1:

You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{n,v}$ indicate whether $a_n=v$. The problem is to maximize $$I = \sum_{n=1}^{10} (n a_n^2 - n^2 a_n) = \sum_{n=1}^{10} \sum_{v=1}^{10} (n v^2 - n^2 v) x_{n,v}$$ subject to linear constraints \begin{align} \sum_v x_{n,v} &= 1 &&\text{for all $n$} \tag1 \\ \sum_n x_{n,v} &= 1 &&\text{for all $v$} \tag2 \end{align} Constraint $(1)$ assigns exactly one value $v$ to each $a_n$. Constraint $(2)$ assigns exactly one $a_n$ for each value $v$.

An optimal solution, with objective value $336$, turns out to be $$x_{1,4}=x_{2,5}=x_{3,6}=x_{4,7}=x_{5,8}=x_{6,9}=x_{7,10}=x_{8,3}=x_{9,2}=x_{10,1}=1,$$ with all other $x_{n,v}=0$, and this solution corresponds to $a=(4,5,6,7,8,9,10,3,2,1)$.

The linear programming upper bound is also $336$, and the dual variables provide a certificate of optimality.

Duals for the lower bound $x_{n,v} \ge 0$: \begin{matrix} n \backslash v &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline 1 &-84 &-28 &0 &0 &-6 &-20 &-44 &-80 &-130 &-196 \\ 2 &-90 &-34 &-4 &0 &0 &-6 &-20 &-44 &-80 &-130 \\ 3 &-94 &-40 &-10 &-4 &0 &0 &-6 &-20 &-44 &-80 \\ 4 &-94 &-44 &-16 &-10 &-4 &0 &0 &-6 &-20 &-44 \\ 5 &-88 &-44 &-20 &-16 &-10 &-4 &0 &0 &-6 &-20 \\ 6 &-74 &-38 &-20 &-20 &-16 &-10 &-4 &0 &0 &-6 \\ 7 &-50 &-24 &-14 &-20 &-20 &-16 &-10 &-4 &0 &0 \\ 8 &-14 &0 &0 &-14 &-20 &-20 &-16 &-10 &-4 &0 \\ 9 &0 &0 &-12 &-36 &-50 &-56 &-56 &-52 &-46 &-40 \\ 10 &0 &-16 &-42 &-78 &-102 &-116 &-122 &-122 &-118 &-112 \\ \end{matrix} Duals for constraint $(1)$: $$(50, 54, 54, 48, 34, 10, -26, -76, -106, -124)$$ Duals for constraint $(2)$: $$(34, -20, -44, -38, -24, 0, 36, 86, 152, 236)$$ Multiplying the corresponding constraints by these dual multipliers and adding them up yields $I \le 336$, as claimed.

Solution 2:

$\color{brown}{\mathbf{Notation.}}$

Denote \begin{cases} \overrightarrow A = (a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10})\\ \overrightarrow E = (1,2,3,4,5,6,7,8,9,10),\\ R^{[k]}_z\left(\overrightarrow A\right) = (a_{z+1},a_{z+2},\dots,a_{k},a_1,a_2,\dots a_z,a_{k+1},a_{k+2},\dots,a_{10})\\ R\underbrace{_{z,y,\dots,f}}_l\left(\overrightarrow A\right) = \underbrace{R^{[11-l]}_f\left(\dots R^{[9]}_y\left(\dots R^{[10]}_z\left(\overrightarrow A\right)\right)\right)}_{l},\tag1 \end{cases} where
$\quad z\in \{0,1,\dots,k\},\quad k\in \{2,3,4,5,6,7,8,9,10\},\quad l\in\{1,2,3,4,5,6,7,8,9\},$

$\quad R^{[k]}_z\left(\overrightarrow A\right)$ is the left cyclic shift of the first $k$ components of $\overrightarrow A$ to $z$ positions,

$\quad R\underbrace{_{z,y,\dots,f}}_l\left(\overrightarrow A\right)$ is the superposition of such shifts with the decreasing quantity of permutated components.

The first cyclic shift allows to set the value of $a_{10},$ the second cyclic shift - to set the value of $a_9,$ and so on.
For example, \begin{cases} R_1\left(\overrightarrow E\right) = (2,3,4,5,6,7,8,9,10,1),\\ R_{1,1}\left(\overrightarrow E\right) = (3,4,5,6,7,8,9,10,2,1),\\ R_2\left(\overrightarrow E\right) = (3,4,5,6,7,8,9,10,1,2),\dots \end{cases} Therefore, any vector $\overrightarrow A$ belongs to the set of superpositions $(2)$ of the cyclic shifts in the form of $$\left\{R_{\large z^\,_{10},z^\,_9,\dots,z^\,_2}\left(\overrightarrow E\right),\quad\text{where}\quad z_k\in\{0,1,\dots,k-1\}\right\}.$$

In the further, will be used short notation $$\vec E_{\large z^\,_{10},z^\,_9,\dots,z^\,_2} = R_{\large z^\,_{10},z^\,_9,\dots,z^\,_2}\left(\overrightarrow E\right),\quad I_{\large z^\,_{10},z^\,_9,\dots,z^\,_2} = I\left(\vec E_{\large z^\,_{10},z^\,_9,\dots,z^\,_2}\right).\tag2$$

$\color{brown}{\textbf{The task standing.}}$

The goal function can be presented in the form of $$I\left(\overrightarrow A\right) = \frac13\sum\limits_{n=1}^{10} n^3 - \frac13\sum\limits_{n=1}^{10} a_n^3 - \sum\limits_{n=1}^{10} n^2a_n +\sum\limits_{n=1}^{10} na_n^2 = \frac13\sum\limits_{n=1}^{10}(n-a_n)^3,\tag3$$ (see also OP).

Then the permutation of the pair $(a_k,a_{k+1})$ of neighbour elements leads to the difference \begin{align} &3\Delta I = (k-a_k)^3 + (k+1-a_{k+1})^3 - (k-a_{k+1})^3 - (k+1-a_k)^3 \\ &= (a_{k+1}-a_k)\Big((k-a_k)^2+(k-a_k)(k-a_{k+1})+(k-a_{k+1})^2\Big)\\ &+(a_k-a_{k+1})\Big((k+1-a_k)^2+(k+1-a_k)(k+1-a_{k+1})+(k+1-a_{k+1})^2\Big)\\ &=3(a_{k+1}-a_k)\Big(k^2-ka_k-ka_{k+1} - (k+1)^2+(k+1)a_k+(k+1)a_{k+1}\Big)\\ &=3(a_{k+1}-a_k)(a_k+a_{k+1}-2k-1), \end{align}

which should be positive for any pair of the solution's neighbour components.
This leads to constraint to the neighbour components of solution $\overrightarrow A$ in the form of

\begin{cases} a_{k+1} > a_{k},\quad\text{if}\quad a_k+a_{k+1} > 2k+1\\ a_{k+1} < a_{k},\quad\text{if}\quad a_k+a_{k+1} < 2k+1.\tag4 \end{cases}

$\color{brown}{\mathbf{Searching.}}$

The obtained task is a discrete optimization task. Should be maximized $I_{\large z^\,_{10},z^\,_9,\dots,z^\,_2},$ taking in account $(3)-(4).$

The goal function assumed unimodal.

The first cyclic shift leads to the vector $$\vec E_z = (z+1,z+2,\dots,10,1,2,\dots z),\tag{5}$$ wherein from $(4)$ should $z<2.$

Then the single possible solution under constraints $(4)$ is $\vec E_1.$

Similarly, for dimensions $l\le5$ the set of the possible solutions is $$\{\vec E_1,\vec E_{1,1},\vec E_{1,1,1},\vec E_{1,1,1,1},\vec E_{1,1,1,1,1}\},$$

wherein $$E\underbrace{_{1,1,\dots,1}}_l = (l+1,l+2,\dots,10,l,l-1,\dots,1),$$

$$3I\underbrace{_{1,1,\dots,1}}_l = \sum\limits_{k=1}^{10-l}(-l)^3 + \sum_{k=11-l}^{10}(2k-11)^3 = \sum\limits_{k=1}^{10-l}(-l)^3 + \sum_{k=1}^l (11-2k)^3,$$ $$I\underbrace{_{1,1,\dots,1}}_l = \frac13 l(9-l)(10-l)(11-l),\tag6$$ $$\begin{pmatrix}I_1 \\ I_{1,1} \\ I_{1,1,1} \\ I_{1,1,1,1} \\ I_{1,1,1,1,1}\end{pmatrix} =\begin{pmatrix} 240 \\ 336 \\ 336 \\ 280 \\ 200 \end{pmatrix}\tag7.$$

Therefore, maximum of the issue sum is

$\color{brown}{\mathbf{I_{\max}=336}}$ at $\color{green}{\mathbf{\overrightarrow A = (3,4,5,6,7,8,9,10,2,1)}}$ or $\color{green}{\mathbf{\overrightarrow A = (4,5,6,7,8,9,10,3,2,1)}}.$