Deje $x_1,x_2,\ldots,x_n$ $n$ sin números negativos ($n>2$) con una suma fija $S$.
¿Cuál es el máximo de $x_1x_2+x_2x_3+\cdots+x_nx_1$?
Respuestas
¿Demasiados anuncios?
Lissome
Puntos
31
Fijo Este es carlop la solución de simplifyid, así que por favor upvote que de la solución.
Para $n=3$ tenemos por C-S o reordenamiento
$$x_1x_2+x_2x_3+x_3x_1 \leq x_1^2+x_2^2+x_3^2$$
La adición de $2(x_1x_2+x_2x_2+x_3x_1)$ tenemos
$$3(x_1x_2+x_2x_3+x_3x_1) \leq (x_1+x_2+x_3)^2 \,.$$
Para $n \geq 4$ incluso hemos
$$x_1x_2+x_2x_3+....+x_{2k}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$
desde cualquier término en el lado izquierdo aparece en el lado derecho.
Así
$$\sqrt{x_1x_2+x_2x_3+....+x_{2k}x_1} \leq \frac{x_1+x_3+..+x_{2k} + x_2+x_4+...+x_{2k-1}}{2} =\frac{S}{2}$$
Para $n \geq 4$ impar
Desde el LHS suma es cíclica, es decir, sin pérdida de generalidad podemos suponer que $x_{2k+1}$ (de lo contrario reordenar) es el menor plazo. A continuación, $x_{2k+1} \leq x_4$ (aquí es donde necesitamos $n \geq 4$.)
$$x_1x_2+x_2x_3+....+x_{2k+1}x_1 \leq x_1x_2+x_2x_3+....+x_{2k}x_{2k+1}+x_{4}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$
De nuevo POR AM_GM usted obtener
$$\sqrt{x_1x_2+x_2x_3+....+x_{2k+1}x_1} \leq \frac{x_1+x_3+..+x_{2k+1} + x_2+x_4+...+x_{2k}}{2} = \frac{S}{2} $$
Tengo que resolver esto en 3 partes. Primero para $n=3$, $n=4$ y finalmente para $n>4$.
Para $n=3$ podemos tomar un tranformation $x'_1=x'_2=(x_1+x_2)/2$ y $x'_3=x_3$. $\sum x_i$ permanece fija mientras que $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}} = (x_1+x_2)^2/4-x_1*x_2 = (x_1^2+2x_1x_2+x_2^2)/4-x_1*x_2 = (x_1^2-2x_1x_2+x_2^2)/4 = (x_1-x_2)^2/4$
que es $>0$ si $x_1$ difiere de $x_2$.
Así que una solución óptima debe tener los primeros dos términos de la igualdad (de lo contrario podemos aplicar esta transformación y obtener un valor más alto), pero usted puede cambiar los términos, por lo que deben ser todos iguales a $S/3$, para un total suma de $S^2/3$.
Para $n=4$ la transformación $x'_1=x_1+x_3$, $x'_3=0$ no cambia el resultado, por lo que tener una solución óptima, la suma de los pares y los impares términos, y el problema es encontrar el máximo de $(\sum x_{odd})*(\sum x_{even})$, que se maximiza si ambos términos son iguales a $S/2$, para un total de $S^2/4$.
Para $n>4$, tengo que probar este lema primera:
Para $n>4$, hay al menos una configuración óptima que tiene al menos un índice de $i$ tal que $x_i=0$
Tomar una configuración que es óptima y que cada $x_i>0$$x_1 = max(x_i)$.
Ahora utilice la siguiente transformación: $x'_2=x_2+x_4$, $x'_4=0$. $\sum x_i$ sigue siendo la misma, pero se $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}}=x_1*(x_2+x_4)+(x_2+x_4)*x_3+\sum_{i>4}{x_i*x_{i+1}}-\sum{x_i*x_{i+1}} = x_1*x_4-x_4*x_5 = x_4*(x_1-x_5) = x_4*(max(x_i)-x_5) \geq x_4*(x_5-x_5) = 0$
Así que tenemos otra solución óptima con un $0$.
Dado que al menos una solución óptima contiene un $0$ por cada $n>4$, el valor máximo de $\sum{x_i*x_{i+1}}$ debe ser no el aumento de $n$ (de lo contrario podemos tener una solución para $n$ $0$ dentro de, quitar ese $0$, y de obtener una mayor solución para $n-1$).
Ahora bien, el valor de la suma debe ser $\leq S^2/4$, pero tomando las $x_1=x_2=S/2$ da esa suma, por lo que la configuración es óptima, por una suma de $S^2/4$.
Esto demuestra que el máximo es de $S^2/3$ si $n=3$ $S^2/4$ lo contrario.
No estoy satisfecho con esta respuesta, porque se descompone a una gran cantidad de análisis de casos. Todavía estoy con la curiosidad de ver una simple prueba (o uno que requiere menos espacio..).
user28956
Puntos
6
Este debe ser un comentario, pero no tengo la reppts.
Considere la posibilidad de $x^n-Sx^{n-1}+e_2x^{n-2}+\ldots+(-1)^ne_n=\prod_{i=1}^n(x-x_i)$, reformular, muy equivocadamente, que la cuestión sobre la búsqueda de la máxima $e_2$.
Deje $x_i=\frac{S}{n}\forall i$. A continuación,$(x-\frac{S}{n})^n=x^n-n(\frac{S}{n})x^{n-1}+{n\choose 2}(\frac{S}{n})^2x^{n-2}+\ldots$, por lo que podemos llegar tan alto como $\frac{n-1}{2n}S^2$, tendiendo a pero siempre menor que $\frac{S^2}{2}$ en general.
Esto es$\frac{S^2}{3}$$n=3$, e $\frac{3}{8}S^2>\frac{S^2}{4}$$n=4$.
Edit: $e_2\geq x_1x_2+x_2x_3+\ldots+x_nx_1$, no necesariamente iguales. De mantenerse, como alguien puede hacer el mismo error.
dineshdileep
Puntos
3858
Esto es INCORRECTO. Se mantiene aquí para que nadie más va a hacer el mismo error.
La respuesta es $\frac{S^2}{4}$. Hay $nC_2$ respuestas que le dan a este valor. Todos ellos son las permutaciones posibles de los vectores $x=[\frac{S}{2},\frac{S}{2},0,0,\dots,0]^T$. Tuve la oportunidad de probar este ya que yo ya sabía que la solución de los comentarios de los usuario de N. S. de usuario Ross Millikan respuesta. Así que el crédito es para él. Voy a demostrar los conceptos de usar $5 \times 5$ matriz. El resultado es fácilmente generalizable.
Definir el vector de columna $x=[x_1,x_2,x_3,x_4,x_5]^T$. A continuación, la función en cuestión puede ser escrito como \begin{align} f(x)=x_1x_2+x_2x_3+x_3x_4+x_5x_1=x^TQx \end{align} donde \begin{align} Q=\begin{bmatrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 & 0 \\\end{bmatrix} \end{align} Tenga en cuenta que $Q$ es una permutación de la matriz y a los no-simétrica. Para todos los no-simétrica matriz$Q$, $x^TQx=x^TCx$ donde $C=(1/2)*(Q+Q^T)$ e es una matriz simétrica. Así tenemos \begin{align} f(x)=x^TCx \end{align} También tenga en cuenta que \begin{align} C=\begin{bmatrix}0 & .5 & 0 & 0 & .5 \\ .5 & 0 & .5 & 0 & 0 \\0 & .5 & 0 & .5 & 0 \\0 & 0 & .5 & 0 & .5 \\.5 & 0 & 0 & .5 & 0 \\\end{bmatrix} \end{align} Tenga en cuenta que las diagonales en ambos lados de la diagonal principal son todos .5 y valores en la parte superior derecha y la esquina inferior izquierda también se $.5$. Ahora $C$ es una matriz simétrica y, por tanto, \begin{align} \lambda_{min}(C)\leq x^TCx \leq \lambda_{max}(C)\text{ %#%#% %#%#%} \end{align} Ahora $\quad \forall x,$ es doblemente estocástica de la matriz (columna de la suma de la fila y la suma es uno). Por lo $x^Tx=1$ es siempre un valor propio. Lo que es más importante, $C$ es una irreductible primitivo de la matriz. Esto se desprende de perron-frobenius de la teoría. Por lo tanto $1$ es el mayor autovalor. Ahora observe que el$C$$1 $. También dispone de unidad de la norma. De hecho, todas las permutaciones de este vector (todos los posibles reordenamientos de sus entradas), tiene el mismo valor para $x=[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0,0,0]^T$ y todos ellos tienen la unidad de la norma. Esta $f(x)=x^TCx=1$ siempre es maximizada en esta unidad-vectores de dirección. Ahora $f(x)$ no es un requisito. Pero, la suma de sus elementos debe ser $f(x)$. De lo anterior, el debate, se puede concluir que todos los elementos excepto dos de los vectores $x^Tx=1$ debe ser igual a cero y el cero de las entradas debe ser igual si $S$ es para ser maximizada. Por simetría, es ver a que todas las permutaciones de los vectores $x$ es el único conjunto de vectores que satisfacen la suma condición mientras dando el máximo de $f(x)$.
