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} = \emptyset$ and satisfies the condition in (1).
When $n = 2$, the sequence $\{1\}, \{1, 2\}, \{2\}, \emptyset$ 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{align*} A_1 &= B_1 = \{1\}, \\ A_i &= B_{i-1} \cup \{k+1\}, \quad i = 2, 3, \dots, 2^k + 1, \\ A_j &= B_{j-2^k}, \quad j = 2^k + 2, 2^k + 3, \dots, 2^{k+1}. \end{align*}$$
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 + \dots + (-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$