Задача
Докажите, что если a1 ≥ a2 ≥ ... ≥ an, b1 ≥ b2 ≥ ... ≥ bn, то наибольшая из сумм вида a1bk1 + a2bk2 + ... + anbkn (k1, k2, ..., kn – перестановка чисел
1, 2, ..., n), это сумма a1b1 + a2b2 + ... + anbn, а наименьшая – сумма a1bn + a2bn–1 + ... + anb1.
Решение
Заметим, что если x ≥ y, z ≥ w , то xz + yw ≥ xw + yz. Действительно, (xz + yw) – (xw + yz) = (x – y)(z – w) ≥ 0.
Рассмотрим в сумме a1bk1 + a2bk2 + ... + anbkn член ajb1, содержащий множитель b1. Если j > 1, то, заменив aj–1bkj–1 + ajb1 на aj–1b1 + ajbkj–1, мы не уменьшим сумму. Так можно продолжать, пока множитель b1 не перейдёт в первое слагаемое. Затем поступим так же с множителем b2 и т. д. В конце концов мы превратим нашу сумму в a1b1 + a2b2 + ... + anbn, не уменьшив её.
Аналогично доказывается, что сумма a1bn + a2bn–1 + ... + anb1 – наименьшая.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь