Solving IMO 1989 #6 using Probability and Expectation

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}^{n} e_j = n\cdot\frac{1}{n} = 1$.

More is true. By the same argument, if we remove any partner pair $\{j,j+n\}$, the expected number of partner pairs in a random permutation of the remaining integers is still 1. This is the critical observation.

Conditional on the partner pair $\{j,j+n\}$ appearing in a random permutation, what is the expected number of partner pairs $e$? Observe that if $n>1$ it must be less than 2, since as before the expected number of partner pairs ignoring $\{j,j+n\}$ is 1, and the probability the $\{j,j+n\}$ pair where they appear has separated another partner pair is greater than 0.

Putting this together, if $n=1$ the property $P$ obviously holds. For $n>1$, note the expected number of partner pairs $E = p\cdot e$, where $p$ is the probability that a random permutation has property $P$ and $e$ is as before. But we already know $E=1$, and by the previous argument if $n>1$ we have $e<2$, hence $1 = p\cdot e < 2p$ and we conclude $p > \frac{1}{2}$.