Let n=2021, and let σ be a permutation of {1,2,…,n} and let W(σ) be its weight. For all integers k⩽n, we set
k =
1 & { if } k n { and } σ(k)>σ(k+1)
0 & { if } k=n
-1 & { if } k n { and } σ(k)σ(k−1)
0 & { if } k=1
-1 & { if } k 1 { and } σ(k)σi>σi+1.Wethendenotebyσ′thepermutationof{1,2,…,n}$ defined by:
▹σj′=σj when 1⩽j⩽i−1;▹σj′=σj+1 when i⩽j⩽n−1;▹σn′=σi.
Since ∣σi−σi+1∣+∣σi+1−σi+2∣=∣σi−σi+2∣, the weight of σ′ is that of σ plus ∣σn−σ1∣, which contradicts the maximality of the weight of σ.
Moreover, and by replacing σ with its "horizontal mirror" permutation, i.e., by replacing each term σj with n+1−σj, which does not change the weight of σ, we assume without loss of generality that σ1σ2j+1 for all integers j such that 1⩽j⩽k.
The weight of σ is then
j=1∑k2σ2j−σ1−σn−j=1∑k−12σ2j+1
Since σ does not take the same value twice, we have
j=1∑k2σ2j⩽j=n+1−k∑n2j=n(n+1)−(n−k)(n+1−k)=3k2+3k and j=1∑k−12σ2j+1+σ1+σn⩾j=1∑k−12j+k+(k+1)=k(k−1)+(2k+1)=k2+k+1
Therefore, the weight of σ cannot exceed 2k2+2k−1=2042219.
Conversely, the permutation indicated at the end of the previous solution is indeed of weight 2042219, and this is indeed the maximum weight.