Return to Answer

For a given $\tau\in S_n$ and for any $j\in[n]$ define the numbers $$a_j:=\chi_{\Delta}(j)-\chi_{\Delta}(j-1)-\chi_{\Delta }(n-j)+\chi_{\Delta}(n-j+1),$$ where $\chi_\Delta:\mathbb{Z}\to\{0,1\}$ denotes the characteristic function of the set $\Delta:=\Delta(\tau)\subset\mathbb{Z}$. Also, with $c:=5n-a_n$, define $$b_j:=a_j-5j+c.$$ We may note right away that since $|a_j|\le2$, the $b_j$ are strictly decreasing, and that $b_n=0$, by the choice of the constant $c$.

For any $E\subset[n]$, for simplicity of notation we put $$ \alpha(E):=\sum_{j\in E} a_j,\qquad \beta(E):=\sum_{j\in E} b_j$$ (so we may think $ \alpha$ and $\beta$ as discrete signed measures supported in $[n]$).

For $i\in[n]$, summing over $j=1,\dots i$ we have

$$ \alpha([i])=\chi_\Delta(i)-\chi_\Delta(n-i).$$

Incidentally, for any $i\in[n]$ we have $i\in\Delta$ if and only if, by definition, $\tau([i])\neq[i]+n-i$ thus also, since $\tau$ is bijective, if and only if $\tau([i]^c)\neq([i]+n-i)^c$, that is $\tau([n-i]+i)\neq [n-i]$ or $\tau^{-1}([n-i])\neq [n-i]+i$, which means $n-i\not\in\Delta^{-1}:=\Delta(\tau^{-1})$. Hence the last formula also writes $$ \alpha([i])=\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i).$$ Also note that, since $n\not\in\Delta$ $$ \alpha([n])=0,$$ and $$ \alpha([i]+n-i)=- \alpha([n-i]) =-\chi_\Delta(n-i)+\chi_\Delta(i)= \alpha([i]).$$

We proceed showing the inequalities on the arithmetic means.

Case I. Assume $i\in\Delta\setminus\Delta^{-1}$. Then by definition of $\Delta^{-1}$, $\tau^{-1}([i])=[i]+n-i$, so that

$$ {\alpha([i])+ \alpha(\tau^{-1}[i])\over 2i}= {\alpha([i])+ \alpha([i]+n-i)\over2i}={\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i)\over i}={1\over i}>0, $$ and summing the arithmetic means of $-5j+c$ on the same sets we have plainly $${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([n])\over n}.$$

Case II. Assume $i\in\Delta\cap\Delta^{-1}$. Thus $\tau^{-1}([i])\neq[i]+n-i$ and, just because $b_j$ are strictly decreasing

$${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([i])+ \beta([i]+n-i)\over2i}$$ and since we have $\alpha([i])=\alpha([i]+n-i)=\alpha([n])=0$ because $\chi_{\Delta}(i)=\chi_{\Delta^{-1}}(i)=1$, summing as before the arithmetic means of the affine part of $b_j$, $${\beta([i])+ \beta([i]+n-i)\over2i}={\beta([n])\over n},$$ concluding the proof.

For a given $\tau\in S_n$ and for any $j\in[n]$ define the numbers $$a_j:=\chi_{\Delta}(j)-\chi_{\Delta}(j-1)-\chi_{\Delta }(n-j)+\chi_{\Delta}(n-j+1),$$ where $\chi_\Delta:\mathbb{Z}\to\{0,1\}$ denotes the characteristic function of the set $\Delta:=\Delta(\tau)\subset\mathbb{Z}$. Also, with $c:=5n-a_n$, define $$b_j:=a_j-5j+c.$$ We may note right away that since $|a_j|\le2$, the $b_j$ are strictly decreasing, and that $b_n=0$, by the choice of the constant $c$.

For any $E\subset[n]$, for simplicity of notation we put $$ \alpha(E):=\sum_{j\in E} a_j,\qquad \beta(E):=\sum_{j\in E} b_j$$ (so we may think $ \alpha$ and $\beta$ as discrete signed measures supported in $[n]$).

For $i\in[n]$, summing over $j=1,\dots i$ we have

$$ \alpha([i])=\chi_\Delta(i)-\chi_\Delta(n-i).$$

Incidentally, for any $i\in[n]$ we have $i\in\Delta$ if and only if, by definition, $\tau([i])\neq[i]+n-i$ thus also, since $\tau$ is bijective, if and only if $\tau([i]^c)\neq([i]+n-i)^c$, that is $\tau([n-i]+i)\neq [n-i]$ or $\tau^{-1}([n-i])\neq [n-i]+i$, which means $n-i \in \Delta^{-1}:=\Delta(\tau^{-1})$. Hence the last formula also writes $$ \alpha([i])=\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i).$$ Also note that, since $n\not\in\Delta$ $$ \alpha([n])=0,$$ and $$ \alpha([i]+n-i)=- \alpha([n-i]) =-\chi_\Delta(n-i)+\chi_\Delta(i)= \alpha([i]).$$

We proceed showing the inequalities on the arithmetic means.

Case I. Assume $i\in\Delta\setminus\Delta^{-1}$. Then by definition of $\Delta^{-1}$, $\tau^{-1}([i])=[i]+n-i$, so that

$$ {\alpha([i])+ \alpha(\tau^{-1}[i])\over 2i}= {\alpha([i])+ \alpha([i]+n-i)\over2i}={\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i)\over i}={1\over i}>0, $$ and summing the arithmetic means of $-5j+c$ on the same sets we have plainly $${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([n])\over n}.$$

Case II. Assume $i\in\Delta\cap\Delta^{-1}$. Thus $\tau^{-1}([i])\neq[i]+n-i$ and, just because $b_j$ are strictly decreasing

$${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([i])+ \beta([i]+n-i)\over2i}$$ and since we have $\alpha([i])=\alpha([i]+n-i)=\alpha([n])=0$ because $\chi_{\Delta}(i)=\chi_{\Delta^{-1}}(i)=1$, summing as before the arithmetic means of the affine part of $b_j$, $${\beta([i])+ \beta([i]+n-i)\over2i}={\beta([n])\over n},$$ concluding the proof.

I think the $n$-ple $b_k:=n-k$ for $k\in [n]:=\{1,\dots,n\}$ fulfills your requirements (and more generally, any strictly decreasing and "centrally symmetric" sequence, that is, such that $b_k+b_{n-k+1}=b_1+b_n$ for all $k\in[n]$ -- or just $b_1$, in your case, since you also want $b_n=0$).

For any $i\in [n]$, the minimum value of the sum $\sum_{k\in E} b_k$ among all subsets $E\subset[n]$ of cardinality $i$ is attained uniquely by the subset $[i]+n-i=\{n,n-1,\dots,n-i+1\}$, just because the $b_k$ are strictly decreasing.

Therefore, for any $\tau\in S_n$ and for any $i\in\Delta(\tau)$ (which exactly means $\tau([i])\neq[i]+n-i$) we have $${b_1+\dots+b_i+ b_{\tau(1)}+\dots+b_{\tau(i)}\over 2i}>{(b_1+\dots+b_i)+ (b_{n}+\dots+b_{n-i+1})\over 2i}=$$$$={(b_1+ b_{n})+(b_2+b_{n-1})+\dots+(b_i+b_{n-i+1})\over 2i}$$ and because the $b_k$ are centrally symmetric this is $$={b_1+ b_{n}\over 2}={b_1+b_2+ \dots+ b_{n }\over n}\ .$$

For a given $\tau\in S_n$ and for any $j\in[n]$ define the numbers $$a_j:=\chi_{\Delta}(j)-\chi_{\Delta}(j-1)-\chi_{\Delta }(n-j)+\chi_{\Delta}(n-j+1),$$ where $\chi_\Delta:\mathbb{Z}\to\{0,1\}$ denotes the characteristic function of the set $\Delta:=\Delta(\tau)\subset\mathbb{Z}$. Also, with $c:=5n-a_n$, define $$b_j:=a_j-5j+c.$$ We may note right away that since $|a_j|\le2$, the $b_j$ are strictly decreasing, and that $b_n=0$, by the choice of the constant $c$.

For any $E\subset[n]$, for simplicity of notation we put $$ \alpha(E):=\sum_{j\in E} a_j,\qquad \beta(E):=\sum_{j\in E} b_j$$ (so we may think $ \alpha$ and $\beta$ as discrete signed measures supported in $[n]$).

For $i\in[n]$, summing over $j=1,\dots i$ we have

$$ \alpha([i])=\chi_\Delta(i)-\chi_\Delta(n-i).$$

Incidentally, for any $i\in[n]$ we have $i\in\Delta$ if and only if, by definition, $\tau([i])\neq[i]+n-i$ thus also, since $\tau$ is bijective, if and only if $\tau([i]^c)\neq([i]+n-i)^c$, that is $\tau([n-i]+i)\neq [n-i]$ or $\tau^{-1}([n-i])\neq [n-i]+i$, which means $n-i\not\in\Delta^{-1}:=\Delta(\tau^{-1})$. Hence the last formula also writes $$ \alpha([i])=\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i).$$ Also note that, since $n\not\in\Delta$ $$ \alpha([n])=0,$$ and $$ \alpha([i]+n-i)=- \alpha([n-i]) =-\chi_\Delta(n-i)+\chi_\Delta(i)= \alpha([i]).$$

We proceed showing the inequalities on the arithmetic means.

Case I. Assume $i\in\Delta\setminus\Delta^{-1}$. Then by definition of $\Delta^{-1}$, $\tau^{-1}([i])=[i]+n-i$, so that

$$ {\alpha([i])+ \alpha(\tau^{-1}[i])\over 2i}= {\alpha([i])+ \alpha([i]+n-i)\over2i}={\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i)\over i}={1\over i}>0, $$ and summing the arithmetic means of $-5j+c$ on the same sets we have plainly $${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([n])\over n}.$$

Case II. Assume $i\in\Delta\cap\Delta^{-1}$. Thus $\tau^{-1}([i])\neq[i]+n-i$ and, just because $b_j$ are strictly decreasing

$${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([i])+ \beta([i]+n-i)\over2i}$$ and since we have $\alpha([i])=\alpha([i]+n-i)=\alpha([n])=0$ because $\chi_{\Delta}(i)=\chi_{\Delta^{-1}}(i)=1$, summing as before the arithmetic means of the affine part of $b_j$, $${\beta([i])+ \beta([i]+n-i)\over2i}={\beta([n])\over n},$$ concluding the proof.

I think the $n$-ple $b_k:=n-k$ for $k\in [n]:=\{1,\dots,n\}$ fulfills your requirements (and more generally, any strictly decreasing and centrally symmetric sequence, that is, such that $b_k+b_{n-k}=b_1+b_n$ for all $k\in[n]$).

For any $i\in [n]$, the minimum value of the sum $\sum_{k\in E} b_k$ among all subsets $E\subset[n]$ of cardinality $i$ is attained uniquely by the subset $[i]+n-i=\{n,n-1,\dots,n-i+1\}$, just because the $b_k$ are strictly decreasing.

Therefore, for any $\tau\in S_n$ and for any $i\in\Delta(\tau)$ (which exactly means $\tau([i])\neq [i]+n-i$) we have $${b_1+\dots+b_i+ b_{\tau(1)}+\dots+b_{\tau(i)}\over 2i}>{(b_1+\dots+b_i)+ (b_{n}+\dots+b_{n-i+1})\over 2i}$$ and because the $b_k$ are centrally symmetric this is $$={(b_1+ b_{n})+(b_2+b_{n-1})+\dots+(b_i+b_{n-i+1})\over 2i}={b_1+ b_{n}\over 2}={b_1+b_2+ \dots+ b_{n }\over n}\ .$$

I think the $n$-ple $b_k:=n-k$ for $k\in [n]:=\{1,\dots,n\}$ fulfills your requirements (and more generally, any strictly decreasing and "centrally symmetric" sequence, that is, such that $b_k+b_{n-k+1}=b_1+b_n$ for all $k\in[n]$ -- or just $b_1$, in your case, since you also want $b_n=0$).

For any $i\in [n]$, the minimum value of the sum $\sum_{k\in E} b_k$ among all subsets $E\subset[n]$ of cardinality $i$ is attained uniquely by the subset $[i]+n-i=\{n,n-1,\dots,n-i+1\}$, just because the $b_k$ are strictly decreasing.

Therefore, for any $\tau\in S_n$ and for any $i\in\Delta(\tau)$ (which exactly means $\tau([i])\neq[i]+n-i$) we have $${b_1+\dots+b_i+ b_{\tau(1)}+\dots+b_{\tau(i)}\over 2i}>{(b_1+\dots+b_i)+ (b_{n}+\dots+b_{n-i+1})\over 2i}=$$$$={(b_1+ b_{n})+(b_2+b_{n-1})+\dots+(b_i+b_{n-i+1})\over 2i}$$ and because the $b_k$ are centrally symmetric this is $$={b_1+ b_{n}\over 2}={b_1+b_2+ \dots+ b_{n }\over n}\ .$$