# 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

• There are only $10!$ arrangements! It's completely inelegant, but your device almost certainly has enough computing power to find the optimal arrangement within seconds. I'd highly recommend using itertools with python. Commented May 3, 2020 at 16:06
• See oeis.org/A049031. Commented May 3, 2020 at 20:11
• @MartinR wow, it seems everything is on oeis at this point Commented May 6, 2020 at 4:09
• By Holder's Inequality : $\displaystyle \sum_{n=1}^{10} b_{n}^3 \leq \left ( \sum_{n=1}^{10} b_{n} \right )^3 .$ Is it ? Or am I wrong ? Commented May 8, 2020 at 16:20

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.

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

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*}