On the inequality $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$ Given $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ prove that
$$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$
This problem was proposed by the new contributor  @user3458994 and it was closed by five users. I find it somewhat challenging (it does not have an immediate answer), but it is sufficiently well posed and, indeed, it can be solved by answering correctly.
There are many possible sums $\sum_{i=1}^n|a_i-b_i|$; in fact there are $n!$ possibilities (number of permutations of the set $\{1,2,\cdots,n\}$). The minimum for these sums is $0$ corresponding to the identity permutation $a_i\rightarrow b_i=a_i$ in which case the inequality is trivially verified. We expose one of these sums having a maximum value $M$ exactly equal to $\big\lfloor \frac{n^2}{2}\big\rfloor$. I believed no other sum has a value greater than $M$ in which case the problem would be false (am I wrong?).
 A: Here's an almost immediate answer.
By expanding each term of $ |a_i - b_i|$ into the corresponding $\pm (a_i - b_i)$, we ge that
$$ \sum |a_i - b_i | = \sum c_i i,  $$ where $c_i \in \{-2, 0, 2 \}$ and $\sum c_i = 0 $.
Note: This is a necessary, but not sufficient condition. In particular, not all combinations of $c_i$ are possible from the absolute value, so we'd subsequently have to ensure that this can be satisfied. However, we're "lucky" enough that this works out for us.
When $n=2m$ is even, the maximum of $\sum c_i i $ is $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$.
This is satisfied with $a_i = i, b_i = n+1-i$, so it's the maximum of $ \sum |a_i - b_i|$.
When $n = 2m+1$ is odd, the maximum of $\sum c_i i $ is $ -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)$.
This is satisfied with $a_i = i, b_i = n+1-i$, so it's the maximum of $ \sum |a_i - b_i|$.
Note: The necessary and sufficient condition is $ \sum_{i=1}^k c_{n+1-i} \geq 0$ for all $ 1 \leq k \leq n$. Once that is satisfied, there's a pretty natural way to assign the values. (Have a think about it.)
A: I have already given an answer in that post. I will post it again here. It's somewhat similar to the rearrangement inequality: When $\{a_i\}$ and $\{b_i=i\}$ have opposite order, the sum of the absolute difference reaches maximum (there could be other cases which also reach this maximum). The rest is just easy calculation.

Lemma: If $x>y,z>w$ then $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$
WLOG we can assume $y\geqslant w$. Then $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|$$
which follows from the triangle inequality.
WLOG assume $b_i=i$. Then from the lemma the sum of absolute differences obtains its maximum value when $a_i$ is decreasing, i.e. $$\sum_{i=1}^n|a_i-i| \leqslant \sum_{i=1}^n |n+1-2i|.$$
If $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.$$
If $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$$
A: For any permutation, there's some $1 \le k \le n$ values of $i$ where
$$a_i - b_i \lt 0 \tag{1}\label{eq1A}$$
Thus, the remaining $n - k$ values of $i$ will be where
$$a_i - b_i \ge 0 \tag{2}\label{eq2A}$$
For simplicity, if need be, adjust the values of $a_i$ and $b_i$ so the $k$ values where \eqref{eq1A} hold are the ones where $1 \le i \le k$. This then gives
$$\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}$$
The last line comes from $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ so the last $2$ terms of the line before cancel. In \eqref{eq3A}, the maximum value comes from the $b_i$ being the largest allowed $k$ values, i.e., $n - k + 1 \le b_i \le n$, and $a_i$ being the smallest allowed $k$ values, i.e., $1 \le a_i \le k$. Thus,
$$\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}$$
Note $f(k) = 2k(n - k)$ is a concave down parabola with a maximum at $k = \frac{n}{2}$. For even $n$, this value of $k$ is an integer, with it giving a maximum value of \eqref{eq4A} as
$$\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}$$
For odd $n$, the same maximum value is achieved with $k = \frac{n - 1}{2}$ and $k = \frac{n + 1}{2}$. Using the first value, we get from \eqref{eq4A} that
$$\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}$$
This shows the stated inequality always holds. Note Piquito's answer gives an explicit example where the maximum possible value is reached for even $n$.
