Доказательство для случая, когда все значения различны

Предполагается, что значения отсортированы по возрастанию.

Идея доказательства для чётного числа точек n = 2*i.

В этом случае i- номер точки, соответствующей медиане. Точнее, медиана находятся в интервале [a(i), a(i+1)).

Тогда для x из интервала [a(i), a(i+1)) сумма выглядит так: половина слагаемых имеет вид x-a(j), вторая половина a(k) - x. В сумме все x сокращаются, результат становится равным S_0 = sum(a(k), k>i) - sum(a(j), j<=i)

Сдвинем x в интервал (a(i-1), a(i)). Сумма станет равна S_1 = sum(a(k), k>i+1) + a(i+1) - x + a(i) - x - sum(a(j), j<i) = S_0 + 2*a(i) - 2*x

Так как a(i) > x, то S_1 > S_0. Если сдвинуть x ещё дальше, между a(i-1) и a(i-2) , то сумма будет S_2 = S_1 + 2*a(i-1) - 2*x > S_1 > S_0. Можно по индукции показать, что для каждого последующего интервала сумма будет возрастать.

Теперь сдвинем x в интервал (a(i+1), a(i+2)), тогда сумма будет равна S_1' = sum(a(k), k>i+1) + x - a(i+1) + x - a(i) + sum(a(j), j<i) = S_0 - 2*a(i+1)+2*x

Так как в этом случае x > a(i+1) то S_1' > S_0.

Если сдвинуть x дальше, между a(i+2) и a(i+3), то сумма S_2' = S_1' + 2*x - 2*a(i+2) > S_1' > S_0. Опять индукцией можно показать, что по мере удаления от a(i) сумма будет только расти.

Следовательно, для чётного числа точек минимум достигается в точках интервала (a(i), a(i+1)), в том числе в медиане (a(i) + a(i+1))/2)

Теперь нечётное число точек n = 2*i + 1

Медиана равна a(i+1). Сумма в медиане равна S_0 = sum(a(k), k > i+1) + sum(a(j), j < i+1)

Если x сдвинуть в интервал (a(i), a(i+1)), то сумма будет S_1 = S_0 + a(i+1) - x > S_0.

Если x сдвинуть в интервал (a(i+1), a(i+2)), то сумма будет S_1' = S_0 + x - a(i+1) > S_0.

Следовательно, для нечетного числа точек минимум достигается в медиане a(i+1).

Дополнение для случая, когда некоторые значения совпадают

Я оставлю текст ниже, он почти верный. Нужно отдельно рассмотреть вариант, когда медиана исходной последовательности не совпадает с медианой упрощённой последовательности.

Этот случай можно доказать как предыдущий, считая значения различными, но в сумме введя вес.

S = sum(w(i)*|a(i)-x|, 1 <= i <=n), где w(i) - сколько раз повторяется a(i) в исходной последовательности. То есть все w(i) целые числа не меньше единицы.

Тогда при сдвигании x относительно медианы сумма будет увеличиваться не на значение 2*|x-a(i)|, а на значение 2*w(i)*|x-a(i)| > 0. То есть минимум в медиане.