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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.