MathLabs

第2問

n≥2n \ge 2 を整数とする。nn 個の要素からなる集合の 2n2^n 個の部分集合すべてを、ある順序で A1,A2,…,A2nA_1, A_2, \dots, A_{2^n} とする。次を証明せよ。 ∣A1∖A2∣+∣A2∖A3∣+⋯+∣A2n−1∖A2n∣+∣A2n∖A1∣≥2n−2.|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}.
ステップ 2/5: 各要素で ax=bxa_x=b_x を示す
前のステップ次のステップ
si=[x∈Ai]: #(1,0)-transitions=#(0,1)-transitionss_i=[x\in A_i]:\ \#(1,0)\text{-transitions}=\#(0,1)\text{-transitions}
詳しい解説

要素 xx を固定し、si=[x∈Ai]s_i=[x\in A_i] とおく。巡回的な 0/10/1 列 (si)(s_i) では、状態 11 から出る回数と状態 11 に入る回数が等しいので、(1,0)(1,0) 遷移の個数は (0,1)(0,1) 遷移の個数に等しい。したがって ax=bxa_x=b_x である。