MathLabs

第6题

若集合 {1,2,…,2n}\{1,2,\ldots,2n\} 的排列 (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) 满足对于至少一个 i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\} 有 ∣xi−xi+1∣=n|x_i-x_{i+1}|=n，就称其具有性质 PP。证明对每个正整数 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,其余排列更少,证毕。