Минимальное значение суммы

[Xero]

Всем здоровья.

Вопрос следующий, на курсе математической статистики появилась нужда доказать следующую теорему, которую я доказывал принципиально иначе от преподавателя. И он (преподаватель) не уверен в правильности данного решения. Так вот обращаюсь за помощью.

Теорема: Пусть $x_1, x_2, ..., x_n$ растущая последовательность чисел. Сумма $ \sum_{k=1}^n |x_k-a|$ будет минимальной, если $a$ - медиана этой последовательности. То есть если $n=2k$, то $a=(x_k+x_{k+1})/2$, если же $n=2k+1$, то $a=x_{k+1}$.

Доказательство:
Рассмотрим сначала случай, когда n=2. То сумма сводится к $|x_1-a|+|x_2-a|$, благодаря неравенству треугольника получаем:
$|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $, так как последовательно растущая.
Что подходит под теорему даже для любого $a\in [x_1,x_2]$. А медиана находится в этом промежутке.

Далее, пусть $n$- произвольное число. Тогда начнём уменьшать нашу сумму следующим образом. Сначала рассмотрим только крайние элементы суммы, то есть $|x_1-a|+|x_n-a|$, вспомним, что мы доказывали для $n=2$, получаем что $a$ где-то между этими числами. Теперь тоже самое повторим для следующей пары чисел (на одну ближе к середине) $|x_2-a|+|x_{n-1}-a|$, отсюда получаем, что $a$ теперь в новом интервале, который является подинтервалом предыдущего. И т.д. пока мы можем это делать, если $n=2k$, то получим $a\in[x_k,x_{k+1}]$.
Если же $n=2k+1$, то получим $a=x_{k+1}$.

Теперь нужно показать, что такая сумма действительно минимальна. Пусть $a$ не из этого интервала, тогда все слагаемые будут минимизированы кроме тех, начиная с которого $a$ не попадает в заданный интервал.

И пожалуй всё. Что здесь надо доделать? И верно ли это доказательство?

[demolishka]

Не вдавался в подробности вашего решения. Но можно сделать проще. Как вы заметили для случая $n=2$ всё сводится к правильному применению неравенства треугольника. Т.е. так, чтобы полученная оценка снизу достигалась при каком-то $a$.
Пусть $a \in [x_k;x_{k+1}]$. Тогда

$$\sum\limits_{p=1}^{n} |x_p-a| = ka - \sum_{s=1}^{k}x_s - (n-k)a + \sum_{p=k+1}^{n}x_p = (2k-n)a - \sum_{s=1}^{k}x_s + \sum_{p=k+1}^{n}x_p.$$

Отсюда видно, что в случае $n=2k$ сумма превращается в $\sum\limits_{p=1}^{k} |x_{k+p}-x_p|$. А это и есть оценка снизу на исходную сумму.
Если же $n=2k+1$, то сумма превращается в $-a - \sum\limits_{s=1}^{k}x_s + \sum\limits_{p=k+1}^{2k+1}x_p$. Отсюда опять же видно, что если положить $a=x_{k+1}$, то слагаемых в обоих суммах станет поровну и получится опять же оценка снизу с помощью неравенства треугольника.

[мат-ламер]

В точке минимума производная минимизируемой функции меняет знак (но в самой точке минимума она не существует). Производная в точке $x\ne x_k$ равна разности количества точек $x_k$ слева и справа от $x$.

[--mS--]

Xero в сообщении #987445 писал(а):

благодаря неравенству треугольника получаем:
$|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $, так как последовательно растущая.
Что подходит под теорему даже для любого $a\in [x_1,x_2]$. А медиана находится в этом промежутке.

Должно быть, Вы хотели сказать, что при любом $a\in [x_1,x_2]$ в неравенстве $|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $ нижняя граница достигается, т.е. правая часть $|x_1-a|+|x_2-a| =x_2-x_1 $ не зависит от $a\in [x_1,x_2]$ и меньше уже не бывает.

Нормальное доказательство. На занятии мы именно так и рассуждаем, только картинку с расстояниями рисуем.

[fractalon]

Xero в сообщении #987445 писал(а):

Теперь нужно показать, что такая сумма действительно минимальна. Пусть $a$ не из этого интервала, тогда все слагаемые будут минимизированы кроме тех, начиная с которого $a$ не попадает в заданный интервал.

Вот это, по-моему, кривовато сформулировано. Если вы не можете доказать минимальность другой суммы тем же методом, то это не значит, что та сумма не минимальна.
Этого абзаца, кажется, вообще не требуется. Просто пусть нашлась лучшая точка $b$. Но у нас $|x_1-a|+|x_n-a| \le |x_1-b|+|x_n-b|$, и $|x_2-a|+|x_{n-1}-a| \le |x_2-b|+|x_{n-1}-b|$ и так далее... Так и получается, что $\sum \limits_{i=1}^{n} {|x_i-a|} \le \sum \limits_{i=1}^{n} {|x_i-b|}$
Но это недочёты формулировки. В целом добавляю голос за то, что доказательство верное.

Хотя, честно говоря, непонятно отчего весь сырбор с такими разборами сумм и прочим. Неформально можно изложить проще.
Пусть $n = 2k$. Поставим точку $a$ в значение медианы. После сдвигов $a$ влево или вправо, значение будет сохранятся, пока мы не дойдём до точки $x_k$ или $x_{k+1}$. После того, как мы дошли до какой-то из этих точек, у нас уже будет разное количество точек слева и справа, и сдвигая точку $a$ на $\varepsilon$ в ту же сторону мы будем изменять в одну сторону разное количество положительных и отрицательных величин (расстояний до точек), причём изменять всех на одно и то же $\varepsilon$, что, очевидно, даст прирост суммы.
Итого, в медиане локальный минимум, а в две стороны от неё сумма монотонна. Победа.
Для $n=2k+1$ рассуждения точно те же, только нет островка постоянства суммы.

[ewert]

Несколько странное доказательство. Прежде всего, утверждение просто очевидно в силу да, картинки, т.е. выпуклости функции. А после того, как оно очевидно, напрашивается и естественное оформление: если количество узлов слева и справа от точки разное, то в этой точке просто производная не равна нулю (а если сама точка в узле, то одного знака обе односторонние производные, за исключением случая, когда это -- один из двух центральных узлов).

Это если доказательство вообще нуждается в формальном выписывании, в чём я сильно сомневаюсь. По-моему, картинки более чем достаточно.