第2問

n \ge 2

を整数とする。

n

個の要素からなる集合の

2^n

個の部分集合すべてを、ある順序で

A_1, A_2, \dots, A_{2^n}

とする。次を証明せよ。

|A_1\setminus A_2| + |A_2\setminus A_3| + \cdots + |A_{2^n-1}\setminus A_{2^n}| + |A_{2^n}\setminus A_1| \ge 2^{n-2}.

ステップ 1/5: 遷移の個数を設定する

前のステップ次のステップ

a_x:=\#\{i:x\in A_i\setminus A_{i+1}\},\quad b_x:=\#\{i:x\in A_{i+1}\setminus A_i\},\quad i=1,\dots,2^n\ (\text{indices mod }2^n)

詳しい解説

集合を法 $2^n$ で巡回的に番号付けする。各要素 $x$ について、 $A_i$ に属するが $A_{i+1}$ に属さない遷移の個数を $a_x$ 、逆向きの遷移の個数を $b_x$ とする。すると求める和は $\sum_i|A_i\setminus A_{i+1}|=\sum_x a_x$ である。