- Get link
- Google+
- Other Apps

**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}\).

## Comments

## Post a Comment