Combinatorics Question - Combinations

Question

How many different integers can be obtained as a sum of two or more of the numbers $1,3,5,10,20,50,82$?

I set this problem up into different cases using the fact that we are choosing 2 up to 7 of the numbers to create a sum and using the combinations formula.

${7}\choose{2}$+${7}\choose{3}$+${7}\choose{4}$+${7}\choose{5}$+${7}\choose{6}$+${7}\choose{7}$ = $120$

Answer 1

The number of subsets of $S:=\{1,3,5,10,20,50,82\}$ is $2^7=128$. The number of such subsets with at least two elements is $128-1-7=120$. Now, as JMoravitz remarked, we only have to worry about $82$.

First, note that, if $X$ and $Y$ are subsets of $S$ containing $82$, then $\sum X$ and $\sum Y$ are distinct as $X\setminus\{82\}$ and $Y\setminus\{82\}$ are both contained in $S\setminus\{82\}$. Thus, we have to count the number of pairs $(X,Y)$ of subsets of $S$ such that $82\in X$, $82\notin Y$, and $\sum X=\sum Y$. It is easily seen that $\{10,20,50\}\subseteq Y$. Thus, we only have to consider whether $1$, $3$, or $5$ are in $Y$, giving at most $2^3=8$ possibilities. Here is the complete list of all possible pairs $(X,Y)$:

1. $X=\{1,82\}$ and $Y=\{3,10,20,50\}$;
2. $X=\{3,82\}$ and $Y=\{5,10,20,50\}$;
3. $X=\{1,3,82\}$ and $Y=\{1,5,10,20,50\}$;
4. $X=\{1,5,82\}$ and $Y=\{3,5,10,20,50\}$.

Thus, we conclude that there are in total $120-4=116$ possible numbers which arise as a sum of at least two distinct elements of $S$.