University of South Carolina High School Math Contest/1993 Exam/Problem 20

Problem

Let $A_1, A_2, \ldots , A_{63}$ be the 63 nonempty subsets of $\{ 1,2,3,4,5,6 \}$. For each of these sets $A_i$, let $\pi(A_i)$ denote the product of all the elements in $A_i$. Then what is the value of $\pi(A_1)+\pi(A_2)+\cdots+\pi(A_{63})$?

$\mathrm{(A) \ }5003 \qquad \mathrm{(B) \ }5012 \qquad \mathrm{(C) \ }5039 \qquad \mathrm{(D) \ }5057 \qquad \mathrm{(E) \ }5093$

Solution

We have $(1+1)(1+2)(1+3)(1+4)(1+5)(1+6)-1$ (The $-1$ since we have one less set). This is $7!-1=5039$. If you don't understand what the above means, just think about the simplifying of the brackets. Open the brackets and you should notice why it is correct. If you are also wondering whether or not if we got all the sets in the above multiplication, just think about the choices we have at each bracket. We have $2$ choices for which number we want to multiply and there are 6, which gives us $64$ total ways. This makes sense with the construction of the problem. If you are also confused about why we subtracted 1, just think about it this way: we explained that there are 64 ways, but we only have 63, so we subtract 1 because the number 1 is added twice in the simplification of the brackets.