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}.
ステップ 5/5: 不等式を結論する
前のステップ次のステップ
#{i:ai+bi=0}≤2n−1⟹∑x(ax+bx)≥2n−1⟹∑i∣Ai∖Ai+1∣≥2n−2\#\{i:a_i+b_i=0\}\le2^{n-1}\Longrightarrow\sum_x(a_x+b_x)\ge2^{n-1}\Longrightarrow\sum_i|A_i\setminus A_{i+1}|\ge2^{n-2}
詳しい解説

ゼロの項は長さ 2n2^n の巡回グラフの独立集合をなすので、高々 2n−12^{n-1} 項しかゼロにならない。他の項はすべて少なくとも 11 だから ∑x(ax+bx)≥2n−1\sum_x(a_x+b_x)\ge2^{n-1}。第3段階から求める下界 2n−22^{n-2} が従う。