IMO 1989 · Problem 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,\ldots,2n-1\}\). Show that, for each \(n\), there are more permutations with property \(P\) than without.

Official text of the problem. Official problem paper (PDF)

Solution

For \(n=1\), both permutations have property \(P\). Hence assume \(n\ge2\).

For each \(j\in\{1,\ldots,n\}\), let \(A_j\) be the set of permutations in which \(j\) and \(j+n\) are consecutive. The permutations with property \(P\) are exactly those in \(A_1\cup\cdots\cup A_n\).

Treating \(j\) and \(j+n\) as one block leaves \(2n-1\) objects to arrange. The block has two possible internal orders, so \[ |A_j|=2(2n-1)!. \] For distinct \(j,k\), the pairs \(\{j,j+n\}\) and \(\{k,k+n\}\) are disjoint. Treating both pairs as blocks similarly gives \[ |A_j\cap A_k|=4(2n-2)!. \]

We use the counting inequality \[ \left|\bigcup_{j=1}^{n}A_j\right| \ge \sum_{j=1}^{n}|A_j| -\sum_{1\le j<k\le n}|A_j\cap A_k|. \] Indeed, a permutation belonging to exactly \(r\) of these sets contributes \(r-\binom r2\) to the right-hand side. This is \(0\) when \(r=0\), and when \(r\ge1\), \[ r-\binom r2 =1-\frac{(r-1)(r-2)}2\le1, \] which is its contribution to the left-hand side.

Consequently, the number of permutations with property \(P\) is at least \[ \begin{aligned} 2n(2n-1)!-4\binom n2(2n-2)! &=(2n)!\left(1-\frac{n-1}{2n-1}\right)\\ &=\frac{n}{2n-1}(2n)!\\ &>\frac{(2n)!}{2}. \end{aligned} \] Since there are \((2n)!\) permutations altogether, more have property \(P\) than do not. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).