Subject (4). For each non-empty subset $A=\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$ of the set $\{1,2, \ldots, 10\}, k=1,2, \ldots, 10$, consider the sum

$$
S(A)=a_{1}-a_{1} a_{2}+a_{1} a_{2} a_{3}-\cdots-(-1)^{k} a_{1} a_{2} \cdots a_{k}
$$

where $a_{1}<a_{2}<\cdots<a_{k}$. Determine the sum of all these sums.
Solution. Let the universal set be $[n]=\{1,2, \ldots, n\}$. By manually performing the calculations for $n \in\{1,2,3,4\}$, we establish the conjecture $\sum_{\emptyset \neq A \subseteq[n]} S(A)=2^{n-1}$ (here we see the advantage of "generalizing" the statement - which allows us to simultaneously obtain "particularizations" from which we can empirically derive a working hypothesis). Assuming the formula is true for $n$, we consider the case $n+1$. If $n+1 \in A$, we denote $A^{\prime}=A \backslash\{n+1\}$, so $\emptyset \subseteq A^{\prime} \subseteq[n]$. For the unification of notations, we define $S(\emptyset)=0$ (which does not affect the formulas), and also $\prod_{a \in \emptyset} a=1$. Then we have

$S(A)=S\left(A^{\prime} \cup\{n+1\}\right)=S\left(A^{\prime}\right)-(-1)^{|A|} \prod_{a \in A} a=S\left(A^{\prime}\right)+(n+1)(-1)^{\left|A^{\prime}\right|} \prod_{a \in A^{\prime}} a$, so

$$
\sum_{n+1 \in A \subseteq[n+1]} S(A)=\sum_{\emptyset \subseteq A^{\prime} \subseteq[n]} S\left(A^{\prime}\right)+(n+1) \sum_{\emptyset \subseteq A^{\prime} \subseteq[n]}(-1)^{\left|A^{\prime}\right|}\left(\prod_{a \in A^{\prime}} a\right)
$$

But $\sum_{\emptyset \subseteq A^{\prime} \subseteq[n]} S\left(A^{\prime}\right)=2^{n-1}$, according to the induction hypothesis, and we will also show that $\sum_{\emptyset \subseteq A^{\prime} \subseteq[n]}(-1)^{\left|A^{\prime}\right|}\left(\prod_{a \in A^{\prime}} a\right)=0$. We write

$$
P(x)=\sum_{\emptyset \subseteq A^{\prime} \subseteq[n]}(-1)^{\left|A^{\prime}\right|}\left(\prod_{a \in A^{\prime}} a\right) x^{n-\left|A^{\prime}\right|}=\sum_{k=0}^{n}(-1)^{k}\left(\sum_{\left|A^{\prime}\right|=k} \prod_{a \in A^{\prime}} a\right) x^{n-k}
$$

and it is seen that $P(x)=\prod_{k=1}^{n}(x-k)$, so $\sum_{\emptyset \subseteq A^{\prime} \subseteq[n]}(-1)^{\left|A^{\prime}\right|}\left(\prod_{a \in A^{\prime}} a\right)=P(1)=0$, as promised. Finally, we have

$$
\sum_{\emptyset \neq A \subseteq[n+1]} S(A)=\sum_{\emptyset \subseteq A \subseteq[n]} S(A)+\sum_{n+1 \in A \subseteq[n+1]} S(A)=2^{n-1}+2^{n-1}=2^{n}
$$

It follows that for $n=10$, the desired value is $2^{10-1}=512$.