0
$\begingroup$

Given $n$ positive integers $x_i,i=1,2,\ldots,n,$ such that $$x_1+x_2+\cdots+x_n=q$$ The sum of their cubes is $$x_1^3+x_2^3+\cdots+x_n^3$$

With the help of some examples I found that sum of cubes is minimum when numbers are almost equal ($|x_i-x_j|\le1$). But I am unable to prove this. Please help.

$\endgroup$
  • $\begingroup$ Have you tried Lagrange multipliers? If you put $g(x,y,\lambda)=\sum_{i} (x_i^3) - \lambda\left(\sum_i (x_i) - q \right)$ you will obtain that the minimum happens exactly when $\lambda=\frac{x_i}{3}$ and $x_i=\frac{q}{n}$ for all $i\leq n$. $\endgroup$ – Darío G Aug 24 '16 at 10:19
  • 1
    $\begingroup$ Do you mean for the $x_i$ to be integers (as the condition $|x_i - x_j| \leq 1$ seems to suggest)? $\endgroup$ – Travis Willse Aug 24 '16 at 10:21
  • $\begingroup$ Yes, $x_i$ are integers. $\endgroup$ – Camran Aug 24 '16 at 18:49
  • $\begingroup$ @Wore I think $\lambda=\frac{x_i^2}{3}$??? $\endgroup$ – Camran Aug 24 '16 at 18:57
  • $\begingroup$ @Camran Yes, $\lambda=\frac{x_i^2}{3}$. Although it does not matter anymore since the $x_i$ have to be integers. $\endgroup$ – Darío G Aug 25 '16 at 12:42
1
$\begingroup$

Here I assume, as the given condition suggests, that the $x_i$ must be integers.

Hint Suppose you have two numbers, $x_i, x_j$ in a partition of $q$ into positive integers such that $|x_i - x_j| > 1$, and w.l.o.g. suppose $x_i > x_j$. What happens to the sum of cubes if you replace $x_i$ with $x_i - 1$ and $x_j$ with $x_j + 1$ (which in particular gives another partition of $q$)?

$\endgroup$
0
$\begingroup$

You can use the power means inequality: if $x_1, x_2,\dots, x_n$ are positive numbers, their $p$-th power mean is $$M_p(x_1,x_2,\dots,x_n)=\Biggl(\frac{x_1^p+x_2^p+\dots+x_n^p}n\Biggr)^{\!\tfrac1p}.$$

The *power means inequality states that

if $p<r$, then $\;M_p(x_1,x_2,\dots,x_n)\le M_r(x_1,x_2,\dots,x_n) $, and both means are equal if and only if for each $1\le i,j\le n$, $\;x_i=x_j$.

Apply this inequality to the arithmetic mean $ (p=1)$ and the cubic mean $(r=3)$ to obtain $$\sum_{i=1}^n x_i^3 \ge \frac{q^3}{n^2}$$ Equality happens when all $x_i$s are equal.

$\endgroup$
0
$\begingroup$

Theorem: If p is a positive integer greater than 1 and x_i are elements of {0, 1 , 2 , 3, …, q} i goes from 1 to n, such that the sum of the n x_i's is q, then the sum of (x_i)^p from 1 to n is minimized when the x_i's are within at most 1 of each other.

Lemma: for 0 <= a <= 1/2, g(a) = (1/2 + a)^p + (1/2 - a)^p is strictly monotonically increasing. This is because g(a) is a polynomial with non-negative coefficients.

Proof: Take n and d both positive integers and d is greater than 1.

n^p + (n+d)^p = (2n+d)^p [(n/(2n+d))^p +((n+d)/(2n+d))^p]

n^p + (n+d)^p = (2n+d)^p g(d/[2(2n+d)]) where g is define in the lemma. Note: we can add to n as we subtract from n + d until we are within 1 (if both are odd) or zero (if both are even) without effecting the denominator, 2(2n+d), and minimize the sum. Apply repeatedly. Q.E.D.

$\endgroup$

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.