1989 IMO SL #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.

We generalize this for all $0\le r\le n$. 

Let $A$ be the set of permutations that do not satisfy $P(r)$, and let $B$ be the set of permutation that do satisfy $P(r)$. Define $f:A\longrightarrow B$ as $$f(x_1x_2\ldots x_{2n})=x_2x_3\ldots x_1x_s\ldots x_{2n}$$where $s=\min{\{x_s\,|\, |x_s-x_1|=r\}}$, which is possible because $r\le n$. We claim that $f$ is injective. Suppose $f(a)=f(b)$, implying $$a_2a_3\ldots a_1a_s\ldots x_{2n}=b_2b_3\ldots b_1b_r\ldots x_{2n}.$$ Note that $(a_1,a_s),(b_1,b_r)$ are the only pairs that satisfy $|x_s-x_1|=r$, so $s=r$ and hence $a_i=b_i$ for all $i$, which implies that $a=b$ and that $f$ is injective. However, now there are permutations that have more than one pair of numbers that satisfy $P(r)$ which are obviously not attainable by $f$. Hence, $f$ is injective but not surjective, implying $|A|<|B|$, as desired. $\square$