Finding maximum value of squared sum

Question

Given k positive integers such that $x_1+x_2+...+x_k=n$, find the maximum possible value of $x_1^2+x_2^2+...+x_k^2$.

I know we can find its minimum value using Cauchy-Schwarz inequality, but is there any way to find its maximum value?

Answer 1

Here is a way without Karamata, though that's an inequality well worth the effort studying.

As the number of possibilities for $x_i$ is finite, there must be at least one possibility which gives a maximal value. Further, we note that in a maximal solution, there can only be one distinct value other than $1$ that the variables can take.

Proof: Suppose $a,b>1$ are present in a maximal solution. Then we may replace $a, b$ with $a+b-1, 1$, as the sum remains the same and $(a+b-1)^2+1 > a^2+b^2 \iff (a-1)(b-1)> 0$.

It immediately follows that a maximal solution is having all variables $1$, except possibly one variable which takes the value $n-k+1$.

Answer 2

As $t\mapsto t^2$ is convex, using Karamata’s Inequality, the maximum is when all except one variable is zero, as $(n,0,0,\dots,0)\succ (x_1,x_2,x_3,\dots,x_k)$.

In the new version with only positive integers, similarly we must have $(n-k+1,1,1...,1)\succ (x_1,x_2,..,x_k)$ and hence the maximum must be $(n-k+1)^2+k-1$.