Ремонт в аэропорту

[wpoms.]

В аэропорту для обозначения зала ожидания проведены `n` параллельных линий длины `a_1 <= a_2 <= a_3 <= ... <= a_n`. Однако архитектор решил, что все линии должны иметь одинаковую длину. Известно, что стоимость метра продления линий (дополнительной покраски) равна стоимости уменьшения длины (стирания лишней покраски). Какую длину должны иметь линии для того, чтобы свести к минимуму затраты на переделку?

@темы: Задачи на экстремум

Comments

[Adjirranirr]

При `a_1 = a_2 = a_3 = ... = a_n` затраты, очевидно, будут нулевыми.

[Trotil]

Тут, наверное, надо дать какую-то оценку.
Например, очень грубая оценка: затраты не будут превышать `(a_n-a_1)*n`.

[All_ex]

Тут, наверное, надо дать какую-то оценку. - По-моему, оценка тут ни при чём... надо ведь не затраты найти, а длину...
При `a_1 = a_2 = a_3 = ... = a_n` затраты, очевидно, будут нулевыми. - это конечно так... но ведь неравенства написаны...


Построим из выборки `a_1 <= a_2 <= ... <= a_n` вариационный ряд...
Пусть длина `A_1` встречается `n_1` раз, `A_2` встречается `n_2` раз, ..., `A_m` встречается `n_m` раз. При этом `A_1 < A_2 < ... < A_m, \ \ n_1 + n_2 + ... + n_m = n`...
Рассмотрим величину новой дины всех полос после перекраски - `A` ... при этом затраты на перекраску равны `f(A) = sum_{k=1}^{m} n_k * |A_k - A|`

Предположим, что `A_s <= A < A_{s+1}`... и рассмотрим величину `epsilon > 0`, при которой `A_s < A + epsilon <= A_{s+1}`... При этом полосы меньшей длины будут докрашены на `epsilon`, что увеличивает расходы... а большей длины будут меньше стёрты, что уменьшает расходы...
Обозначим накопленную частоту `N_s = sum_{k=1}^{s} n_k`... Тогда `f(A + epsilon) = f(A) + epsilon*N_s - epsilon*(n - N_s) ` или `f(A + epsilon) - f(A) = epsilon*(2*N_s - n)`... откуда видно, что при `(2*N_s - n) > 0` расходы растут, а при `(2*N_s - n) < 0` - убывают...
Следовательно, минимум достигается при `(2*N_s - n) = 0`...

Но здесь возможны варианты...
1) Если найдётся `s`, при котором `2*N_s = n`, то `A_{min}` может быть любым из отрезка `[A_s; A_{s+1}]`...
2) Если найдётся `s`, при котором `2*N_{s-1} < n \ & \ 2*N_s > n`, то `A_{min} = A_s` ...

В общем всё это напоминает нахождение выборочной медианы....

[Adjirranirr]

но ведь неравенства написаны...

Написаны, да. Нестрогие. И спрашивается, а какими должны быть величины `a_i,\ i = \bar(1,n)`, чтобы их можно было уравнять с минимальным убытком. Очевидно, равными и должны быть.

Какой вопрос, такой ответ =)

[All_ex]

Adjirranirr, Какой вопрос, такой ответ =) - ну, да... вопрос поставлен не ахти... переводчика на мыло...