2
$\begingroup$

"Given positive integers $k,n$ and nonnegative integers $x_1,x_2,...,x_n$ satisfying $x_1 + x_2 + \dots+ x_n = k$, is it true that $x_1^2+x_2^2+\dots+x_n^2$ is minimized if and only if $|x_i-x_j|\leq1$ for all $i,j$ ?"

Hello. I am reading one paper where I am not sure how to deal with this part. So basically, we want to distribute $k$ identical objects into $n$ identical boxes, and minimize the sum of squares of the numbers of objects in the boxes. So I denote the number of objects by $x_i$ and formulate the problem above. It is claimed that when the distribution is as even as possible, then the sum of squares of $x_i$'s is minimized.

This does look intuitively true (or does it?), but I am not sure how to prove this if it is true.

This feels like a constrained integer least square problem but I never studied it. What I tried is to use AM-QM inequality to have a bound by first changing the above absolute value into $(x_i - x_j)^2\leq 1$ and then expanding this and summing all over the pairs, but I only get a lower bound $\frac{k^2}{n}$ and an upper bound $\frac{k^2}{n} + \frac{n-1}{2}$. Perhaps pigeonhole then can be used to find some pairs of $i,j$ with $|x_i - x_j|\geq2$ for some pair, but I am still stuck.

Trying to be exact, the most even distribution must be like $k = (q+1)r+q(n-r)$ where $q,r$ are the quotient,remainder in the division algorithm. I could not proceed any further. In general, I think instead of finding the exact minimum, we only need to show that if $|x_i - x_j|\geq 2$, then the sum is greater than when we use the most even distribution. This way the two directions of the statement are handled simultaneously.

Any suggestion is appreciated. Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint

Suppose that $x \ge y +2$ are integers. Then $$(x-1)^2 + (y+1)^2= x^2+y^2-2(x-y)+2 \lt x^2+y^2$$

If the difference between the elements of an ordered pair of integers is greater or equal to two, you can find an ordered pair having the same sum, a difference decreased by two and such that the sum of their squares is less than the initial sum of squares.

Based on that fact, you can derive a proof by induction of your result.

$\endgroup$
1
  • $\begingroup$ @user10354138 Yes for sure! Typo corrected. $\endgroup$ Aug 12, 2021 at 11:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .