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

第 2/5 步：证明每个元素满足

a_x=b_x

s_i=[x\in A_i]:\ \#(1,0)\text{-transitions}=\#(0,1)\text{-transitions}

详细分析

固定元素 $x$ ，令 $s_i=[x\in A_i]$ 。在循环 $0/1$ 序列 $(s_i)$ 中，离开状态 $1$ 的次数等于回到状态 $1$ 的次数，因此 $(1,0)$ 型转移数等于 $(0,1)$ 型转移数，即 $a_x=b_x$ 。