Пусть координаты точек x₁, ..., x_N не убывают (если это не так, то просто отсортируем предварительно последовательность).

Предположим, что мы нашли точку z, и она лежит на интервале (x[i],x[i+1]). Справа от нее i точек, слева - N-i. Сумма расстояний Smin будет такой:

Smin=(z-x[1])+ ... +(z-x[i])+(x[i+1]-z)+ ... +(x[N]-z).

Предположим, что i>N-i и мы в пределах интервала сдвигаем точку z влево на какую-то маленькую величину d (d<z-x[i]). Получаем новую сумму S

S=(z-d-x[1])+ ... +(z-d-x[i])+(x[i+1]-(z-d))+ ... +(x[N]-(z-d))=Smin-d*i+d*(N-i).

А так как, по предположению, i>N-i, то S<Smin !?

Ситуация, когда N-i>i, исследуется аналогично - мы делаем сдвиг на величину d<x[N+1] - z вправо, не выходя при этом за границы интервала, и опять же получаем, что новая сумма S<Smin. Случай, когда z совпадает с одной из точек x[i] исследуется так же, как и выше, используя маленькие сдвиги.

Следовательно, для того, чтобы точка z была искомой, необходимо и достаточно, чтобы справа и слева от нее лежало одно и то же число точек. Если N=2k, то точка z может быть любой из точек отрезка [x[k],x[k+1]], если же N=2k+1, то точка z=x[k+1].

Пусть мы решаем задачу для N точек на прямой.

Точка z должна, очевидно, лежать на отрезке [x[1],x[N]].

Если N=1, то данная точка и является искомой.

Если N=2, то z может лежать где угодно на отрезке [x₁,x_N] - суммарное расстояние будет одинаковым и равным длине отрезка.

Если N>2, то суммарное расстояние от точки z до точек с минимальной и максимальной координатами (т.е. до точек x₁ и x_N) не зависит от местоположения точки z и равно длине отрезка [x₁, x_N]. Так как суммарное расстояние до этих двух точек постоянно, то поэтому мы можем их отбросить, и решать задачу уже для N-2 точек x₂,...,x_N-1. Проведя необходимое число раз сокращение количества точек, мы придем к уже рассмотренным случаям одной или двух точек.

Окончательно получаем: если N=2k, то точка z может быть любой из точек отрезка [x_k,x_k+1], если же N=2k+1, то точка z=x[k+1].