2
$\begingroup$

Let $m,n \in \mathbb{N}$ and $m \geq n \geq 2$ and $x_1,x_2,...x_n \in \mathbb{N}_{\geq 1}$ such as $x_1+x_2+...+x_n=m$. Find $\min P$ with $P= \sum_{i=1}^{n} x_i^2.$

$\endgroup$

closed as off-topic by user9072, fedja, Stefan Kohl, Franz Lemmermeyer, Felipe Voloch Nov 1 '15 at 21:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Community, fedja, Franz Lemmermeyer, Felipe Voloch
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Where does this come from? And what do you mean by "find". Obviously one can try all the possibilities... $\endgroup$ – Igor Rivin Nov 1 '15 at 13:59
  • 7
    $\begingroup$ Won't the minimum simply be attained by taking the $x_i$ to be as close to one another as possible. So take some of them equal to $\lfloor m/n\rfloor$ and the others equal to $\lceil m/n\rceil$ to make the sum equal to $m$. $\endgroup$ – Joe Silverman Nov 1 '15 at 14:02
  • $\begingroup$ Solve this using Calculus Lagrange multipliers. The solution will be Joe's solution. $\endgroup$ – Daniel Parry Nov 1 '15 at 14:48
  • 3
    $\begingroup$ So, to be specific, $$P=q^2n+(2q+1)r$$ where $m=nq+r$ with $0 \le r \le m-1.$ The results from taking $r$ of the $x_i$ to be $q+1$ and the remaining $n-r$ to be $q.$ $\endgroup$ – Aaron Meyerowitz Nov 1 '15 at 15:31
8
$\begingroup$

This is a low-tech explanation of Joe Silverman's comment (but see also Geoff Robinson's response).

Proposition. The minimum is attained when the variables differ by at most $1$, i.e. when each $x_i$ is either $\lfloor m/n\rfloor$ or $\lceil m/n\rceil$.

Proof. If $x_i-x_j\geq 2$, say, then replacing $x_i$ (resp. $x_j$) by $x_i-1$ (resp. $x_j+1$) yields a better $n$-tuple, because $$(x_i-1)+(x_j+1)=x_i+x_j\qquad\text{but}\qquad (x_i-1)^2+(x_j+1)^2<x_i^2+x_j^2.$$

Remark. Note that the proposition determines a unique $n$-tuple for the minimum, namely the number of $\lfloor m/n\rfloor$'s and $\lceil m/n\rceil$'s is determined by the residue of $m$ modulo $n$.

$\endgroup$
  • 1
    $\begingroup$ Clean,and better than what I said! $\endgroup$ – Geoff Robinson Nov 1 '15 at 15:40
4
$\begingroup$

It is hard to find a precise answer, since there are some choices of $m,n$ which are easier than others . Lagrange's identity gives $\left( \sum_{i} x_{i}\right)^{2} + \sum_{i<j} (x_i -x_j)^{2} = n P$, which is relevant.

$\endgroup$
1
$\begingroup$

This is a quadratic integer linear programming problem, see this 2014 paper (by Christian Bliekú, Pierre Bonami , and Andrea Lodi) for a survey of what is known. (this problem is positive definite, so not as hard as the hardest case).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.