MathLabs

第6問

集合 {1,2,…,2n}\{1,2,\ldots,2n\} の順列 (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) が性質 PP を持つとは、ある i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\} について ∣xi−xi+1∣=n|x_i-x_{i+1}|=n となることである。任意の正整数 nn に対し、性質 PP を持つ順列の方が持たない順列より多いことを証明せよ。
ステップ 5/5: 全順列の半分を超える
前のステップ次のステップ
ざっくり言うと

過半数を厳密に超えることが、P を持たない順列より多いという結論である。

2n2(2n−2)!>(2n)!2⟹∣A∣>(2n)!22n^2(2n-2)!>\frac{(2n)!}{2}\quad\Longrightarrow\quad |A|>\frac{(2n)!}{2}
詳しい解説

(2n)!=2n(2n−1)(2n−2)!(2n)!=2n(2n-1)(2n-2)! なので、2n2(2n−2)!>(2n)!/22n^2(2n-2)!>(2n)!/2 は 2n>2n−12n>2n-1 と同値であり真である。したがって全 (2n)!(2n)! 順列の半数以上が AA、すなわち性質 PP を持ち、残りはそれより少ない。