Big Mathematics Challenge on Set and Summation?

Question

please be aware that this is not homework. it's past PHD entrance Exam on 2011.

Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$

if we have: $$T=\sum_{(A_1,A_2,A_3)\in B} |A_1\cup A_2 \cup A_3| $$

What is the value of $T$?

a) $2^{59}-2^{56}$

b) $2^{60}-2^{57}$

c) $20(2^{59}-2^{56})$

d) $20(2^{60}-2^{57})$

Answer 1

First note that:

$$\sum_{(A_1,A_2,A_3)\in B} \left|A_1\cup A_2\cup A_3\right|$$

is the same as:

$$\sum_{i=1}^{20} \sum_{(A_1,A_2,A_3)\in B}_{i\in A_1\cup A_2\cup A_3} 1$$

(Why?)

The internal sum is independent of $i$, so this is:

$$20\sum_{(A_1,A_2,A_3)\in B}_{1\in A_1\cup A_2\cup A_3} 1$$

How many elements of $B$ have $1\in A_j$ for some $j$? There are $2^{60}$ elements of $B$, and the probability of picking an element of $B$ without $1$ is $1-\frac{1}{8}$. So the total is:

$$20\left(2^{60}-2^{57}\right)$$

So (d).