2
$\begingroup$

If $x_i\in [-1,1]$, $i=1, \cdots, 2015$, what is the minimum of $x_1x_2+x_2x_3+\cdots+x_{2014}x_{2015}+x_{2015}x_1$?

My attempt (i=3 case): $x_1x_2+x_2x_3+x_3x_1=x_1(x_2+x_3)+x_2x_3$. If $x_2+x_3\ge 0$, then we take $x_1=-1$, so we need to minimize $-(x_2+x_3)+x_2x_3=x_2(x_3-1)-x_3$. Obviously, the minimum is attained when $x_2=1$ (regardless of $x_3$ now), so in this case, the minimum is $-1$. If $x_2+x_3<0$, then we take $x_1=1$, so we need to minimize $(x_2+x_3)+x_2x_3=x_2(x_3+1)+x_3$. Obviously, the minimum is attained when $x_2=-1$ (regardless of $x_3$), so in this case, the minimum is $-1$. Conclusion: when $i=3$, the minimum of the expression is $-1$.

$\endgroup$
  • $\begingroup$ What have you tried so far, and just where are you stuck? This is not a homework-answering site: we want to see that you have put significant work into the problem. $\endgroup$ – Rory Daulton Feb 27 '16 at 0:21
  • $\begingroup$ I was able to find the minimum of $x_1x_2+x_2x_3+x_3x_1$... I don't know how to extend the idea for larger indices? $\endgroup$ – Steve Feb 27 '16 at 0:28
  • 1
    $\begingroup$ OK, I see you have done some work, I'll retract my vote to close the question. $\endgroup$ – Rory Daulton Feb 27 '16 at 0:29
3
$\begingroup$

The objective function is linear in each $x_i$, so the minimum has to occur at a boundary, i.e. when $x_i \in \{-1, 1\}$. So we need to only check a finite (albeit large) set for the minimum (which must also exist because the set is finite).

Now $x_i x_j$ has its minimum value of $-1$, so for a sum of $2015$ such terms, the minimum cannot be lower than $-2015$. Further, $-2015$ itself cannot be achieved, which can be shown as follows:

Suppose it is possible to achieve this, so all terms summed are $-1$. WLOG let $x_1=-1$ (as flipping the signs of all variables simultaneously does not change the function). Successively using $x_kx_{k+1}=1$, we get $x_2 = 1, x_3 = -1, \cdots x_k = (-1)^k$ as the only possibility. However this leaves the last term positive, which is a contradiction.

A sum of odd number of odd numbers has to be odd, so the next best possibility is $-2013$, which in fact is achieved with $x_k = (-1)^k$, so this is indeed the minimum.

$\endgroup$
  • $\begingroup$ “A sum of odd number of odd numbers has to be odd” this is important here. Thanks. $\endgroup$ – Steve Feb 28 '16 at 12:21

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.