1. let $S$ be the set of all $n$-tuples $\left(X_{1}, \ldots, X_{n}\right)$, where $X_{1}, \ldots, X_{n}$ are subsets of $\{1,2, \ldots, 1000\}$, which do not all have to be different, and which can also be empty. For $a=\left(X_{1}, \ldots, X_{n}\right) \in S$ denote

$$
E(a)=\text { number of elements of } X_{1} \cup \ldots \cup X_{n}
$$

Find an explicit expression for the sum

$$
\sum_{a \in S} E(a)
$$
## 1st solution

We count the number of pairs $(a, x)$ in two ways, where $a=\left(X_{1}, \ldots, X_{n}\right) \in S$ is an $n$-tuple and $x \in X_{1} \cup \ldots \cup X_{n}$.

(a) For a fixed $a \in S$ there are by definition exactly $E(a)$ such elements $x$. Therefore, the number we are looking for is even

$$
\sum_{a \in S} E(a)
$$

(b) There are 1000 possibilities to select an element $x \in\{1,2, \ldots, 1000\}$. How many $n$-tuples $\left(X_{1}, \ldots, X_{n}\right)$ are there with $x \in X_{1} \cup \ldots \cup X_{n}$ ? Each of the subsets $X_{k}$ may or may not contain $x$, but $x$ must lie in at least one of these subsets. For every other element $y \in\{1,2, \ldots, 1000\}$ and every $k$ you can freely decide whether $y$ is in $X_{k}$ or not. In total, there are $\left(2^{n}-1\right) \cdot\left(2^{n}\right)^{999}$ different such $n$-tuples. The number you are looking for is therefore

$$
1000\left(2^{n}-1\right) 2^{999 n}
$$