Re: HSC 2015 4U Marathon - Advanced Level
How would you expand that?
Apologies, the method I had in mind does not quite work when you follow it through.
It is still quite an easy problem though.
1. Observe that the problem is trivial for n=2, with equality iff one of the sequences is constant.
2. Suppose
is such that
is maximised.
3. Suppose there is a pair
with
. Unless
, the permutation
which agrees with sigma except at i and j, and sends i and j to
respectively makes the sum strictly larger (contradicting maximality).
4. So if the sum is maximal then for every pair
with
, we have
. We can then perform the interchange in (3) pairwise without changing the sum, until we have the
increasing and hence equal to
. This completes the proof.