Задача 110748

Темы:    [ Выпуклый анализ и линейное программирование ] [ Неравенства с модулями ]

Сложность: 6- Классы: 10,11

Условие

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

d_i = MAX { a_j | 1 ≤ j ≤ i } - MIN { a_j | i ≤ j ≤ n }
d = MAX { dⁱ | 1 ≤ i ≤ n }

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

MAX { |x_i - a_i| | 1 ≤ i ≤ n } ≥ d/2.

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

Решение

Автор: Канель-Белов А.Я.

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

2. Предположим противное
|x_i - a_i| < d/2 для любого i от 1 до n
Заметим, что d_i = a_k - a_l для некоторых 1 ≤ k ≤ i и i ≤ l ≤ n
Теперь d_i = (a_k - x_a) + (x_k - x_a) + (x_l - a_l) ≤ |a_k - x_k| + |x_l - a_l| < d

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

Для п.б) положим x_i = MAX { a_i | 1 ≤ i ≤ n } - d/2.

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

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