IMO 1989 Problem 6

A more elegant solution not from me is at the bottom.

A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ 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 $ T$ than without.

=======================

Proof #1

We say that a pair of numbers are twins if they differ by $n$. Let $a_{2n,2k}$ be the number of permutations with at most a pair of neighboring twins such that the number of elements separated by them differ by $2k$. So $a_{2n,2n}$ is the number of permutations without $T$. For $k\notin\{n,-n\}$ we have $$a_{2n,2k}=a_{2n,2n}+2n\cdot a_{2n-2,2k}.$$ Moreover $$a_{2n,2n}=2n\left(a_{2n-2,2n-2}+a_{2n-2,2n-4}+\dots+a_{2n-2,4-2n}\right).$$ With some manipulation we get $$a_{2n,2n}=2n\left((2n-1)a_{2n-2,2n-2}+(2n-2)a_{2n-4,2n-4}\right).$$ Let $f(2n):=a_{2n,2n}/(2n)!$, then $$f(2n)=f(2n-2)+\frac{f(2n-4)}{(2n-1)(2n-3)}\le f(2n-2)+\frac{1}{2}(\frac{1}{2n-3}-\frac{1}{2n-1}).$$ Since $f(4)=1/3$, for $2n\ge6$ we have $$f(2n)\le \frac{1}{3}+\frac{1}{2}\left(\frac{1}{3}-\frac{1}{5}+\frac{1}{5}-\frac{1}{7}+\dots\right)<\frac{1}{2}.$$

Proof #2

Let $(x_1,\dots,x_{2n})$ be a permutation without $T$ and $x_k$ be the twin of $x_1$ where $k>2$, then $$f(x_1,\dots,x_{2n})=(x_2,\dots,x_{k-1},x_1,x_k,\dots,x_{2n})$$ has $T$. The mapping $f$ is injective but not surjective, so the inequality follows.