Задача
ALG-B2-M04-P024 Сумма с произвольным циклом
#24
★★★★★ Уровень 5 из 5
Пусть \(a_1,a_2,\ldots,a_n>0\), а \(\sigma\) - любая перестановка чисел \(1,2,\ldots,n\). Докажите \[\sum_{i=1}^n a_i^{m+1}\ge\sum_{i=1}^n a_i^m a_{\sigma(i)}\] для любого натурального \(m\).
Подсказка. Упорядочьте \(a_i\). Тогда \(a_i^m\) упорядочены так же, а правая часть является одной из перестановок произведений.
Переупорядочим числа: \(u_1\le\cdots\le u_n\). Тогда \(u_1^m\le\cdots\le u_n^m\). По rearrangement максимальная сумма \(\sum u_i^m u_{\tau(i)}\) достигается при \(\tau(i)=i\), то есть равна \(\sum u_i^{m+1}\). Правая часть исходного неравенства соответствует некоторой перестановке \(\tau\), поэтому она не больше.
Итоговая задача модуля: она объединяет перестановки, степени и общий параметр.