Prueba de una desigualdad que parece intuitivo

Question

Estoy en busca de una corta prueba de la siguiente declaración:

Deje $x_1 \ge \cdots \ge x_n \ge 0$ y deje $0 \le a_1,\dots,a_n \le 1$. Si $\sum_{k=1}^n a_k \le m$ para algunos entero$m$, $$\sum_{k=1}^n a_k x_k \le \sum_{k=1}^m x_k.$$

Mi intuición es que los pesos $a_1,\dots,a_n$ puede ser "redistribuir" o "desplazado" hacia adelante, de modo que $a_k=0$$k>m$. No es demasiado duro para convertir esto en una prueba por inducción que implementa un algoritmo. Pero una rigurosa prueba termina siendo bastante larga, aunque la declaración no parece sencillo.

Alguien ha visto esto antes, y es que hay un menor (posiblemente menos algorítmico) enfoque?

Answer 1

Alineación

Answer 2

Creo que he encontrado una prueba corta con la idea en Comentario de Rahul:

\begin{align} \sum_{k=1}^n x_k a_k &= \sum_{k=1}^{n-1} (x_k-x_{k+1}) \sum_{j=1}^k a_j + x_n\sum_{j=1}^n a_j \\ &= \sum_{k=1}^{m} (x_k-x_{k+1}) \sum_{j=1}^k a_j + \sum_{k=m+1}^{n-1} (x_k-x_{k+1}) \sum_{j=1}^k a_j + x_n\sum_{j=1}^n a_j \\ &\le \sum_{k=1}^{m} (x_k-x_{k+1})k + \sum_{k=m+1}^{n-1} (x_k-x_{k+1})m + x_n m \\ &= \sum_{k=1}^n x_n \end {Alinee el}

Answer 3

Vamos a suavizar los valores de $a_i$ para obtener el obligado.

Reemplace$(a_k,a_{k+1})$$(\min(1,a_k+a_{k+1}), \max(0, a_k+a_{k+1}-1))$.

A continuación, nos fijamos en los términos que se vean afectados.

$$(\min(1,a_k+a_{k+1})x_k+\max(0, a_k+a_{k+1}-1)x_{k+1})-(a_kx_k+a_{k+1}x_{k+1})\\ =\min(1-a_k,a_{k+1})x_k+\max(-a_{k+1}, a_k-1)x_{k+1}\\ =\min(1-a_k,a_{k+1})x_k-\min(1-a_k,a_{k+1})x_{k+1}\\ =\min(1-a_k,a_{k+1})(x_k-x_{k+1})\geq0$$

Por lo tanto, esto aumenta el valor de la mano izquierda.

Hacemos esto de reemplazo hasta que esto no se puede cambiar el $a_i$. En ese caso, tenemos para todos los $k$, $a_k=1$ o $a_{k+1}=0$.

Tome la primera a la $k$ tal que $a_{k+1}=0$, aumentar el$a_k$$1$. Es fácil ver aquí, $k=m$ si $m$ asume que es el mínimo valor posible. Ahora, el lado izquierdo es igual a la del lado derecho, y hemos terminado.