Problem 6

A permutation

(x_1,x_2,\ldots,x_{2n})

\{1,2,\ldots,2n\}

has property

P

|x_i-x_{i+1}|=n

for at least one

i\in\{1,\ldots,2n-1\}

. Prove that for every positive integer

n

there are more permutations with property

P

than without it.

Step 1 of 5: Encode property P by events

Previous step Next step

In plain words

Each possible difference- $n$ adjacency is one event; property $P$ is their union.

A_k=\{\pi: k\text{ and }k+n\text{ are adjacent}\},\qquad P=\bigcup_{k=1}^{n}A_k

Detailed analysis

For $1\le k\le n$ , let $A_k$ consist of permutations in which the two numbers $k$ and $k+n$ occupy neighboring positions. Having property $P$ means belonging to at least one such set, so the desired permutations form $A=\bigcup_{k=1}^n A_k$ .