Отзывы пользователей

Даны числа а1, ..., аn

Даны числа а1, ..., аn.
Для 1 ≤ in положим

di = MAX { aj | 1 ≤ ji } - MIN { aj | ijn }
d = MAX { di | 1 ≤ in }

а) Доказать, что для любых x1x2 ≤ ... ≤ xn выполняется неравенство

MAX { |xi - ai| | 1 ≤ in } ≥ d/2.


б) Доказать, что равенство в (*) выполняется для некоторых {xi} i=1...n

Решение.

1. Заметим, что функция |x - R| кусочно линейна, точка нелинейности при x = R. Кроме того, в процессе движения по параметру максимум/минимум линейной функции достигается на границе.
Таким образом, задача сводится к случаю, когда xi = aj(i), а такой случай проверяется непосредственно.

2. Предположим противное
|xi - ai| < d/2 для любого i от 1 до n
Заметим, что di = ak - al для некоторых 1 ≤ ki и iln
Теперь di = (ak - xa) + (xk - xa) + (xl - al) ≤ |ak - xk| + |xl - al| < d

Следовательно, d = MAX di < d - противоречие.

Для п.б) положим xi = MAX { ai | 1 ≤ in } - d/2.
 
Поделиться: