The Angry Statistician

IMO 1989 #6: A permutation $\{x_1, x_2, \ldots , x_m\}$ of the set $\{1, 2, \ldots , 2n\}$, where $n$ is a positive integer, is said to have property $P$ if $| x_i - x_{i+1} | = n$ for at least one $i$ in $\{1, 2, ... , 2n-1\}$. Show that for each $n$ there are more permutations with property $P$ than without. Solution: We first observe that the expected number of pairs $\{i, i+1\}$ for which $| x_i - x_{i+1} | = n$ is $E = 1$. To see this note if $j$, $1 \leq j \leq n$, appears in position $1$ or $2n$ it's adjacent to one number, otherwise two. Thus the probability it's adjacent to its partner $j+n$ in a random permutation is $$\begin{equation} \eqalign{ e_j &= \frac{2}{2n}\cdot \frac{1}{2n-1} + \frac{2n-2}{2n}\cdot \frac{2}{2n-1} \\ &= \frac{2(2n-1)}{2n(2n-1)} \\ &= \frac{1}{n}. } \end{equation}$$ By linearity of expectation we overall have the expected number of $j$ adjacent to its partner $j+n$ is \(\sum_{j=1}^{...