Дано
$a_1 \leq a_2 \leq a_3\leq ...\leq a_n$
$b_1 \leq b_2 \leq b_3\leq ...\leq b_n$
Нужно доказать или опровергнуть что
$\sum_{i=1}^{n} |a_i-b_i| \leq \sum_{i=1}^{n} |a_i-b_{\sigma(i)}|$
Где $\sigma(i)$ - ф-ция перестановок. Т.е. если нам, например, дан набор $\{1, 2, 3, 4, 5\}$ и перестановка $\{3, 1, 2, 4, 5 \}$ то $\sigma(1)=3$, $\sigma(2)=1$, ..., $\sigma(5)=5$.
Иными словами: сумма $\sum_{i=1}^{n} |a_i-b_j|$ минимальна тогда, когда $i=j$
\sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}+a_{n}-a_{k}|+|a_{k}-b_{n}+b_{n}-b_{s}| = \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}|+a_{n}-a_{k}+|b_{n}-a_{n}|+b_{n}-b_{s} = \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}|+|a_{n}-a_{k}|+|b_{n}-a_{n}|+|b_{s}-b_{n}| \geq \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right |+|b_{s}-a_{k}|+|b_{n}-a_{n}|
бле тег забыл, но пох, коороче просто по индукции деалешь, последние элементы вставляя на место
$
\sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | + |b_{n}-a_{k}|+|a_{n}-b_{s}| =
\sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}+a_{n}-a_{k}|+|a_{k}-b_{n}+b_{n}-b_{s}| = \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}|+a_{n}-a_{k}+|b_{n}-a_{n}|+b_{n}-b_{s} = \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right | +|b_{n}-a_{n}|+|a_{n}-a_{k}|+|b_{n}-a_{n}|+|b_{s}-b_{n}| \geq \sum_{i\neq n,k}^{n}\left | a_{i}-b_{\sigma i}\right |+|b_{s}-a_{k}|+|b_{n}-a_{n}|
$
Не благодари.