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}^{...