Как из критерия унимодальности следует унимодальность функции?

Question

[Егор Полянский]

Добрый вечер! Дана задача (на первом скриншоте)

В этой задаче используется тернарный поиск, и мне нужно было доказать, что если функция f(x) является унимодальной, то ее максимум можно было бы искать тернарным поиском, то есть:
Рассмотрим переход от f(x) к f(x+1). Мы убираем 2 предмета веса 1 и добавляем предмет веса 2. С каждым разом предмет веса 2, которые мы добавляем, будет все хуже и хуже, а предметы веса 1, которыемы выкидываем, все лучше и лучше. Поэтому f(x+1) - f(x) <= f(x) - f(x-1) => функция унимодальна.

Я доказал это следующим образом:


Теперь мне следует доказать, что как из этого выражения f(x + 1) - f(x) <= f(x) - f(x -1) следует унимодальность функции?

Прошу помочь с этим вопросом!

Answer 1

[Wataru]

В унимодальной функции разности соседних элементов сначала неотрицательные а потом неположительные. И наоборот, если разности такие, то, очевидно, сначала функция возрастает (возможно, ступенчато) а потом убывает.

Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
2) они все неположительные. Монотонно убывающая функция.
3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.