第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}.

ステップ 4/5: 隣り合う二項は同時にゼロにならない

a_i+b_i=0\iff A_{i+1}=A_i^c

詳しい解説

遷移 $A_i\to A_{i+1}$ で、 $a_i+b_i$ は所属が変わる要素数である。これは $A_{i+1}=A_i^c$ のとき、かつそのときに限りゼロである。隣り合う2項がゼロなら $A_{i+2}=A_i$ となり、列挙した集合が相異なることに反する。