|x - a1|+|x-a2|+.....|x-an|
a1 < a2 <....<an

Доказывать планирую по индукции, но идея вычисления не очень ясна. Если бы ai были бы положительными, возможно подошло бы их среднее арифметическое, а так совсем беда.

задан 15 Сен 21:53

изменен 15 Сен 22:04

нарисуйте графики функций $%y=|x-1|+|x-2|$% и $%y=|x-1|+|x-2|+|x-3|$%... думаю тогда всё будет ясно...

(15 Сен 22:06) all_exist

Нарисовал, заметил что они пересекаются в одной точке, что минимум стал немного выше, однако все равно не ясно как это обобщить, тем более что ai это вещественные числа

(15 Сен 22:14) Arkon

Ну, вы не на то смотрите... нарисуйте тогда ещё $%y=|x-2|$% и $%y=|x-1|+|x-2|+|x-3|+|x-4|$%... неужели не замечаете где находится минимум?...

(15 Сен 22:53) all_exist

Нет, с чего вы так решили?

(16 Сен 0:04) Arkon
10|600 символов нужно символов осталось
1

Положительность чисел тут никак не влияет. На числовой прямой у нас имеется n точек, которые идут слева направо. Берётся точка x, и мы находим сумму расстояний от неё до данных n точек. Эту сумму надо минимизировать. Смысл можно вложить такой: где надо расположить почтовое отделение, чтобы жителям было удобнее всего туда ходить (считается что все живут в домах вдоль прямой дороги).

Ответ здесь такой: если n нечётно, то x равно среднему из чисел (с номером (n+1)/2). Если n чётно, то годится любая точка отрезка между двумя средними числами (с номерами n/2 и n/2+1).

Доказательство: при чётном n все числа разбиваем на пары: a(1) и a(n), a(2) и a(n-1), ... ; в середине числа с номерами n/2 и n/2+1. При нечётном n принцип такой же, но одно число в середине, имеющее номер (n+1)/2, остаётся без пары.

В силу неравенства треугольника, |x-a(1)|+|x-a(n)|>=a(n)-a(1), причём равенство имеет место в точности для точек между a(1) и a(n). Аналогично, |x-a(2)|+|x-a(n-1)|<=a(n-1)-a(2), и так далее. Складывая все такие неравенства, при чётном n имеем |x-a(1)|+...+|x-a(n)|>=(a(n)+...+a(n/2+1))-(a(1)+...+a(n/2)). Значение величины в правой части (оно и будет наименьшим) достигается тогда и только тогда, когда все неравенства становятся равенствами. А для этого необходимо и достаточно, чтобы x лежало между каждой из рассматриваемых пар точек. В частности, между парой точек в середине, чего явно достаточно.

При нечётном n складываем те же неравенства, отдельно рассматривая среднюю из величин |x-a((n+1)/2)|, про которую мы знаем, что она неотрицательна, и равенство имеет место тогда и только тогда, когда x=a((n+1)/2), то есть x совпадает со средней точкой. Правая часть неравенства (это наименьшее значение) при этом будет равна (a(n)+...+a((n+3)/2))-(a(1)+...+a((n-1)/2)); средняя точка не участвует.

Кстати, среднее арифметическое подходит не всегда: например, для трёх чисел 1,2,6 подходит только x=2 с минимальной суммой расстояний 5, а среднее x=3 дало бы сумму 6. А вот к положительному случаю при необходимости всё как раз сводится, если сдвинуть числа по оси вправо достаточно далеко.

ссылка

отвечен 15 Сен 22:55

Огромное вам спасибо, я полностью понял решение и идею! Я сформулировал краткое доказательство: Возьмём точку посередине и обозначим dist до точек слева как a, справа как b, количество точек слева и справа как k Тогда, сдвинувшись от выбранной точки в правую сторону на e получим новую сумму расстояний: a+ke + b - ke Однако, если мы зашли за другую точку справа, то расстояние до нее стало не 0, а какое-то другое положительное число p Тогда итоговое расстояние будет a+ke + b - ke + p, что, конечно, больше чем a+b Аналогично для левого случая Это достаточно корректное доказательство?

(16 Сен 0:15) Arkon

@Arkon: решение, полученное на основании этой идеи, само по себе верное. Но его надо грамотно оформить, следя за тем, чтобы везде говорилась правда, чтобы все мысли были понятны и однозначны и так далее. Кроме этого, рассуждение должно охватывать все случаи, и т.п.

Я бы сделал так: представим себе, что мы не посередине. Тогда по одну сторону у нас больше точек, чем по другую. Тогда, сдвигаясь на малое расстояние к точкам в ту сторону, где их больше, мы суммарное расстояние уменьшаем. Тогда экстремума в них нет, а в "средних" точках он есть.

(16 Сен 0:29) falcao

Да, так нагляднее Ещё раз спасибо за помощь!

(16 Сен 0:41) Arkon

@Williams Wol...: я не смог увидеть документ -- сказано, что он удалён из общего доступа.

(16 Сен 2:26) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,735
×671
×91
×70

задан
15 Сен 21:53

показан
95 раз

обновлен
16 Сен 3:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru