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 5 of 5: Conclude the bound

Previous step Next step

\#\{i:a_i+b_i=0\}\le2^{n-1}\Longrightarrow\sum_x(a_x+b_x)\ge2^{n-1}\Longrightarrow\sum_i|A_i\setminus A_{i+1}|\ge2^{n-2}

Detailed analysis

The zero terms form an independent set in the cycle of length $2^n$ , so at most $2^{n-1}$ terms vanish. Every other term is at least $1$ , hence $\sum_x(a_x+b_x)\ge2^{n-1}$ . Step 3 gives the required lower bound $2^{n-2}$ .