|
|
 |
Условие
Даны два набора чисел: a1, ..., an и b1, ..., bn. Расположим числа ak в возрастающем порядке, а числа bk – в убывающем порядке. Получатся наборы
A1 ≤ ... ≤ An, B1 ≥ ... ≥ Bn. Доказать, что max{a1 + b1, ..., an + bn} ≥ max{A1 + B1, ..., An + Bn}.
Решение
Перенумеруем числа в исходных наборах {ai}, {bi} так, что bi = Bi при всех i. Пусть для некоторых индексов k < l выполнено неравенство al < ak. Докажем, что если мы поменяем местами ak и al, то число {ak + bk} не возрастёт. Действительно, ak + bk ≥ ak + bl и
ak + bk ≥ al + bk.
С другой стороны ясно, что такими операциями можно из произвольной
перестановки чисел a1, ..., an можно получить перестановку A1, ..., An. Следовательно,
max{a1 + b1, ..., an + bn} ≥ max{A1 + B1, ..., An + Bn}.
