Maximizing $\sum_{n\in[m]}|f(n)-n|$ where $f(n)$ is a permuation of $[m]$

Question

Given $m\in\Bbb Z_{\ge1},[m]=\{1,2,...,m\}$ and $f(n)$ an arbitrary bijection from $[m]\to[m]$, I am interested in finding the maximum value of$$I_f=\sum_{n\in[m]}|f(n)-n|$$and the permutation $f^*(n)$ which achieves the maximum value. So far, I was trying to prove that the maximum is achieved for $f^*(n)=m+1-n$ which gives $I_{\max}=I_{f^*}=\lfloor m^2/2\rfloor$. Since I was not able to prove my hunch mathematically, I ran a small C++ program to build arbitrary permutations of $[m]$ and find the maximum $I_f$ for $1\le m\le 20$, and not once did I see the value of $I_f$ exceed $\lfloor m^2/2\rfloor$. Is my hunch correct and if so, how to go about proving it?

Answer 1

Let $1\le a<b \le m$ be two integers. Let $f$ be the initial permutation, and $\tilde{f}$ be another permutation resulted by exchanging values of $f$ at $a$ and $b$, that is: $$\tilde{f}(n)=\begin{cases}f(n) & \text{ if } n \ne a,b \\ f(b) & \text{ if } n=a\\ f(a) & \text{ if } n=b\\ \end{cases}$$ We will prove that if $f(a) < f(b)$ then $I_f \le I_{\tilde{f}}$.Indeed,
If $f(a)\le a, f(b) \le b$, then $$I_{\tilde{f}}-I_{f}=|f(b)-a|+|f(a)-b|-(-f(a)-f(b)+a+b) \ge 0 $$ If $f(a)\ge a, f(b) \ge b$, then $$I_{\tilde{f}}-I_{f}=|f(b)-a|+|f(a)-b|-(f(a)+f(b)-a-b) \ge 0 $$ If $f(a)>a$, $f(b)\le b$, then $a< f(a)<f(b) \le b$, then $$I_{\tilde{f}}-I_{f}=(f(b)-a)+(b-f(a))-(f(a)-a+b-f(b)) =2(f(b)-f(a)) \ge 0 $$ If $f(a)<a$, $f(b)\ge b$, then $f(a)<a<b<f(b) \le b$, then $$I_{\tilde{f}}-I_{f}=( f(b)-a +b-f(a)) - ( f(b)-b+a-f(a)) = 2b-2a > 0$$

Besides, by Bubble Sort, we know that for any permutation $f$, there is a sequence of permutation $f_0,f_1,\dots,f_k$ such that: $f_0=f$ and $f_k=f_*$ - the only decreasing permutation- such that $f_{l+1}$ is resulted from $f_l$ by exchanging two positions that are not situated decreasing. Thus, $$I_f \le \dots \le I_{f_*}$$ Hence the conclusion.

P.s: As I noted, you can use Karamata's inequality if you want a more compact solution( also more analytic).

P.s2: My conclusion uses Bubble Sort, which seems a bit tautological here. Nonetheless, the essential idea for a combinatoric proof is present.