Cuál es el mínimo de esta expresión

Question

Si $x_i\in [-1,1]$ , $i=1, \cdots, 2015$ ¿Cuál es el mínimo de $x_1x_2+x_2x_3+\cdots+x_{2014}x_{2015}+x_{2015}x_1$ ?

Mi intento (caso i=3): $x_1x_2+x_2x_3+x_3x_1=x_1(x_2+x_3)+x_2x_3$ . Si $x_2+x_3\ge 0$ , entonces tomamos $x_1=-1$ , por lo que tenemos que minimizar $-(x_2+x_3)+x_2x_3=x_2(x_3-1)-x_3$ . Obviamente, el mínimo se alcanza cuando $x_2=1$ (independientemente de $x_3$ ahora), por lo que en este caso, el mínimo es $-1$ . Si $x_2+x_3<0$ , entonces tomamos $x_1=1$ , por lo que tenemos que minimizar $(x_2+x_3)+x_2x_3=x_2(x_3+1)+x_3$ . Obviamente, el mínimo se alcanza cuando $x_2=-1$ (independientemente de $x_3$ ), por lo que en este caso, el mínimo es $-1$ . Conclusión: cuando $i=3$ el mínimo de la expresión es $-1$ .

Answer 1

La función objetivo es lineal en cada $x_i$ por lo que el mínimo tiene que producirse en un límite, es decir, cuando $x_i \in \{-1, 1\}$ . Así que sólo tenemos que comprobar un conjunto finito (aunque grande) para el mínimo (que también debe existir porque el conjunto es finito).

Ahora $x_i x_j$ tiene su valor mínimo de $-1$ por lo que para una suma de $2015$ tales términos, el mínimo no puede ser inferior a $-2015$ . Además, $-2015$ no se puede lograr, lo que se puede demostrar de la siguiente manera:

Supongamos que es posible conseguirlo, por lo que todos los términos sumados son $-1$ . WLOG dejar $x_1=-1$ (ya que invertir los signos de todas las variables simultáneamente no cambia la función). Utilizando sucesivamente $x_kx_{k+1}=1$ obtenemos $x_2 = 1, x_3 = -1, \cdots x_k = (-1)^k$ como única posibilidad. Sin embargo, esto deja el último término positivo, lo que es una contradicción.

Una suma de números Impares de números Impares tiene que ser impar, así que la siguiente mejor posibilidad es $-2013$ que, de hecho, se consigue con $x_k = (-1)^k$ Así que este es el mínimo.