Maximize $\sum{a_i^2}$ given $\sum{a_i}=237$ I recently got stuck with the following problem:
Consider 18 integer numbers in segment $[10; 20]$. Find the maximum possible value of
$$
\sum_{i=1}^{18} {a_i^2}
$$
given that
$$\sum_{i=1}^{18} {a_i}=237$$
I don't really know how to approach this problem. The thing is, solving it like constraint optimization problem I got the solution $a_1=a_2=...=a_n=\frac{237}{18} \approx13.2$
But we need to solve it in integers. And just taking numbers around $13.2$ doesn't make sense to me. Any ideas?
 A: An optimal solution cannot have $10 < a_i \leq a_j < 20$ for some $i$, $j$ because that contradicts optimality (you could increment $a_j$ and decrement $a_i$ and get a higher objective value). Therefore, there can be at most one element that is not $10$ or $20$.
There is therefore an optimal solution for which $a_1, \ldots, a_m$ take the value $10$, $a_{m+1},\ldots,a_{17}$ take the value $20$, and $a_{18} \in [10,20] \cap \mathbb{Z}$. From the equality constraint it follows that $a_{18} = 237 - 10m - 20(17-m) = 10m-103$. The only $m$ for which $10m-103 \in [10,20]$ is $m=12$, so the problem is solved.
If you had multiple $m$, you should evaluate the objective value ($100m + 400(17-m) + a_{18}^2 = 100m^2 - 2360m + 17409$) and pick the one for which the objective is the highest.

Other method This problem is also easy to solve with an integer programming solver after you formulate it appropriately. Let $x_{10}$ denote the number of times you pick $10$, etc, then the problem is:
\begin{align}
\max_{x} \quad & \sum_{i=10}^{20} i^2 x_i \\
\text{s.t.} \quad & \sum_{i=10}^{20} i x_i = 237 \\
& \sum_{i=10}^{20} x_i = 18 \\
& x_i \in \mathbb{Z}_+
\end{align}
I have added the GAMS model below, which you can solve on the NEOS server. The optimal solution is
$$a = (10,10,10,10,10,10,10,10,10,10,10,10,17,20,20,20,20,20)$$
with an objective value of 3489.
Set
   i 'idx'    / r10*r20 /;

Parameter
   a(i) / r10 10, r11 11, r12 12, r13 13, r14 14, r15 15, r16 16, r17 17, r18 18, r19 19, r20 20 /;

Integer   Variable x(i);
Variable z;

Equation objective, budget, eighteen_numbers;
objective.. z =e= sum(i, a(i)*a(i)*x(i));
budget.. sum(i, a(i)*x(i)) =e= 237;
eighteen_numbers.. sum(i, x(i)) =e= 18;

Model knapsack / all /;
solve knapsack max z using mip;

A: The idea is to suppose all of the $a_i$ are fixed except for two of them, and see what happens if you add $1$ to one and subtract $1$ from the other.  So say for instance $a_1 = x$, $a_2 = y$, and all the other $a_i$ are fixed.  Then adding $1$ to $x$ and subtracting $1$ from $y$ gives the same sum, but what happens to the sum of squares?  $$(x+1)^2 + (y-1)^2 - (x^2 + y^2)$$ is the amount by which the sum of squares increases or decreases.  But this is $$2x + 1 - 2y + 1 = 2(x-y+1).$$  So if $x \ge y$, this means the sum of squares will increase if we add $1$ to $x$ and subtract $1$ from $y$.  Repeated application of this logic means that the sum of squares is actually maximized when $x$ is as large as possible and $y$ is as small as possible.  Then we repeat this logic for the other terms in the sum; it follows that the maximum is attained when we can make as many of the $a_i$ as large as possible.  Since the $a_i$ are restricted to $[10; 20]$ we want the largest $m$ such that $20 m + 10(18 - m) \le 237$, or $m = 5$.  This means $5$ of the $a_i$ are equal to $20$, $12$ of them are $10$, and the last one makes up the remainder, which has value $17$, and the sum of squares is $3489$.

A slightly different way to look at the second part of the solution is to note that since each of the $a_i$ must be at least $10$, we can create an auxiliary sequence $b_1, b_2, \ldots, b_{18}$ with $b_i = a_i - 10$, hence $b_i \in [0; 10]$ and the constraint on them is $$\sum_{i=1}^{18} b_i = 57.$$  Then the same reasoning as before gives five $b_i$ equal to $10$, and one $b_i$ equals $7$.
