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 ) $

Question

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

Answer 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.

Answer 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)}}.$

Answer 3

Here are some heuristic thoughts.

A generalisation:

We set $N=10$ and consider the generalisation \begin{align*} \color{blue}{\sum_{n=1}^N\left(na_n^2-n^2a_n\right)\qquad\to\qquad \max}\tag{1} \end{align*}

We computationally calculate the maximum of the sum in (1) for small values of $N=2,3,...,8$ and obtain \begin{align*} \begin{array}{c|r|l} N&\max&(a_1,a_2,\ldots,a_N)\\ \hline 2&0&(1,2)\\ &0&(2,\color{blue}{1})\\ 3&2&(2,3,\color{blue}{1})\\ 4&8&(2,3,4,\color{blue}{1})\\ 5&20&(2,3,4,5,\color{blue}{1})\\ 6&40&(2,3,4,5,6,\color{blue}{1})\\ &40&(3,4,5,6,\color{blue}{2,1})\\ 7&80&(3,4,5,6,7,\color{blue}{2,1})\\ 8&140&(3,4,5,6,7,8,\color{blue}{2,1}) \end{array}\tag{2} \end{align*}

Table (2) clearly shows which kind of pattern we have to study. We start with a value $1\leq k\leq N-1$ and the sequence which produces a maximum is one or more of \begin{align*} \left(k+1,\ldots,N,\color{blue}{k,k-1,\ldots,1}\right)\qquad\qquad k\in\{1,2,\ldots,N-1\}\tag{3} \end{align*}

Plausibility check:

The expression (1) \begin{align*} \sum_{n=1}^N\left(na_n^2-n^2a_n\right)=\sum_{n=1}^Nna_n^2-\sum_{n=1}^Nn^2a_n\qquad\to\qquad \max \end{align*} becomes a maximum if we can find pattern $(a_1,a_2,\ldots,a_N)$ so that one sum becomes as large as possible whereas the other sum becomes as small as possible (indicated by max/min with tilde notation). \begin{align*} \sum_{n=1}^Nna_n^2&\qquad\to\qquad\widetilde{\max}\\ \sum_{n=1}^Nn^2a_n&\qquad\to\qquad\widetilde{\min} \end{align*}

This approach is plausible, since \begin{align*} \begin{array}{llll} (1,2,\ldots,N)&\to &\sum_{n=1}^N n a_n^2=\sum_{n=1}^Nn^3&\to\max\\ \\ (N,N-1,\ldots,1)&\to &\sum_{n=1}^N n a_n^2=\sum_{n=1}^Nn(N+1-n)^2&\to\min\\ \end{array} \end{align*} are maximum and minimum values and cyclic shift of the permutation decreases the value of the first sum and increases the value of the second sum.

Conclusion:

It is sufficient to consider the $N-1$ permutations \begin{align*} \color{blue}{\left(k+1,k+2,\ldots,N,k,k-1,\ldots,1\right)\qquad\qquad k\in\{1,2,\ldots,N-1\}} \end{align*} which maximize the sum \begin{align*} &\color{blue}{\sum_{n=1}^N}\color{blue}{\left(na_n^2-n^2a_n\right)}\\ &\ \ =\sum_{n=1}^{N-k}\left(n(n+k)^2-n^2(n+k)\right)\\ &\quad+\sum_{n=1}^k\left((N-k+n)(k+1-n)^2-(N-k+n)^2(k+1-n)\right)\\ &\ \;\,\,\color{blue}{=\frac{1}{3}k\left(N\left(N^2-1\right)-k\left(3N^2-1\right)+3k^2N-k^3\right)}\tag{4}\\ &\qquad\qquad\color{blue}{\to \max} \end{align*}

We finally find for $N=10$ using formula (4) \begin{align*} \begin{array}{r|rrrrrrrrr} k&1&2&3&4&5&6&7&8&9\\ \sum&240&\color{blue}{336}&\color{blue}{336}&280&200&120&56&16&0 \end{array} \end{align*} two solutions $k=2,3$ providing a maximum: \begin{align*} \color{blue}{(3,4,5,6,7,8,9,10,2,1)}\quad\to\quad\sum_{n=1}^{10}\left(na_n^2-n^2a_n\right)=\color{blue}{336}\\ \color{blue}{(4,5,6,7,8,9,10,3,2,1)}\quad\to\quad\sum_{n=1}^{10}\left(na_n^2-n^2a_n\right)=\color{blue}{336} \end{align*}