Return to Revisions

Here is a short proof that at most $2n-2$ swaps are necessary. We proceed by induction on $n$. For the base case $n=1$, it is clear that no swaps are necessary. For the inductive step, let $X_1,X_2,X_3,X_4$ be multisets of $n$ numbers in $[0,1]$. For each $i \in [4]$, arbitrarily choose $x_i \in X_i$, and let $Y_i=X_i \setminus \{x_i\}$. By induction, we may perform at most $2n-4$ swaps to $Y_1 ,\dots, Y_4$ to obtain $Y_1', \dots, Y_4'$ such that $|\sigma(Y_i') - \sigma(Y_j')| \leq 1$ for all $i,j$. By renaming, we may assume that $\sigma(Y_1') \leq \sigma(Y_2') \leq \sigma(Y_3') \leq \sigma(Y_4')$. For each $i \in \{2,3,4\}$ let $d_i=\sigma(Y_i')-\sigma(Y_1')$. It suffices to reorder $x_1, \dots, x_4$ using at most two swaps, such that $|\sigma(Y_i' \cup \{x_i)\}) - \sigma(Y_j' \cup \{x_j\})| \leq 1$ for all $i,j$. By performing a single swap, we may assume that $x_1$ is the largest element among $x_1, \dots, x_4$. If we can perform an additional swap so that $x_1 \geq x_2 \geq x_3 \geq x_4$, then we are done since $\sigma(Y_1') \leq \sigma(Y_2') \leq \sigma(Y_3') \leq \sigma(Y_4')$. This is always possible unless $x_1 \geq x_3 \geq x_4 \geq x_2$, or $x_1 \geq x_4 \geq x_2 \geq x_3$. In the first case we choose the index $i \in \{3,4\}$ such that $d_{i}+x_{i}$ is maximum and we swap $x_i$ with $x_2$. In the second case, we choose the index $i \in \{2,3\}$ such that $d_{i}+x_{i}$ is minimum and we swap $x_i$ with $x_4$.