Двач.hk не отвечает.
Вы видите копию треда, сохраненную 24 марта в 21:30.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Вы видите копию треда, сохраненную 24 марта в 21:30.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
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], чтобы минимизировать путь нужно не идти назад.
Двач.hk не отвечает.
Вы видите копию треда, сохраненную 24 марта в 21:30.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Вы видите копию треда, сохраненную 24 марта в 21:30.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.