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

  • $\begingroup$ If you allow the $a_i$s to be 0, you can fix $k=n$. $\endgroup$ – 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.

So the best is either two values near n/2 or three values near n/3. Try them and you'll see the second is better.

  • $\begingroup$ 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! $\endgroup$ – Matjaž Krnc Dec 16 '14 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.