Si$\sum_{i=1}^n a_n=0$, entonces puede encontrar un "buen" pedido de$a_i$.

Question

Estoy tratando de demostrar (o refutar, pero creo que es verdad y me sorprendería si alguien se las arreglaría para refutarla) un pequeño teorema.

Dado un array de números reales $A=[a_1,a_2,...,a_n]$ tal que $\sum_{i=1}^n a_i=0$, quiero demostrar que hay un reordenamiento (a través de la rotación, de la permutación) de los elementos de la matriz, de tal manera que nunca vamos a llegar a un negativo temporal de la suma.

Es un poco difícil y el inglés no es mi lengua nativa, voy a tratar de explicar con un ejemplo.

Echemos un vistazo a la matriz $A=[1,-6,2,3]$. si sumamos los elementos obtenemos $1+(-6)+2+3=0$. Pero $1+(-6)=-5$. Así que no es un buen orden. Porque mientras que la suma de todos los elementos, hemos tenido un temporal suma que es negativo.

Sin embargo, si hacemos girar la matriz a $A'=[2,3,1,-6]$, luego tenemos a $2+3+1+(-6)=0$. Y en ningún lugar en este resumen se hicieron tenemos una suma negativa.

Nota muy importante:

Cuando me dicen que el reordenamiento no me refiero a la permutación. Me refiero a la rotación solamente. si nuestra matriz original se $A=[1,-6,2,3]$ $A'=[3,2,1,-6]$ no es válido reordenación porque no se puede rotar $A$ y llegar a $A'$. Me refiero a la circular de rotación solamente. No permutación.

Lo que traté de hacer:

La primera cosa que me vino a la mente es la inducción. Es sencillo ver que si $a_1+a_2=0$, luego tenemos a $3$ opciones de: $a_1=a_2=0$, en cuyo caso la rotación que va a hacer, o $a_1>0>a_2$ o $a_2>0>a_1$. En cualquier caso, es posible encontrar una rotación que no habrá negativo temporal de la suma.

Pero, ¿cómo podemos generalizar? Supongamos que yo pueda encontrar un buen arreglo para un array con $k$ elementos. Qué significa que puedo encontrar a un buen arreglo para un array con $k+1$ elementos?

Otra idea sería asumir que no hay tal acuerdo y, a continuación, esperamos llegar a una contradicción a la suma total sea cero. He fallado para llegar a una contradicción.

Answer 1

Definir $S_0=0$ y considerar las sumas parciales $S_k:=\sum_{i=1}^k a_i$. Deje $k^*$ ser cualquier valor de $k$ donde $S_k$ es mínimo. Si $k^*=n$,$k^*=0$. Entonces la rotación $[a_{k^*+1}, a_{k^*+2}, \ldots,a_{k^*}]$ debe satisfacer a su criterio.

Para ver esto de manera gráfica, crear una segunda copia de $[a_1,\ldots,a_n]$ y anexar a la original, luego de la parcela $S_k$ vs $k$ para esta nueva secuencia de tener $2n$ elementos: vamos a tener $S_0=S_n=S_{2n}=0$. La rotación se define anteriormente corresponde a mover el eje horizontal a la línea de $y=S_{k^*}$, con el origen de mudarse a $(k^*, S_{k^*})$.

Answer 2

Por inducción deje $A=[a_1,\cdots,a_{n+1}]$

1. Si para cada una de las $i$ tenemos $a_i\leq 0$ o $a_i+a_{i+1}\leq 0$ (con la notación $a_{n+2}=a_1$), entonces se puede demostrar que para todos los $i$ $a_i=0$ o $a_i+a_{i+1}=0$:
   • si existe alguna $i_0$ tal que $a_{i_0}=0$, entonces usted puede aplicar inducción sobre el resto debido a una diferencia en $0$ no cambia nada
   • De lo contrario,$i$ $a_i\neq 0$ a continuación, $a_i+a_{i+1}=0$ por cada $i$ y esto implica que $a_i=(-1)^ia_1$ y usted puede empezar por un término positivo y listo.
2. De lo contrario, no existe un índice $i_0$ tal que $a_{i_0}\geq 0$ $a_{i_0}+a_{i_0+1}\geq 0$ en este cas aplicar la hipótesis de inducción: $$\left[a_1,\cdots,a_{i_0-1},a_{i_0}+a_{i_0+1},a_{i_0+2},\cdots, a_{n+1}\right] $$