16. Let $a_{1}, a_{2}, \ldots, a_{24}$ be integers with sum 0 and satisfying $\left|a_{i}\right| \leq i$ for all $i$. Find the greatest possible value of $a_{1}+2 a_{2}+3 a_{3}+\cdots+24 a_{24}$.
(2 marks)設 $a_{1} 、 a_{2} 、 \cdots 、 a_{24}$ 為整数, 它們之和為 0 , 且對所有 $i$ 皆有 $\left|a_{i}\right| \leq i$ 。求 $a_{1}+2 a_{2}+3 a_{3}+\cdots+24 a_{24}$ 的最大可能值。
16. 1432
16. Clearly the maximum value exists as $a_{1}+2 a_{2}+3 a_{3}+\cdots+24 a_{24} \leq 1^{2}+2^{2}+\cdots+24^{2}$. Let's see what happens when maximality is reached. We claim that at maximality, we must have $a_{m}=-m$ or $a_{n}=n$ for any pair $(m, n)$ satisfying $1 \leq m<n \leq 24$. Indeed, if this is not true for some such $(m, n)$, then we can replace $a_{m}$ by $a_{m}-1$ and $a_{n}$ by $a_{n}+1$, so that the conditions are still satisfied, but the value of $a_{1}+2 a_{2}+3 a_{3}+\cdots+24 a_{24}$ is increased by $(n-m)$. This contradicts the maximality and hence proves the claim.
In view of the claim and the fact that the sum of $a_{1}$ to $a_{24}$ is zero, when maximality is reached there must exist integers $s$ and $t$ such that $a_{m}=-m$ for $1 \leq m \leq s$ and $a_{n}=n$ for $t \leq n \leq 24$, where $t$ can only be equal to $s+1$ or $s+2$, for otherwise we may take $m=s+1$ and $n=t-1$ and the claim is violated.
- The case $t=s+1$ cannot occur, for otherwise we will get $-(1+2+\cdots s)+[(s+1)+(s+2)+\cdots+24]=0$, or $1+2+\cdots+s=\frac{1+2+\cdots+24}{2}=150$, but 150 is not a triangular number.
- Hence we must have $t=s+2$. We check that the last triangular number below 150 is $1+2+\cdots+16=136$. On the other hand, $18+19+\cdots+24=147$. Hence $a_{17}=-11$. The answer is thus $-\left(1^{2}+2^{2}+\cdots+16^{2}\right)+17(-11)+\left(18^{2}+19^{2}+\cdots+24^{2}\right)=1432$.