Problem 2

Let

n \ge 2

be an integer. Let

A_1, A_2, \dots, A_{2^n}

be the

2^n

subsets of an

n

-element set, listed in some order. Prove that

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

Step 2 of 5: Show

a_x=b_x

for each element

Previous step Next step

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

Detailed analysis

Fix an element $x$ and let $s_i=[x\in A_i]$ . In the cyclic $0/1$ sequence $(s_i)$ , every departure from $1$ is balanced by an arrival at $1$ , so the number of $(1,0)$ transitions equals the number of $(0,1)$ transitions. Thus $a_x=b_x$ .