第6問

集合

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

の順列

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

が性質

P

を持つとは、ある

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

について

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

となることである。任意の正整数

n

に対し、性質

P

を持つ順列の方が持たない順列より多いことを証明せよ。

ステップ 1/5: 性質Pを事象で表す

ざっくり言うと

差が $n$ の隣接を1つの事象とし、性質 $P$ はその合併である。

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

詳しい解説

$1\le k\le n$ に対し、数 $k$ と $k+n$ が隣接する順列全体を $A_k$ とする。性質 $P$ は少なくとも1つの集合に属することなので、求める順列は $A=\bigcup_{k=1}^n A_k$ である。