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
![](https://latex.codecogs.com/png.latex?\bg_white \sigma)
is such that
![](https://latex.codecogs.com/png.latex?\bg_white \sum_{j=1}^n a_jb_{\sigma(j)})
is maximised.
3. Suppose there is a pair
![](https://latex.codecogs.com/png.latex?\bg_white i<j)
with
![](https://latex.codecogs.com/png.latex?\bg_white y_{\sigma(i)}>y_{\sigma(j)})
. Unless
![](https://latex.codecogs.com/png.latex?\bg_white x_i=x_j)
, the permutation
![](https://latex.codecogs.com/png.latex?\bg_white \sigma')
which agrees with sigma except at i and j, and sends i and j to
![](https://latex.codecogs.com/png.latex?\bg_white \sigma(j),\sigma(i))
respectively makes the sum strictly larger (contradicting maximality).
4. So if the sum is maximal then for every pair
![](https://latex.codecogs.com/png.latex?\bg_white i<j)
with
![](https://latex.codecogs.com/png.latex?\bg_white y_{\sigma(i)}>y_{\sigma(j)})
, we have
![](https://latex.codecogs.com/png.latex?\bg_white x_i=x_j)
. We can then perform the interchange in (3) pairwise without changing the sum, until we have the
![](https://latex.codecogs.com/png.latex?\bg_white y_{\sigma(j)})
increasing and hence equal to
![](https://latex.codecogs.com/png.latex?\bg_white y_j)
. This completes the proof.