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

第 5/5 步：得出不等式

\#\{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}

详细分析

零项构成长度为 $2^n$ 的循环图中的独立集，故至多有 $2^{n-1}$ 项为零。其余各项至少为 $1$ ，所以 $\sum_x(a_x+b_x)\ge2^{n-1}$ 。由第三步即得所需下界 $2^{n-2}$ 。