Prueba de la solución única de una minimización sobre dos secuencias

Question

Dadas dos secuencias no estrictamente ascendentes, demuestre que ningún reordenamiento de términos en cualquiera de las dos secuencias producirá una menor $S$ .

$A=1,2,3,4,5...\\B=2,3,4,5,6...$

$S=\left|A_1 - B_1\right|+\ldots +\left|A_n - B_n\right|$

Supongamos que las secuencias tienen la misma longitud.

Answer 1

Considere dos secuencias cualesquiera de longitud $n$ , digamos que $\langle a_1,\ldots,a_n\rangle$ y $\langle b_1,\ldots,b_n\rangle$ . Sin pérdida de generalidad, supongamos que $a_1\le a_2\le\ldots\le a_n$ . Ahora demuestre que si hay índices $j$ y $k$ tal que $1\le j<k\le n$ y $b_j>b_k$ y, a continuación, intercambiando $B_j$ y $B_k$ nunca aumenta $S$ (y puede disminuirlo). Como siempre se puede poner la segunda secuencia en orden no decreciente mediante una secuencia de intercambios de este tipo, se deduce que $S$ es mínima cuando la segunda secuencia también es no decreciente.

En el peor de los casos, considere todos los arreglos posibles de $a_j,a_k,b_j$ y $b_k$ individualmente; algunos de ellos son

$$\begin{align*} &a_j\le a_k\le b_k<b_j\;,\\ &a_j\le b_k\le a_k<b_j\;,\text{ and}\\ &a_j\le b_k<b_j\le a_k\;. \end{align*}$$

En cada caso se quiere comparar $$|a_j-b_j|+|a_k-b_k|$$ avec $$|a_j-b_k|+|a_k-b_j|\;.$$