International Mathematical Olympiad 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.