MHB How to Minimize the Sum of Squares with Given Distinct Elements?

[anemone]

Here is this week's POTW:

-----

Let $x_1,\,x_2,\,x_3,\,x_4,\,x_5,\,x_6,\,x_7$ and $x_8$ be distinct elements in the set $\{-7,\,-5,\,-3,\,-2,\,2,\,4,\,6,\,13\}$.

What is the minimum possible value of $(x_1+\,x_2+\,x_3+\,x_4)^2+(x_5+\,x_6+\,x_7+\,x_8)^2$?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to the following members for their correct solution::)

1. Ackbach
2. Opalg
3. lfdahl
4. kaliprasad
5. greg1313

Solution from Opalg:

Spoiler

The minimum value is $34$. There is more than one way to achieve this, for example $$(-7+2+4+6)^2 + (-5-3-2+13)^2 = 5^2 + 3^2 = 25 + 9 = 34.$$

To see that no smaller total is possible, notice that the sum of all eight numbers is $8$. So if $X = x_1+x_2+x_3+x_4$ and $Y = x_5+x_6+x_7+x_8$ then $X+Y = 8$. If either $X$ or $Y$ is $6$ or greater then its square is (at least) $36$, which is already too large. So the only possibilities for achieving the minimum are $\{X,Y\} = \{5,3\}$ as in the above example, or $X=Y=4.$

To see that the case $X=Y=4$ cannot occur, we may as well assume that $13$ is one of the numbers in $X$. If $X$ contains no other positive numbers, then it must contain three of the negative numbers with sum $-9.$ But it is easy to see that this cannot happen. (If we leave out $-7$ from the set $\{-7,-5,-3,-2\}$ then the sum of the other three numbers is $-10$. If we leave out $-5$ then the sum is $-12$. And so on.)

If $X$ contains another positive number besides $13$ then that number had better be $2$. (If it is $4$ or $6$ then the positive numbers in $X$ will sum to $17$ or $19$, and there is no way for the two negative numbers in $X$ to bring the sum of all the numbers in $X$ down to $4$.) But if $X$ contains $13$ and $2$ (with sum $15$) then the two negative numbers in $X$ must have sum $-11$, and there is no way to achieve that.

Thus $X=Y=4$ is not achievable, and the minimum only occurs when $\{X,Y\} = \{5,3\}$.

Alternate solution from Ackbach:

Spoiler

This is a problem tailor-made for a brute force search algorithm: simply generate all possible permutations of the set, compute the function for each permutation, and see which one gives you the best outcome. I've implemented this solution in LabVIEW as follows:

https://www.physicsforums.com/attachments/6029

This VI is the top-level code that calls the permutation generator and processes each one.

https://www.physicsforums.com/attachments/6030

This VI generates all the possible permutations using Heap's algorithm.

The answer is 34, the output from the set $\{2,-7,6,4,-3,-5,-2,13\}$.

Suggested model solution:

Spoiler

Note that the sum of the elements in the set is 8. Let $a=x_1+\,x_2+\,x_3+\,x_4$ so $x_5+\,x_6+\,x_7+\,x_8=8-a$.

Then we have

$(x_1+\,x_2+\,x_3+\,x_4)^2+(x_5+\,x_6+\,x_7+\,x_8)^2=a^2+(8-a)^2=2a^2+16a+64=2(a-4)^2+32\ge 34$ as $(a-4)^2> 1$.

34 can be attained by letting $x_1,\,x_2,\,x_3,\,x_4$ be distinct elements in the set $\{-7,\,-5,\,2,\,13\}$.