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 3 of 5: Rewrite the target sum

\sum_x(a_x+b_x)=2\sum_x a_x \implies \sum_i|A_i\setminus A_{i+1}|=\tfrac12\sum_x(a_x+b_x)

Detailed analysis

Summing $a_x=b_x$ over all elements gives $\sum_xa_x=\sum_xb_x$ , so the required sum is half of $\sum_x(a_x+b_x)$ .