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

ステップ 3/5: 目標の和を書き換える

\sum_x(a_x+b_x)=2\sum_x a_x \implies \sum_i|A_i\setminus A_{i+1}|=\tfrac12\sum_x(a_x+b_x)

詳しい解説

$a_x=b_x$ をすべての要素について足すと $\sum_xa_x=\sum_xb_x$ となる。したがって求める和は $\sum_x(a_x+b_x)$ の半分である。