第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)$ 的一半。