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 5 of 5: Beat half of all permutations

Previous step Next step

In plain words

A strict majority is exactly the required comparison with permutations without P.

2n^2(2n-2)!>\frac{(2n)!}{2}\quad\Longrightarrow\quad |A|>\frac{(2n)!}{2}

Detailed analysis

Since $(2n)!=2n(2n-1)(2n-2)!$ , the inequality $2n^2(2n-2)!>(2n)!/2$ is equivalent to $2n>2n-1$ , which is true. Thus more than half of all $(2n)!$ permutations lie in $A$ and have property $P$ ; the remaining permutations are fewer, completing the proof.