Problem 1063

To prove (contribution method) that for any $x \in S$, it is sufficient to prove that the number of times $x$ is counted on both sides of (1) is the same.

If $x$ does not belong to any of the sets $S_{1}, S_{2}, \cdots, S_{n}$, then $x$ is counted 1 time on the left side of (1), and $x$ is counted 1 time in the first term $|S|$ on the right side of (1), while in the other summation terms on the right side of (1), $x$ is counted 0 times. Therefore, the total number of times $x$ is counted on the right side of (1) is also 1.

If $x$ belongs to exactly $k$ of the sets $S_{1}, \cdots, S_{n}$, where $k \geqslant 1$, then $x$ is counted 0 times on the left side of (1), and in the first term, second term, $\cdots$, $(k+1)$-th term, $\cdots$, the last term on the right side, $x$ is counted $1, C_{k}^{1}$, $C_{k}^{2}, \cdots, C_{k}^{k}, 0, 0, \cdots, 0$ times, respectively. Therefore, the total number of times $x$ is counted on the right side of (1) is
$$1 - C_{n}^{1} + C_{n}^{2} - \cdots + (-1)^{k} C_{k}^{k} + 0 + \cdots + 0 = (1-1)^{k} = 0.$$

In summary, we know that for any $x \in S$, the number of times $x$ is counted on both sides of (1) (i.e., the contribution of $x$ to both sides of the equation) is the same. Therefore, (1) holds.

For any subset $S_{1}, S_{2}, \cdots, S_{n}$ of $S$, since
$$\overline{S_{1} \cup S_{2} \cup \cdots \cup S_{n}} = \bar{S}_{1} \cap \bar{S}_{2} \cap \cdots \cap \bar{S}_{n},$$

we have $|S_{1} \cup S_{2} \cup \cdots \cup S_{n}| + | \bar{S}_{1} \cap \bar{S}_{2} \cap \cdots \cap \bar{S}_{n}| = |S|$. Thus, Theorem 2 can be derived from Theorem 1.