Question

1) Вдоль прямолинейной дороги расположены N домов. Где на этом шоссе нужно вырыть колодец, чтобы сумма расстояний от домов до колодца была минимальной? 2) Даны числа $a_1\ \textless \ a_2\ \textless \ \ldots \ \textless \ a_N.$ Найти x, при которых функция
принимает наименьшее значение.
Объяснить, почему в некотором смысле это не две задачи, а одна, и решить ее.

$y=|x-a_1|+|x-a_2|+\ldots +|x-a_N|$

Answer 1

Объяснение:

1) Если количество домов N четное, то колодец можно поставить в любом месте между N/2 и (N/2 + 1) домом.

Например, если домов всего 2, то между 1 и 2 домами.

Обозначим S расстояние между домами.

Житель 1 дома пройдет до колодца расстояние x, а житель 2 дома расстояние S-x.

В сумме они пройдут x + S - x = S, то есть расстояние между домами.

Точно также, если домов 4, то колодец ставим между домами 2 и 3.

Тогда 1 и 4 жители вместе пройдут S, а 2 и 3 жители вместе пройдут s1 - расстояние между 2 и 3 домом.

Сумма равна S + s1.

Если же поставить колодец, например, между домами 1 и 2, то 2 житель пройдет расстояние y от 2 дома до колодца, а 3 житель (s1+y) - сначала s1 от 3 дома до 2, а потом ещё y до колодца.

В сумме получится

S + y + s1 + y = S + s1 + 2y > S + s1

Если же количество домов N нечетно, то ставить колодец надо во дворе среднего дома (N+1)/2.

Например, если домов 3, то ставим колодец около 2 дома.

Тогда для 1 и 3 жителя сумма расстояний будет по-прежнему S, а расстояние для 2 жителя будет 0.

Сумма всех расстояний равна S + 0 = S.

Точно также, для 5 домов колодец нужно ставить возле 3 дома, для 7 - возле 4, и т.д.

2) y = |x-a1| + |x-a2| + ... + |x-a(N)|

Это по сути та же задача.

y - сумма расстояний (модули - это расстояния между точками)

x - положение колодца

a1, a2, ... a(N) - положения домов.

И доказательство точно такое же.

Если N четно, то x может быть любым от a(N/2) до a((N+1)/2).

Если N нечетно, то x = a((N+1)/2)