ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110748
Темы:    [ Выпуклый анализ и линейное программирование ]
[ Неравенства с модулями ]
Сложность: 6-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Даны числа а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.

Источники и прецеденты использования

олимпиада
Название Международная Математическая Олимпиада
год
Год 2007
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .