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$.

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

I think it can be solved with a simple algorithm:

  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$
  3. Repeat from point 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$.

The final solution is thus what @kamran was guessing.


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.