Problem

Source: MEMO 2015, problem T-3

Tags: combinatorics, permutations, optimization



There are $n$ students standing in line 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.