设 $n$ 是正整数，我们称集合 ${1,2,\cdots,2n}$ 的一个排列 $({x}_{1},{x}_{2},\cdots,{x}_{2n})$ 具有性质 $P$，是指在 ${1,2,\cdots,2n-1}$ 中至少有一个 $i$，使得 $\left| {{x}_{i}}-{{x}_{i+1}} \right|=n$．求证：对于任何 $n$，具有性质 $P$ 的排列比不具有性质 $P$ 的排列的个数多．（波兰）
【难度】
【出处】
1989年第30届IMO试题
【标注】
【答案】
略
【解析】
设排列 $(x_1,x_2,\cdots,x_{2n})$ 中 $k$ 与 $k+n$ 相邻的排列的集合为 $N_k(1\leqslant k\leqslant n)$，则具有性质 $P$ 的排列个数 $\displaystyle m\geqslant \sum\limits_{k=1}^n|N_k|-\sum_{1\leqslant k< l\leqslant n}|N_k\bigcap N_l|$，
因为 $|N_k|=2\times (2n-1)!,|N_k\bigcap N_l|=2^2\times (2n-2)!$（将 $k$ 与 $k+n,l$ 与 $l+n$ 并在一起，与剩下的 $2n-4$ 个数一起，有 $(2n-2)!$ 种排列，其中 $k$ 与 $k+n$，$l$ 与 $l+n$ 并成的"数"可以将 $k$ 与 $k+n$，$l$ 与 $l+n$ 交换位置，各有两种排列），所以
$\begin{aligned}
m&\geqslant 2n(2n-1)!-2^2\times (2n-2)!C_n^2\\
&=(2n)!-2n(n-1)(2n-2)!\\
&=2n\cdot (2n-2)!\cdot n\\
&>\frac{1}{2}\cdot (2n)!
\end{aligned}$
因为 $|N_k|=2\times (2n-1)!,|N_k\bigcap N_l|=2^2\times (2n-2)!$（将 $k$ 与 $k+n,l$ 与 $l+n$ 并在一起，与剩下的 $2n-4$ 个数一起，有 $(2n-2)!$ 种排列，其中 $k$ 与 $k+n$，$l$ 与 $l+n$ 并成的"数"可以将 $k$ 与 $k+n$，$l$ 与 $l+n$ 交换位置，各有两种排列），所以
$\begin{aligned}
m&\geqslant 2n(2n-1)!-2^2\times (2n-2)!C_n^2\\
&=(2n)!-2n(n-1)(2n-2)!\\
&=2n\cdot (2n-2)!\cdot n\\
&>\frac{1}{2}\cdot (2n)!
\end{aligned}$
答案
解析
备注
