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

第 1/5 步：设置转移计数

a_x:=\#\{i:x\in A_i\setminus A_{i+1}\},\quad b_x:=\#\{i:x\in A_{i+1}\setminus A_i\},\quad i=1,\dots,2^n\ (\text{indices mod }2^n)

详细分析

将各集合按模 $2^n$ 循环编号。对每个元素 $x$ ，记属于 $A_i$ 但不属于 $A_{i+1}$ 的转移数为 $a_x$ ，反向转移数为 $b_x$ 。则所求之和为 $\sum_i|A_i\setminus A_{i+1}|=\sum_x a_x$ 。