# Find a permutation $\sigma$ maximizing the sum $\sum_{i=1}^n {a_i \over \sigma(i)}$.

Given $$a_1< a_2<\dots < a_n,$$

find a permutation $$\sigma$$ maximizing the sum >$$\sum_{i=1}^n {a_i \over \sigma(i)}.$$

I can't figure our where to begin. I know that the solution is $$\sigma=e$$, but I cannot prove it.

• Maybe worth trying: without loss of generality, assume the $a_i$'s are non-decreasing, and use the rearrangement inequality? – Clement C. Jul 16 '16 at 14:48
• After the edit, and to provide more details to my previous comment: en.m.wikipedia.org/wiki/Rearrangement_inequality – Clement C. Jul 16 '16 at 14:56
• For the answer to be $\sigma=e$, I think you need $a_1>a_2>\cdots>a_n$. – Thomas Andrews Jul 16 '16 at 14:57
• Sorry for the lack of information. I edited it. – Razvan Paraschiv Jul 16 '16 at 14:59
• Imagine $a_n$ is huge compared to the other terms. Then the maximum sum will certainly have $\sigma(n)=1$ – Joffan Jul 16 '16 at 15:08