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 4 of 5: No two consecutive terms vanish

Previous step Next step

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

Detailed analysis

For a transition $A_i\to A_{i+1}$ , $a_i+b_i$ counts the elements whose membership changes. It is zero exactly when $A_{i+1}=A_i^c$ . Two consecutive zero terms would give $A_{i+2}=A_i$ , impossible because all listed subsets are distinct.