# What is the minimum of this expression

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$.

• 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. – Rory Daulton Feb 27 '16 at 0:21
• 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? – Steve Feb 27 '16 at 0:28
• OK, I see you have done some work, I'll retract my vote to close the question. – Rory Daulton Feb 27 '16 at 0:29

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.