## T-3

There are $n$ students standing in line in positions 1 to $n$. While the teacher looks away, some students change their positions. When the teacher looks back, they are standing in line again. If a student who was initially in position $i$ is now in position $j$, we say the student moved for $|i-j|$ steps. Determine the maximal sum of steps of all students that they can achieve.

Answer. $\frac{n^{2}}{2}$ for even $n$ and $\frac{n^{2}-1}{2}$ for odd $n$


Solution 1. Let us denote $x_{i}$ the place of student $i$ after switching places. Since $\sum_{i=1}^{n} i-x_{i}=$ $\sum_{i=1}^{n} i-\sum_{i=1}^{n} x_{i}=0$ holds, sum of summands $i-x_{i}$ which are negative is the same as sum of absolute values of summands $i-x_{i}$ which are negative. Therefore to maximize sum $\sum_{i=1}^{n}\left|i-x_{i}\right|$, it is enough to maximize sum of positive summands $i-x_{i}$. Let $k$ of summands be positive. Then $\sum_{j=1}^{k} i_{j}-x_{i_{j}} \leqslant \sum_{j=n-k+1}^{n} j-\sum_{j=1}^{k} j=k(n-k)$ which is maximal when $k=\left\lfloor\frac{n}{2}\right\rfloor$ with value $\frac{n^{2}}{2}$ for even $n$ and $\frac{n^{2}-1}{2}$ for odd $n$. This sum of movements can be achieved if students $i$ and $n-i+1$ switch places for $i=1, \ldots,\left\lfloor\frac{n}{2}\right\rfloor$.
