<s>[INST] How many different positive integers can be obtained as a sum of some or all off the numbers: $1,3,5,10,25$? 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?
 [/INST] 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.
</s>