Help with a minimum-distance permutation problem Given an ascendantly ordered non-negative real number sequence $X=x_1,...,x_n$, and another non-negative sequence $Y=y_1,...,y_n$, let $P$ denote all permutations of $Y$. Given a particular permutation $p\in P$, denote the permuted $Y$ as $Y_p=y_{i_1},...,y_{i_n}$. Let $p_0$ be the particular permutation s.t. element in $Y_{p_0}$ are ascendantly ordered as well.
Define $d(X,Y_p)=|y_{i_1}-x_1|+...+|y_{i_n}-x_n|$, and let $d^*=\min_{p\in P}{d(X,Y_p)}$. The question is

Is $d^*=d(X,Y_{p_0})$, i.e. is the minimum distance between $X,Y_p$ is the distance between the ordered $X$ and ordered $Y$? If not, can you give a counterexample?

For example, suppose
$X=1,2,3,4$, $Y=9,7,8,0$, then $d(X,Y_0)=d((1,2,3,4),(0,7,8,9))$. It seems that this is the minimum distance over all permutations of $Y$.
Thank you!
 A: The answer is affirmative. Suppose for a moment that an optimal permutation of $Y$ is not ascending, then there exist at least one unordered pair: $y_{i_j} > y_{i_k}$ ($j<k$). By switchting this pair, the difference in distance between $X$ and $Y_p$ is reduced by:
$$
\begin{align}
&|y_{i_j}-x_j|+|y_{i_k}-x_k|-|y_{i_j}-x_k|-|y_{i_k}-x_j| \\
= \quad & (|y_{i_j}-x_j|-|y_{i_j}-x_k|)+(|y_{i_k}-x_k|-|y_{i_k}-x_j|) \\
\geq \quad & 0.
\end{align}
$$
So, there is always an optimal permutation of $Y$ that is ascending. The optimum is not necessarily unique. This is obvious when all elements of $X$ are the same, or when all elements of $Y$ are smaller (or larger) than all elements of $X$. Even in other cases there are multiple optima, like in your example, you can take the permutation $(0,9,8,7)$.
A: If you have $x_1 < x_2$ and $y_1 < y_2$ there are three cases:


*

*$x_1 < x_2 < y_1 < y_2$

*$x_1 < y_1 < x_2 < y_2$

*$y_1 < x_1 < x_2 < y_2$


You can easily check in all cases that $|y_1 - x_1| + |y_2 - x_2| \leq |y_1 - x_2| + |y_2 - x_1|$.
Want to show: for any $\sigma \in S_n$, 
$$\sum_{k=1}^n |x_k - y_k| \leq \sum_{k=1}^n |x_k - y_{\sigma(k)}|$$
Let's proceed by induction on $n$. The above argument serves as a base case. 
Now, consider any $\sigma \in S_{n+1}$. If $\sigma$ has a fixed point, then $\sigma(j) = j$ for some $j$ and the term $|x_j - y_j|$ appears in both sums. Then we can subtract this term and thus we have reduce the problem to one of a permutation on $n$ letters. By the induction hypothesis, we are done.
Suppose $\sigma$ has no fixed points. Let $\sigma(n+1) = m$ and $\sigma(k) = n+1$. 
Consider what would happen to the sums if we "swapped" these two. Let $\sigma'$ be $\sigma$ with $\sigma'(n+1) = n+1$ and $\sigma'(k) = m$. Since $x_k < x_{n+1}$ and $y_m < y_{n+1}$, we know that 
$$|x_k - y_m| + |x_{n+1} - y_{n+1}| \leq |x_{k} - y_{n+1}| + |x_{n+1} - y_m|$$
Since $\sigma$ and $\sigma'$ agree at all other positions, this shows 
$$ \sum_{k=1}^n |x_k - y_{\sigma'(k)}| \leq \sum_{k=1}^n |x_k - y_{\sigma(k)}|$$
And thus this reduces to the case with a fixed point. 
Done. 
