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 \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}. } 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…