# Finding maximum of a function with unfixed number of variables

Can anybody solve this:

For a constant positive integer $n\geq6$ find $k$ and positive integers $a_{1},a_{2},...,a_{k}$ that maximize the expression

$$\sum_{i=1}^{k}\left[-4a_{i}^{3}+\left(3n-3\right)a_{i}^{2}+\left(3n+1\right)a_{i}\right],$$ with $a_{1}+a_{2}+\dots+a_{k}=n$.

Some of my experimental results shows that the optimal solution is attained at $k=3$, with $a_{1},a_{2},a_{3}$ roughly equal to $\frac{n}{3}$.

• If you allow the $a_i$s to be 0, you can fix $k=n$. – Brendan McKay Dec 11 '14 at 5:49

Allow the variables to be zero, and take $k=n$.
If $a_i,a_j$ are changed to $a_i-1,a_j+1$, the function changes by $6(a_j-a_i+1)(n-2a_i-2a_j-1)$. From this, everything follows.
If there are four non-zero values, the smallest two of them sum to at most $n/2$, so it is advantageous to move them apart until one of them is 0. Therefore, the optimum occurs with at most three non-zero values.
If one value is greater than n/2, and there are two other nonzero values, it is likewise advantageous to move the two small values apart until one is 0: you get two non-zero values which are best as equal as possible. If there are three values all less than $n/2$, it is advantageous to move them together.
• Thank you for great answer! There is a slight problem with this solution at $n=4$, where $a_1=a_2=a_3=a_4=1$ is optimal solution (note that changing values with above procedure yields a negative change of a function). But otherwise I think this solves it. Thanks a lot! – Matjaž Krnc Dec 16 '14 at 10:02