Skip to main content
1 of 4
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

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}\ .$$

Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269