IMO 1989/6

[Phlembac Adib Hasan]

A permutation $ \{x_1, \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.

[Tahmid Hasan]

Seems rather simple, or I made some trivial mistakes! Could you please check?
Suppose $(x_1,...,x_1,...,x_j,...,x_{2n})$ is a permutation without the property $T$ and $|x_i-x_j|=n$ for some $1 \le i \neq j \le 2n$.
Consider the following bijection: $(x_1,...x_i,...,x_j,...,x_{2n}) \Rightarrow (x_1,...,x_i,x_j,...,x_{2n})$.
So for every permutation not having the property, we have constructed a permutation having the property.
Now consider the permutation $(1,2,3,...,2n)$. This permutation has the property but doesn't appear in any permutation considered before.
Hence the number of permutation with the property is obviously greater than the number of permutations without.

[*Mahi*]

Tahmid Hasan wrote:

Consider the following bijection: $(x_1,...x_i,...,x_j,...,x_{2n}) \Rightarrow (x_1,...,x_i,x_j,...,x_{2n})$.

Bijection means an one-to-one relation. The relation you described is many-to-many, and thus can't exactly be used to show an inequality (without counting something else like number of pairs with $|x_i-x_j|=n$)

[Tahmid Hasan]

Sorry, I meant to write injection . Now I see the bug, fixing $i$, which obviously fixes $j$ removes the bug.

[*Mahi*]

Tahmid Hasan said:

Sorry, I meant to write injection . Now I see the bug, fixing $i$, which obviously fixes $j$ removes the bug.

That is still many to one, for example with $i=1$ (or minimum $i$), both $(1,2,3,4)$ and $(1,2,4,3)$ will map to $(1,3,2,4)$.

[Tahmid Hasan]

But $(1,2,4,3)$ has the property $T$. That's not how I defined the injection!

[*Mahi*]

Okay, but does that actually matter? The fact here is, even if you fix $i$, for all of the positions of $j$ (with all the other integers in the same serial) you will get the same permutation, and thus it is a many-to-one relation, which in turn nullifies the validity of the proof.