IMO 1989 Problem 6

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.