Олимпиадная задача по математике для 10–11 классов: выпуклый анализ, Канель-Белов
Даны числаа1, ...,аn. Для 1 ≤i≤nположим
di = MAX { aj | 1 ≤ j ≤ i } - MIN { aj | i ≤ j ≤ n }
d = MAX { di | 1 ≤ i ≤ n }
а) Доказать, что для любыхx1≤x2≤ ... ≤xnвыполняется неравенство
MAX { |xi - ai| | 1 ≤ i ≤ n } ≥ d/2.
б) Доказать, что равенство в (*) выполняется для некоторых {xi}i=1...n
Разобрать решение
Автор: [Канель-Белов А.Я.](https://mirolimp.ru/tasks?author%5Bvalue%5D=100277)
Решение. 1. Заметим, что функция |x - R| кусочно линейна, точка нелинейности приx = R. Кроме того, в процессе движения по параметру максимум/минимум линейной функции достигается на границе. Таким образом, задача сводится к случаю, когдаxi = aj(i), а такой случай проверяется непосредственно.
Предположим противное |xi-ai| <d/2 для любогоiот 1 доn Заметим, чтоdi=ak-alдля некоторых 1 ≤k≤iиi≤l≤n Теперьdi= (ak - xa) + (xk - xa) + (xl - al) ≤ |ak - xk| + |xl - al| <d
Следовательно,d= MAXdi<d- противоречие.
Для п.б) положимxi= MAX {ai| 1 ≤i≤n} -d/2.
Обсуждение
0Комментариев пока нет.