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
}>y_{\sigma(j)})
. Unless

, the permutation

which agrees with sigma except at i and j, and sends i and j to
,\sigma(i))
respectively makes the sum strictly larger (contradicting maximality).
4. So if the sum is maximal then for every pair

with
}>y_{\sigma(j)})
, 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.