[USAMO 1999 submission, Titu Andreescu]
Let $n$ be an odd integer greater than $1$. Find the number of permutations $p$ of the set $\{ 1, 2, …, n\}$ for which $$\def\x#1{\lvert p(#1)-#1\rvert} \x1+\x2+\cdots+\x n = \frac{n^2-1}2.$$
The solution is the following:
My problem is that I can’t understand anything from line 4 of the solution (the line that starts with “The maximum…”) and on. Please help me understand!
Best Answer
The previous line is of the form
$\sum_{i=1}^n |a_i - b_i | = \sum_{i=1}^n \pm a_i + \sum_{i=1}^n \pm b_i$.
More accurately, one necessary condition is that $n$ of these terms must be $-$, and $n$ of these terms must be $+$.
(Note that this isn't a sufficient condition. Another condition that we need is $a_i$ is negative iff $b_i $ is positive and $a_i \leq b_i$ )
Generally speaking, how can we maximize this sum, subject to the (first) condition?
Which terms do we want a $-$ sign in front of, which terms dow we want a $+$ sign in front of?
Apply that to this specific case, to obtain the 4th line.
(Verify that the second condition is satisfied, so that this can be achieved and is truly a maximum, not just an upper bound - pet peeve of mine.)
Note that $n$ is an odd integer, so $ \frac{ n+1}{2}$ is an integer.