Let $a_{i}(i=1,2,\cdots,24)$ be integers,and such $a_{1}+a_{2}+\cdots+a_{24}=0$,and $|a_{i}|\le i,i=1,2,\cdots,24$.Find the maximum of the value $$a_{1}+2a_{2}+3a_{3}+\cdots+24a_{24}$$

It seem use Ablel indentity to solve it?But I try some methods can't to solve it

  • $\begingroup$ You can use the fact that $a1+a2+.......+a24=0$ and replace the value of this equation in this equation $a1+2a2+3a3+.....+24a24$ $\endgroup$ – Deepesh Meena Aug 13 '17 at 3:39
  • $\begingroup$ At worst, this is a linear program; maximize the linear functional $\langle1,2,\ldots,24\rangle\cdot\vec{a}$ subject to the various linear equalities and inequalities. $\endgroup$ – Steven Stadnicki Aug 13 '17 at 3:56
  • $\begingroup$ @StevenStadnicki does LPP will really help for integer solution? (just curious!) $\endgroup$ – MAN-MADE Aug 13 '17 at 4:41
  • $\begingroup$ @MANMAID: Of course not every linear program with integer coefficients and constraints will give an integer solution. But when one does it solves the ILP, and I suspect that is true here. $\endgroup$ – hardmath Aug 13 '17 at 14:28

Some observations, assuming the constraint is observed.

Suppose $i\gt j$ and $|a_i|\lt i, |a_j|\lt j$, then we get a greater sum by using $a_i+1, a_j-1$ which increases the total by $i-j\gt 0$.

Also with $a_i\lt i, a_j=j$ we can do the same.

From this we note that at most one of the $a_i$ is not on the limit, because with a pair off the limit we can always increase the sum. The second observation tells us that if there is one off the limit, everything below it is on the negative limit (because if there were something below on the positive limit, we could increase the sum).

From this we build from all zeros, to make $a_{24}=24$ with $a_1=-1, a_2=-2, a_3=-3, a_4=-4, a_5=-5, a_6=-6, a_7=-3$, then we make $a_{23}=23$ by decreasing $a_j$ for the smallest $j$ we can - and keep going until we can do no more.


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.