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 1 of 5: Set up transition counts

Previous step Next step

a_x:=\#\{i:x\in A_i\setminus A_{i+1}\},\quad b_x:=\#\{i:x\in A_{i+1}\setminus A_i\},\quad i=1,\dots,2^n\ (\text{indices mod }2^n)

Detailed analysis

Index the sets cyclically modulo $2^n$ . For each element $x$ , let $a_x$ count transitions in which x belongs to $A_i$ but not $A_{i+1}$ , and let $b_x$ count transitions in the opposite direction. Then the target sum is $\sum_i|A_i\setminus A_{i+1}|=\sum_x a_x$ .