Sur l'inégalité $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$
Donné $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ prouve-le $$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$ Ce problème a été proposé par le nouveau contributeur @ user3458994 et il a été fermé par cinq utilisateurs. Je trouve cela un peu difficile (il n'a pas de réponse immédiate), mais il est suffisamment bien posé et, en effet, il peut être résolu en répondant correctement.
Il existe de nombreuses sommes possibles $\sum_{i=1}^n|a_i-b_i|$; en fait il y a$n!$ possibilités (nombre de permutations de l'ensemble $\{1,2,\cdots,n\}$). Le minimum pour ces sommes est$0$ correspondant à la permutation d'identité $a_i\rightarrow b_i=a_i$auquel cas l'inégalité est vérifiée de manière triviale. Nous exposons l'une de ces sommes ayant une valeur maximale$M$ exactement égal à $\big\lfloor \frac{n^2}{2}\big\rfloor$. Je croyais qu'aucune autre somme n'avait une valeur supérieure à$M$ auquel cas le problème serait faux (ai-je tort?).
Réponses
Voici une réponse presque immédiate.
En élargissant chaque terme de $ |a_i - b_i|$ dans le correspondant $\pm (a_i - b_i)$, on ge ça $$ \sum |a_i - b_i | = \sum c_i i, $$ où $c_i \in \{-2, 0, 2 \}$ et $\sum c_i = 0 $.
Remarque: il s'agit d'une condition nécessaire, mais non suffisante. En particulier, toutes les combinaisons de$c_i$sont possibles à partir de la valeur absolue, nous devrons donc par la suite nous assurer que cela peut être satisfait. Cependant, nous avons la «chance» que cela fonctionne pour nous.
Quand $n=2m$ est pair, le maximum de $\sum c_i i $ est $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$.
Ceci est satisfait de$a_i = i, b_i = n+1-i$, donc c'est le maximum de $ \sum |a_i - b_i|$.
Quand $n = 2m+1$ est étrange, le maximum de $\sum c_i i $ est $ -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)$.
Ceci est satisfait de$a_i = i, b_i = n+1-i$, donc c'est le maximum de $ \sum |a_i - b_i|$.
Remarque: la condition nécessaire et suffisante est $ \sum_{i=1}^k c_{n+1-i} \geq 0$ pour tous $ 1 \leq k \leq n$. Une fois que cela est satisfait, il existe une manière assez naturelle d'attribuer les valeurs. (Pensez-y.)
J'ai déjà donné une réponse dans ce post. Je le posterai à nouveau ici. C'est un peu similaire à l'inégalité de réarrangement: quand$\{a_i\}$ et $\{b_i=i\}$d'ordre opposé, la somme de la différence absolue atteint le maximum (il pourrait y avoir d'autres cas qui atteignent également ce maximum). Le reste n'est qu'un calcul facile.
Lemme: Si$x>y,z>w$ puis $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$
WLOG nous pouvons supposer $y\geqslant w$. ensuite$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|$$
qui découle de l'inégalité triangulaire.
WLOG suppose $b_i=i$. Ensuite, à partir du lemme, la somme des différences absolues obtient sa valeur maximale lorsque$a_i$ diminue, c'est-à-dire $$\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$$
Pour toute permutation, il y en a $1 \le k \le n$ valeurs de $i$ où
$$a_i - b_i \lt 0 \tag{1}\label{eq1A}$$
Ainsi, le reste $n - k$ valeurs de $i$ sera où
$$a_i - b_i \ge 0 \tag{2}\label{eq2A}$$
Pour plus de simplicité, si nécessaire, ajustez les valeurs de $a_i$ et $b_i$ alors le $k$ les valeurs où \ eqref {eq1A} hold sont celles où $1 \le i \le k$. Cela donne alors
$$\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 dernière ligne vient de $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ donc le dernier $2$termes de la ligne avant d'annuler. Dans \ eqref {eq3A}, la valeur maximale provient du$b_i$ étant le plus grand autorisé $k$ valeurs, c'est-à-dire $n - k + 1 \le b_i \le n$, et $a_i$ étant le plus petit autorisé $k$ valeurs, c'est-à-dire $1 \le a_i \le k$. Donc,
$$\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}$$
Remarque $f(k) = 2k(n - k)$ est une parabole concave vers le bas avec un maximum à $k = \frac{n}{2}$. Même pour$n$, cette valeur de $k$ est un entier, avec une valeur maximale de \ eqref {eq4A} comme
$$\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}$$
Pour bizarre $n$, la même valeur maximale est atteinte avec $k = \frac{n - 1}{2}$ et $k = \frac{n + 1}{2}$. En utilisant la première valeur, nous obtenons 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}$$
Cela montre que l'inégalité déclarée est toujours valable. Remarque La réponse de Piquito donne un exemple explicite où la valeur maximale possible est atteinte pour pair$n$.