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

第 4/5 步：相邻两项不能同时为零

a_i+b_i=0\iff A_{i+1}=A_i^c

详细分析

对转移 $A_i\to A_{i+1}$ ， $a_i+b_i$ 是成员资格发生变化的元素数。它为零当且仅当 $A_{i+1}=A_i^c$ 。若相邻两项均为零，则 $A_{i+2}=A_i$ ，这与列出的子集互异矛盾。