Problem
ALG-B2-M04-P024 Sum with an arbitrary cycle
#24
★★★★★ Level 5 of 5
Let \(a_1,a_2,\ldots,a_n>0\), and let \(\sigma\) be any permutation of \(1,2,\ldots,n\). Prove \[\sum_{i=1}^n a_i^{m+1}\ge\sum_{i=1}^n a_i^m a_{\sigma(i)}\] for every positive integer \(m\).
Hint. Order the \(a_i\). Then \(a_i^m\) are ordered in the same way, and the right side is one of the product permutations.
Reorder the numbers as \(u_1\le\cdots\le u_n\). Then \(u_1^m\le\cdots\le u_n^m\). By rearrangement, the maximum of \(\sum u_i^m u_{\tau(i)}\) is attained at \(\tau(i)=i\), and equals \(\sum u_i^{m+1}\). The right side of the original inequality corresponds to some permutation \(\tau\), so it is not larger.
Final module problem: it combines permutations, powers, and a general parameter.