Sobre la desigualdad $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$
Dado $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ Pruebalo $$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$ Este problema fue propuesto por el nuevo colaborador @ user3458994 y fue cerrado por cinco usuarios. Lo encuentro algo desafiante (no tiene una respuesta inmediata), pero está suficientemente bien planteado y, de hecho, se puede solucionar respondiendo correctamente.
Hay muchas sumas posibles $\sum_{i=1}^n|a_i-b_i|$; de hecho hay$n!$ posibilidades (número de permutaciones del conjunto $\{1,2,\cdots,n\}$). El mínimo para estas sumas es$0$ correspondiente a la permutación de identidad $a_i\rightarrow b_i=a_i$en cuyo caso la desigualdad se verifica trivialmente. Exponemos una de estas sumas teniendo un valor máximo$M$ exactamente igual a $\big\lfloor \frac{n^2}{2}\big\rfloor$. Creí que ninguna otra suma tiene un valor mayor que$M$ en cuyo caso el problema sería falso (¿me equivoco?).
Respuestas
He aquí una respuesta casi inmediata.
Ampliando cada término de $ |a_i - b_i|$ en el correspondiente $\pm (a_i - b_i)$, entendemos eso $$ \sum |a_i - b_i | = \sum c_i i, $$ dónde $c_i \in \{-2, 0, 2 \}$ y $\sum c_i = 0 $.
Nota: esta es una condición necesaria, pero no suficiente. En particular, no todas las combinaciones de$c_i$son posibles a partir del valor absoluto, por lo que posteriormente tendríamos que asegurarnos de que se pueda satisfacer. Sin embargo, tenemos la "suerte" de que esto funcione para nosotros.
Cuando $n=2m$ es par, el máximo de $\sum c_i i $ es $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$.
Esto está satisfecho con$a_i = i, b_i = n+1-i$, entonces es el máximo de $ \sum |a_i - b_i|$.
Cuando $n = 2m+1$ es impar, el máximo de $\sum c_i i $ es $ -2\times 1 -2\times 2 \ldots - 2\times m + 2\times (m+2) + 2\times (m+3) + \ldots + 2 \times (2m+1) = 2m(m+1)$.
Esto está satisfecho con$a_i = i, b_i = n+1-i$, entonces es el máximo de $ \sum |a_i - b_i|$.
Nota: La condición necesaria y suficiente es $ \sum_{i=1}^k c_{n+1-i} \geq 0$ para todos $ 1 \leq k \leq n$. Una vez que se satisface, existe una forma bastante natural de asignar los valores. (Piense en ello).
Ya he dado respuesta en ese post. Lo publicaré nuevamente aquí. Es algo similar a la desigualdad de reordenamiento: cuando$\{a_i\}$ y $\{b_i=i\}$tienen orden opuesto, la suma de la diferencia absoluta alcanza el máximo (podría haber otros casos que también alcancen este máximo) El resto es un cálculo sencillo.
Lema: Si$x>y,z>w$ entonces $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$
WLOG podemos asumir $y\geqslant w$. Entonces$x>w$.
$$|x-w|+|y-z|\geqslant |x-z|+|y-w| \iff x-w+|y-z| \geqslant |x-z|+y-w \\ \iff |x-y|+|y-z|\geqslant |x-z|$$
que se sigue de la desigualdad del triángulo.
WLOG asume $b_i=i$. Entonces del lema la suma de las diferencias absolutas obtiene su valor máximo cuando$a_i$ está disminuyendo, es decir $$\sum_{i=1}^n|a_i-i| \leqslant \sum_{i=1}^n |n+1-2i|.$$
Si $n=2m$, $$\sum_{i=1}^n |n+1-2i|=2(2m-1) + 2(2m-3)+\cdots + 2(1)=2m^2 = \lfloor \frac{n^2}{2} \rfloor.$$
Si $n=2m+1$, $$\sum_{i=1}^n |n+1-2i|=2(2m) + 2(2m-2)+\cdots + 2(0)=2m(m+1) = \lfloor \frac{n^2}{2} \rfloor.\blacksquare$$
Para cualquier permutación, hay algunos $1 \le k \le n$ valores de $i$ dónde
$$a_i - b_i \lt 0 \tag{1}\label{eq1A}$$
Así, el resto $n - k$ valores de $i$ será donde
$$a_i - b_i \ge 0 \tag{2}\label{eq2A}$$
Para simplificar, si es necesario, ajuste los valores de $a_i$ y $b_i$ entonces el $k$ los valores donde \ eqref {eq1A} se mantienen son aquellos donde $1 \le i \le k$. Esto entonces da
$$\begin{equation}\begin{aligned} \sum_{i = 1}^{n}|a_i - b_i| & = \sum_{i = 1}^{k}|a_i - b_i| + \sum_{i = k + 1}^{n}|a_i - b_i| \\ & = \sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) - \sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = 1}^{k}(a_i - b_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = 1}^{n}a_i - \sum_{i = 1}^{n}b_i \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
La última línea viene de $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ así que el último $2$términos de la línea antes de cancelar. En \ eqref {eq3A}, el valor máximo proviene del$b_i$ siendo el más grande permitido $k$ valores, es decir, $n - k + 1 \le b_i \le n$y $a_i$ siendo el mas pequeño permitido $k$ valores, es decir, $1 \le a_i \le k$. Así,
$$\begin{equation}\begin{aligned} 2\sum_{i = 1}^{k}(b_i - a_i) & \le 2\left(\sum_{i = n - k + 1}^{n}i - \sum_{i = 1}^{k}i \right) \\ & = 2\left(\frac{k((n - k + 1) + n)}{2} - \frac{k(k + 1)}{2}\right) \\ & = k(n - k + 1 + n - k - 1) \\ & = 2k(n - k) \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Nota $f(k) = 2k(n - k)$ es una parábola cóncava hacia abajo con un máximo en $k = \frac{n}{2}$. Incluso para$n$, este valor de $k$ es un número entero, con un valor máximo de \ eqref {eq4A} como
$$\begin{equation}\begin{aligned} 2k(n - k) & \le 2\left(\frac{n}{2}\right)\left(n - \frac{n}{2}\right) \\ & = n\left(\frac{n}{2}\right) \\ & = \left\lfloor \frac{n^2}{2} \right\rfloor \end{aligned}\end{equation}\tag{5}\label{eq5A}$$
Por extraño $n$, se logra el mismo valor máximo con $k = \frac{n - 1}{2}$ y $k = \frac{n + 1}{2}$. Usando el primer valor, obtenemos de \ eqref {eq4A} que
$$\begin{equation}\begin{aligned} 2k(n - k) & \le 2\left(\frac{n - 1}{2}\right)\left(n - \frac{n - 1}{2}\right) \\ & = (n - 1)\left(\frac{n + 1}{2}\right) \\ & = \frac{n^2 - 1}{2} \\ & = \left\lfloor \frac{n^2}{2} \right\rfloor \end{aligned}\end{equation}\tag{6}\label{eq6A}$$
Esto muestra que la desigualdad declarada siempre se cumple. Tenga en cuenta que la respuesta de Piquito ofrece un ejemplo explícito en el que se alcanza el valor máximo posible para incluso$n$.