How many different positive integers can be obtained as a sum of some or all off the numbers: $1,3,5,10,25$?

Question

How many different positive integers can be obtained as a sum of some or all of the numbers: $1,3,5,10,25$?

I have just started discrete mathematics and I am having problems with some tasks. This is one of them. I don't really know what should be my starting approach. Could someone explain how to solve a problem like this one?

Answer 1

HINT: Notice that all possible sums are distinct so we can restate the problem as "how many non-empty subsets does $\{1,3,5,10,25\}$ have?" because for each element, we either include it to sum or not.

Answer 2

By the PigeonHole Principle, any set of numbers whose cardinality is greater than or equal to $10$, has two proper subsets with the same sum.

Obviously, no two numbers of this group have the same sum. So the total amount of numbers is the total number of combinations. Assuming that the numbers can be only sums, the number is

$^5\text C_2+^5\text C_3+^5\text C_4+^5\text C_5$.

This can also be expressed as $2^5-5$.

Answer 3

A sum is of the form $a*1 + b*3 + c*5 + d*10 + e*25$ where $a,b,c,d,e$ are either $0$ or $1$. There are $2$ choices for each $a,b,c,d,e$ so there are $2^5 = 32$ possible sums. But $0+0+0+0+0 = 0$ is not acceptable so there are only $2^5 - 1 = 31$ possible sums.

But we need to worry about if there are two different ways of writing sums that add to the same number.

$1 + 3 + 5 + 10 = 19 < 25$ so if the sum is more than or equal to $25$ then $e$ must be $1$ and if the sum is less then $25$ then $e$ must be $0$ so if two different sums add to the some thing then the $e$ value in each sum must be the same.

So if $a*1 + b*3 + 5*c + 10*d + 25*e = h*1 + i*3+k*5 + l*10 + m*25$ then $e=m$ and $a*1 + b*3 + c*5 + d*10 = h*1 + i*3 + k*5 +l*10 = N$.

We do the same argument again. $1 + 3 + 5 = 9 < 10$ so if $N \ge 10$ then $d=l=1$ and if $N < 10$ then $d=l=0$ and we have

$a*1 + b*3 + c*5 = h*1 +i*3 + k*5 = M$ and as $1 + 3 = 4 < 5$ we have $c = k$ and as $1 < 3$ we have $b = i$ and therefore $a=h$.

So any possible number can be reached only one way. So there are $31$ distinct sums.

....

It's worth thinking about writing them out and comparing them to the binary representations of $1$ to $31$. It should build intuition:

$1 = 1_2 \to 1$

$2 = 10_2 \to 3$

$3 = 11_2 \to 3+1 = 4$

$4 = 100_2 \to 5 = 5$

$5 = 101_2 \to 5 + 1 = 6$

....

$29 = 11101_2 \to 25 + 10 + 5 + 1 = 41$

$30 = 11110_2 \to 25 + 10 + 5 + 3 = 43$

$31 = 11111_2 \to 25 + 10 + 5 + 3 + 1 = 44$.

It's interesting that there are only $13$ numbers that aren't possible. We can't get $2$ so we can get any $25*a + 10*b + 5*c + 2$ so that rules out, $2,7,12,...,42$ and that accounts for $9$ of the numbers. The rest are that $20... 24$ are impossible.