521 Кб, 650x650Сможет ли матемач справиться с задачей?
Дано
$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$
Дано
$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$
>>797
Потом привыкаешь.
Потом привыкаешь.
\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}|
\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}|
>>799
бле тег забыл, но пох, коороче просто по индукции деалешь, последние элементы вставляя на место
бле тег забыл, но пох, коороче просто по индукции деалешь, последние элементы вставляя на место
>>800
$
\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}|
$
Не благодари.
$
\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}|
$
Не благодари.
Это же очевидно, читая перестановку слева направо мы идём на каждом шаге либо вперёд, либо назад по отрезку натруального ряда [1..n], чтобы минимизировать путь нужно не идти назад.