Задача 61385

Темы:    [ Классические неравенства (прочее) ] [ Перестановки и подстановки (прочее) ] [ Инварианты и полуинварианты ]

Сложность: 3 Классы: 8,9,10,11

Условие

Докажите, что если   a₁ ≥ a₂ ≥ ... ≥ a_n,   b₁ ≥ b₂ ≥ ... ≥ b_n,   то наибольшая из сумм вида   a₁b_k1 + a₂b_k2 + ... + a_nb_kn     (k₁, k₂, ..., k_n – перестановка чисел
1, 2, ..., n),  это сумма   a₁b₁ + a₂b₂ + ... + a_nb_n,   а наименьшая – сумма   a₁b_n + a₂b_n–1 + ... + a_nb₁.

Решение

  Заметим, что если  x ≥ y,   z ≥ w  , то   xz + yw ≥ xw + yz.   Действительно,   (xz + yw) – (xw + yz) = (x – y)(z – w) ≥ 0.
  Рассмотрим в сумме   a₁b_k1 + a₂b_k2 + ... + a_nb_kn   член a_jb₁, содержащий множитель b₁. Если  j > 1,  то, заменив   a_j–1b_kj–1 + a_jb₁   на   a_j–1b₁ + a_jb_kj–1,   мы не уменьшим сумму. Так можно продолжать, пока множитель b₁ не перейдёт в первое слагаемое. Затем поступим так же с множителем b₂ и т. д. В конце концов мы превратим нашу сумму в   a₁b₁ + a₂b₂ + ... + a_nb_n,   не уменьшив её.
  Аналогично доказывается, что сумма   a₁b_n + a₂b_n–1 + ... + a_nb₁   – наименьшая.

Замечания

Обычно утверждение задачи называют транснеравенством.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	16
Название	Неравенства
Тема	Алгебраические неравенства и системы неравенств
задача
Номер	047
книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	10
Название	Неравенства
Тема	Алгебраические неравенства и системы неравенств
параграф
Номер	1
Название	Различные неравенства
Тема	Алгебраические неравенства (прочее)
задача
Номер	10.034