# Minimize the power function with given constraint.

Let $x_1+x_2+\cdots+x_n=m$ then minimize the function

$f(x_1,x_2,\cdots,x_n)=\sum_{i=1}^n (x_i)^{\alpha}$

where $x_i,m,n$ are positive integers and $\alpha>1$.

My attempt: I applied the Lagrange's multiplier and found that minimum is obtained when all $x_i's$ are equal, but I am unable to prove that these $x_i's$ are integers.

My observation: I think the minimum is obtained when all $x_i's$ are almost equal i.e. $|x_i-x_j|\le1, i,j=1,2,\cdots,n$.

• I got all $x_i=m/n, \;i=1,2,\ldots,n$ thus $x_i$ are integers only if $n$ divides $m$ – Raffaele Sep 3 '17 at 20:34
• Did you forget to require the $x_i$ to be non-negative integers? – kimchi lover Sep 3 '17 at 21:08
• Oh! yes $x_i$ are non negative integers. – kamran jamil Sep 4 '17 at 2:10

1. Take two $x_i$,$x_j$, if they exist, such that $x_i-x_j>1$
2. Replace them, respectively, with $x_i-1$ and $x_j+1$
We'll show that the algorithm is finite and that it makes $S=\sum_{k=1}^n x_k^{\alpha}$ smaller at each run. Let's demonstrate the latter: after the substitution, we still have $x_1+x_2+⋯+x_n=m$ and, since $x^\alpha$ is a strictly convex function and $(x_i,x_j)$ majorizes $(x_i-1,x_j+1)$, we can apply Karamata's inequality to obtain $$(x_i-1)^{\alpha}+(x_j+1)^{\alpha} < x_i^\alpha+x_j^\alpha$$ Hence, $$S'=\sum_{k=1,k\neq i,j}^n x_k^{\alpha}+(x_i-1)^{\alpha}+(x_j+1)^{\alpha} < \sum_{k=1,k\neq i,j}^n x_k^{\alpha}+x_i^\alpha+x_j^\alpha=S$$ For the first statement, consider the quantity $I=\sum_{k=1}^n x_k^2$: applying what we found before with $\alpha=2$, we have that $I$ gets strictly smaller at each run, it is integer and it cannot reach 0, for the initial conditions on the $x_k$, so the algorithm must terminate at some point.
Last but not least, we need to show that, independently from the choice of $x_i$ and $x_j$, the algorithm will give us a fixed $n$-uple, without regard to the order of the $x_k$s. The algorithm can terminate if and only if, for a certain integer $t$, all the $x_k$s are either equal to $t$ or to $t+1$. Let's say there are $h$ of them (with $h \leq n$) which are equal to $t+1$ and there are $n-h$ equal to $t$: we have that $$m=h(t+1)+(n-h)t=nt+h$$ That is the Euclidean division between $m$ and $n$, which is unique. Hence, if we denote with $q$ its quotient and with $r$ its remainder, the only possible minimal $n$-uple is that composed by $r$ numbers equal to $q+1$ and the others equal to $q$.