China Western Mathematical Olympiad

(1) We prove by mathematical induction that there exists a sequence $A_1,A_2,\dots ,A_{2^n}$ such that $A_1=\{1\},A_{2^n}=\varnothing$ and satisfies the condition in (1). When $n=2$, the sequence $\{1\},\{1,2\},\{2\},\varnothing$ of $\{1,2\}$ works. Assume that when $n=k$, there exists such a sequence $B_1,B_2,\dots ,B_{2^k}$ of subsets of $\{1,2,\dots ,k\}$. As for $n=k+1$, one can construct a sequence of subsets of $\{1,2,\dots ,k+1\}$, as follows: $$\begin{array}{rl}{A}_1& =B_1=\{1\},\\ A_i& =B_{i-1}\cup \{k+1\},i=2,3,\dots ,2^k+1,\\ A_j& =B_{j-2^k},j=2^k+2,2^k+3,\dots ,2^{k+1}.\end{array}$$ One can easily check that the sequence fulfills the required conditions stated above. By induction we have proved (1) for $n\ge 2$.

(2) We will show that the sum is $0$, independent of the arrangement. Without loss of generality, we may assume that $A_1=\{1\}$, otherwise shift the index cyclically. It follows from $|A_{i+1}|=|A_i|+1$ or $|A_i|-1$ that their parities are different, and hence the parities of the index label of any subset and its cardinality are the same. It follows that ${\sum }_{i=1}^{2^n}(-1{)}^{i}S(A_i)={\sum }_{A\in P}S(A)-{\sum }_{A\in Q}S(A)$, where $P$ consists of all subsets of $\{1,2,\dots ,n\}$ with even numbers of elements, and $Q$ consists of all subsets of $\{1,2,\dots ,n\}$ with odd numbers of elements. For any $x\in \{1,2,\dots ,n\}$, among all $k$-element subsets, $x$ appears in exactly $C_{n-1}^{k-1}$ of them, hence it contributes to the sum $$\sum _{A\in P}S(A)-\sum _{A\in Q}S(A)\text{ as }-C_{n-1}^0+C_{n-1}^1-C_{n-1}^2+\cdots +(-1{)}^n{C}_{n-1}^{n-1}=-(1-1{)}^{n-1}=0.$$ Therefore, ${\sum }_{i=1}^{2^n}(-1{)}^{i}S(A_i)=0$. $\square$