Exercise 2. A permutation of the set $\{1, \ldots, 2021\}$ is a sequence $\sigma=\left(\sigma_{1}, \ldots, \sigma_{2021}\right)$ such that each element of the set $\{1, \ldots, 2021\}$ is equal to exactly one term $\sigma_{i}$. We define the weight of such a permutation $\sigma$ as the sum

$$
\sum_{i=1}^{2020}\left|\sigma_{i+1}-\sigma_{i}\right|
$$

What is the greatest possible weight of permutations of $\{1, \ldots, 2021\}$?
Solution to Exercise 2 Let $n=2021$, and let $\sigma$ be a permutation of $\{1,2, \ldots, n\}$ and let $\mathbf{W}(\sigma)$ be its weight. For all integers $k \leqslant n$, we define

$$
\alpha_{k}=\left\{\begin{array}{ll}
1 & \text { if } k \neq n \text { and } \sigma(k)>\sigma(k+1) \\
0 & \text { if } k=n \\
-1 & \text { if } k \neq n \text { and } \sigma(k)\sigma(k-1) \\
0 & \text { if } k=1 \\
-1 & \text { if } k \neq 1 \text { and } \sigma(k)<\sigma(k-1)\end{cases}\right.
$$

Finally, we set $\varepsilon_{k}=\alpha_{\sigma^{-1}(k)}+\beta_{\sigma^{-1}(k)}$. We then observe that

$$
\mathbf{W}(\sigma)=\sum_{k=1}^{n}\left(\alpha_{k}+\beta_{k}\right) \sigma(k)=\sum_{k=1}^{n} k \varepsilon_{k}
$$

We now denote by $\mathcal{X}$ the set of $n$-tuples $\mathbf{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ such that

$\triangleright x_{1}+x_{2}+\ldots+x_{n}=0$ and

$\triangleright$ there exist two indices $i$ and $j$ for which $x_{i}, x_{j} \in\{-1,+1\}$, and $x_{k} \in\{-2,0,2\}$ whenever $k \notin\{i, j\}$.

By construction, the $n$-tuple $\left(\varepsilon_{1}, \ldots, \varepsilon_{n}\right)$ belongs to $\mathcal{X}$.

More generally, we set $\mathbf{W}(\mathbf{x})=\sum_{k=1}^{n} k x_{k}$ for any $n$-tuple $\mathbf{x} \in \mathcal{X}$, and we consider an $n$-tuple $\mathbf{y}=\left(y_{1}, y_{2}, \ldots, y_{n}\right) \in \mathcal{X}$ for which $\mathbf{W}(y)$ is maximal.

The rearrangement inequality indicates that $y_{1} \leqslant y_{2} \leqslant \ldots \leqslant y_{n}$. Suppose there exists an index $i$ for which $y_{i}=0$. If $i \geqslant 2$ and $y_{i-1}=-1$, replacing $y_{i}$ and $y_{i+1}$ with -2 and 1 increases $\mathbf{W}(\mathbf{y})$ by 2. Similarly, if $i \leqslant n-1$ and $y_{i+1}=1$, replacing $y_{i}$ and $y_{i+1}$ with -1 and 2 increases $\mathbf{W}(\mathbf{y})$ by 2. Since the $n$-tuple $\mathbf{y}$ must contain coordinates equal to $\pm 1$, all its coordinates are therefore non-zero.

Finally, let $a$ be the number of indices $i$ for which $y_{i}=-2$, and $b$ the number of indices $i$ for which $y_{i}=2$. We know that $y_{1}=\ldots=y_{a}=-2, y_{a+1}= \pm 1, y_{a+2}= \pm 1$ and $y_{a+3}=\ldots=y_{n}=2$, so that $a+b+2=n$ and $-2 a+y_{a+1}+y_{a+2}+2 b=0$. Thus,

$$
a=\frac{2 n+y_{a+1}+y_{a+2}}{4}-1 \text { and } b=\frac{2 n-y_{a+1}-y_{a+2}}{4}-1 \text {. }
$$

We then distinguish three cases, depending on the values of $y_{a+1}$ and $y_{a+2}$:

1. If $y_{a+1}=y_{a+2}=-1$, then $a=(n-3) / 2, b=(n-1) / 2$, so

$$
\mathbf{W}(\mathbf{y})=-2 \sum_{k=1}^{a} k-(a+1)-(a+2)+2 \sum_{k=a+3}^{n} k=\left(n^{2}-3\right) / 2
$$

2. If $y_{a+1}=y_{a+2}=1$, then $a=(n-1) / 2, b=(n-3) / 2$, so

$$
\mathbf{W}(\mathbf{y})=-2 \sum_{k=1}^{a} k+(a+1)+(a+2)+2 \sum_{k=a+3}^{n} k=\left(n^{2}-3\right) / 2
$$

3. If $y_{a+1}=-1$ and $y_{a+2}=1$, then $a=b=(n-2) / 2$, which is impossible since $n$ is odd.

Consequently, $\mathbf{W}(\sigma) \leqslant\left(n^{2}-3\right) / 2$.

Conversely, we set $\ell=(n-1) / 2$, and we denote by $\sigma$ the permutation of $\{1,2, \ldots, n\}$ defined by

$$
\begin{cases}\sigma(2 k-1)=\ell+1+k & \text { if } 1 \leqslant k \leqslant \ell \\ \sigma(2 k)=k & \text { if } 1 \leqslant k \leqslant \ell \\ \sigma(n)=\ell+1 & \end{cases}
$$

![](https://cdn.mathpix.com/cropped/2024_06_04_2a6b465c0f07747f8f2dg-06.jpg?height=166&width=169&top_left_y=431&top_left_x=1703)

This permutation is associated with the $n$-tuple $(-2, \ldots,-2,1,1,2, \ldots, 2)$ with $\ell$ coordinates equal to -2 and $\ell$ coordinates equal to 2, so its weight is $\left(n^{2}-3\right) / 2$, as shown in case 2 above.

In conclusion, the maximum weight sought is $\left(n^{2}-3\right) / 2$, which is 2042219.