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.
Problem
Source: MEMO 2015, problem T-3
Tags: combinatorics, permutations, optimization
randomusername
29.08.2015 10:43
Let $\pi(i)$ denote the new location of the student originally in position $i$, where $\pi$ is a permutation of $\{1,...,n\}$. We want to maximize
$$S=\sum_{i=1}^n |i-\pi(i)|=\sum_{i=1}^n(i+\pi(i)-2\min\{i,\pi(i)\}),$$
which is equivalent to minimizing $T=\sum_{i=1}^n \min\{i,\pi(i)\}$. Notice that among the numbers $1,2,\dots,n$ and $\pi(1),\pi(2),\dots,\pi(n)$, every number appears exactly twice. Hence, in $S$ each of these numbers can appear at most twice as a term in $T$. This shows that
$$T\ge \begin{cases} 2(1+2+\dots+k)=k(k+1) & \text{for even }n=2k \\ 2(1+2+\dots+k)+(k+1)=(k+1)^2 & \text{for odd }n=2k+1,\end{cases}$$
and equality can be attained if we choose $(\pi(1),\pi(2),\dots,\pi(n-1),\pi(n))=(n,n-1,\dots,2,1)$. Therefore, the maximum of $S$ is
$$\max S=2(1+2+\dots+n)-2T=\begin{cases} 2k(2k+1)-2k(k+1)=2k^2 & \text{for even }n=2k \\ (2k+1)(2k+2)-2(k+1)^2=2k(k+1) & \text{for odd }n=2k+1,\end{cases}$$
in other words, $\max S=\left\lfloor \frac{n^2}2\right\rfloor$.
rkm0959
29.08.2016 07:55
Very standard problem. Assume that the students changed the position by a permutation $\sigma$ Then we want the maximum of $\sum_{i=1}^n |i-\sigma (i)| = \sum_{i=1}^n (i+\sigma (i)) - 2 \sum_{i=1}^n \text{min} (i,\sigma (i)) = n(n+1) - 2\sum_{i=1}^n \text{min} (i, \sigma (i) ) $ So we want $\text{min} (i, \sigma (i))$ to be small. Each $i$ can be used at most twice, so choosing greedily gives the answer. Equality case can be found easily.