100 Singapore Dollars

Let $x,y,z$ be the number of $1,2,5$ dollar notes respectively. $x+2y+5z=100$ . $z$ should lie between $0$ and $20$ , inclusive. $x,y$ must be non-negative.

Notice that $x = 100 - 5z - 2y$ is uniquely determined for each valid pair $(y,z)$ satisfying $2y+5z \le 100$ , or equivalently $y \le 50-\frac{5z}{2}$ . If $z$ is even, let $z=2t$ , where $0 \le t \le 10$ . By substitution, $y \le 50-5t$ . so there are $(50-5t+1)$ possible $y$ 's. If $z$ is odd, let $z=2t+1$ , where $0 \le t \le 9$ . Substituting yields $y \le 47\frac12-5t$ . Hence, for every odd $z$ , there are $(47-5t+1)$ possible $y$ 's.

The total number of ways is:

$\displaystyle \sum_{t=0}^{10} (51-5t) + \sum_{t=0}^9 (48-5t) = (11+ \sum_{t=0}^{10} (50-5t))+(-20+ \sum_{t=0}^9 (50-5t))$ $=-9+2\displaystyle \sum_{t=0}^9 (50-5t)=-9+10\displaystyle \sum_{t=0}^9 (10-t)=541$ .

The problem is equivalent to finding how many ordered triples of non-negative integers $(x, y, z)$ satisfy $x+2y+5z=100$ . This can be further simplified to finding the number of ordered triples of non-negative integers $(x, y)$ such that $2x+5y\leq100$ , since the number of one dollar notes can make up for the remainder.

Now, we are trying to find the number of lattice points on the graph of $2x+5y\leq100$ with $x, y \geq 0$ , which is a right triangle with 2 legs on the x and y axes. Pick's theorem states that the area of a polygon is equal to the number of lattice points in the interior of the polygon plus half the number of lattice points on the perimeter of the polygon minus one: $A = i+\frac{e}{2}-1$ . Thus, it suffices to find the area of the triangle and the number of lattice points the triangle's perimeter passes through and then use Pick's theorem to find the number of interior lattice points and then the total number of lattice points.

On the hypotenuse of the right triangle, we have $2x=5(20-y)$ , so x must be a multiple of 5. We get 9 lattice points: $(5, 18), (10, 16), \cdots (45, 2)$ . On the vertical leg of the right triangle excluding the origin, we have $x = 0, 0<y \leq 20$ which yields 20 points. On the horizontal leg, we have $y = 0, 0<x \leq 50$ , yielding 50 points. Finally, $(0, 0)$ is our last point. The right triangle passes through a total of $1+9+20+50=80$ lattice points.

The area of our right triangle is $\frac{1}{2}\times 20\times 50=500$ , so by Pick's theorem, we have $i = 500-\frac{80}{2}+1 = 461$ lattice points in the interior of the triangle, and we have 80 lattice points on the perimeter of the triangle, so in total, we have $461+80=\boxed{541}$ lattice points, the number of ways we can make $100.

Let $x, y, z$ be the number of $\$5, \$2, \$1$ notes respectively. Then the problem is equivalent to the number of non-negative solutions to the equation $5x+2y+z = 100$ . Next note that for any values of $x$ and $y$ , there is only one solution for $z$ , therefore the number of solution is equivalent to the number of non-negative solutions for the inequality $5x+2y\leq 100$ .

Now consider the case where $x=2k, 0\leq k\leq 10$ . The number of solutions for $y$ is $\lfloor\frac{100-10k}{2}\rfloor+1=51-5k$ . Total number of solutions for this case is $\sum_{k=0}^{10} 51-5k = 286$

For the case $x=2k+1, 0\leq k\leq 9$ , the number of solutions for $y$ is $\lfloor\frac{100-10k-5}{2}\rfloor+1=48-5k$ .

Total number of solutions for this case is $\sum_{k=0}^9 48-5k = 255$ So total number of solutions is $286+255=\mbox{541}$

Let a,b,c denote the number of $1,$2,$5 notes that are used, respectively.

We must find the number of nonnegative integer triplets (a,b,c) such that $a+2b+5c = 100$

This is equivalent to find the number of nonnegative integer pairs (b,c) such that $2b+5c \leq 100$ since the rest ( $100-2b-5c \geq 0$ ) can be covered with the $1 notes.

Given $c$ , the possible $b$ values are from $0$ to $\lfloor \frac{100-5c}{2} \rfloor$ and it's easy to see that $c \leq 100/5 = 20$

Hence the number of possible pairs are $\sum_{c=0}^{20} 1+\lfloor \frac{100-5c}{2} \rfloor$

Either calculate manually for each $c$ , or divide the sum for odd/even $c$ and the terms can be expressed without floor

Odd $c$ : $1+\lfloor \frac{100-5c}{2} \rfloor = 50 - \frac{5c-1}{2}$

Even $c$ : $1+\lfloor \frac{100-5c}{2} \rfloor = 51 - \frac{5}{2} c$

and it becomes $(3+8+\cdots + 48) + (1+6+\cdots+51)$ $= \frac{(3+48)*10}{2} + \frac{(1+51)*11}{2} = 255+286 = 541$

We can have any number of $5 notes between 0 and 20. If we have n $5 notes, we must have $100-5n left to make out of $2 and $1 notes. We can then have any whole number of $2 notes (call the number of $2 notes m) between 0 and (100-5n)/2, because if the total is under $100, we can simply fill the remainder with $1 notes (for example, if we had 13 $5 notes, there would be $35 remaining, so we could have any one of 0, 1, 2, 3,...,17 $2 notes, and however many $1 notes necessary to total $100). For even values of n, we have n: 0, 2,...,20; the corresponding values for m are: 51, 46,..., 1 For odd n, we have n: 1, 3,...,19 m: 48, 43,...3 These possibilities for m form two arithmetic series, the sum of the first one is 286, the sum of the second one is 255. 255+286=541, which is the answer.

Let $x,y,z$ be the number of $1,2,5$ dollar notes respectively. $x+2y+5z=100$ . $z$ should lie between $0$ and $20$ , inclusive. $x,y$ must be non-negative.

Notice that $x = 100 - 5z - 2y$ is uniquely determined for each valid pair $(y,z)$ satisfying $2y+5z \le 100$ , or equivalently $y \le 50-\frac{5z}{2}$ . If $z$ is even, let $z=2t$ , where $0 \le t \le 10$ . By substitution, $y \le 50-5t$ . so there are $(50-5t+1)$ possible $y$ 's. If $z$ is odd, let $z=2t+1$ , where $0 \le t \le 9$ . Substituting yields $y \le 47\frac12-5t$ . Hence, for every odd $z$ , there are $(47-5t+1)$ possible $y$ 's.

The total number of ways is:

$\displaystyle \sum_{t=0}^{10} (51-5t) + \sum_{t=0}^9 (48-5t) = (11+ \sum_{t=0}^{10} (50-5t))+(-20+ \sum_{t=0}^9 (50-5t))$ $=-9+2\displaystyle \sum_{t=0}^9 (50-5t)=-9+10\displaystyle \sum_{t=0}^9 (10-t)=541$ .

Let the number of 1$,2$ and 5$ notes be x,y and z respectively. Let's assume there are no 5$ notes.So,the 100$ contains only combinations of 1$ and 2$ i.e x+2y=100. We have 51 solutions for this. Similarly, when we take only 2$ and 5$ into accoutn we have 2y+5z=100. We have 11 solutions and for x+5z=100 we have 21 solutions. But, we have included 3 solutions twice i.e when (100,0,0), (0,50,0) and (0,0,20). Therefore total solutions as of now is 80.

Now, let z =1.Hence, x+2y=95. We have to calculate solutions for this equation keeping in mind x and y cannot be zero,since we have included the results in the above 80 solutions.For different values of z ranging from 1 to 19( it cannot be 20 or 0 because the results for them have already been includedin the above 80 solutions) we have the following:

x+2y=95 gives us 47 solutions. x+2y=90 gives us 44 solutions x+2y=85 gives us 42 solutions x+2y=80 gives us 39 solutions x+2y=75 gives us 37 solutions x+2y=70 gives us 34 solutions : : : : : : x+2y= 5 gives us 2 solutions x+2y=10 gives us 4 solutions.

Both the series above are Arithmetic progressions with common difference of 5. The sum of 1st series is 245 and 2nd series is 216.

Therefore,the total number of solutions are 80+245+216=541

First we calculate the number of possible ways if we have only 1 and 2 dollars. Suppose we need to make $n$ dollars. Then the possible number of ways is $[\frac n2]+1$ where $[n]$ is the greatest integer lesser than or equal to $n$ .[This is pretty elementary because there are $[\frac n2]$ cases where different numbers of 2 dollars are used and one case where all are 1 dollars.] Now we have 21 cases. CASE1:0 five dollar. There are $[\frac{100}{2}]+1$ possible ways. CASE2:1 five dollar. There are $[\frac{95}{2}]+1$ possible ways. . . . CASE21:20 five dollars. There are $[\frac 02]+1$ possilbe ways. Adding them we get 541 possible ways.

Let $P\left(n,r\right)$ be the number of ways to write a positive integer $n$ in denominations of the $r$ th denomination and below. Trivially, $P\left(n,1\right)=1$ because there is only one unique way to write a number as a sum of 1s. A recursive definition of this function from the set of denominations $\sigma=\{5,2,1\}$ is

$P\left(n,r\right)= \begin{cases} 1, & \text{if }n=3 \\ \sum_{i=r}^3 \begin{cases} 1, & \text{if }n=\sigma_i \\ P\left(n-\sigma_i,i\right), & \text{if }n>\sigma_i \end{cases} , & \text{else} \end{cases}$

by the Greedy Algorithm. Applying this yields $P\left(100,1\right) = 540$ .

We seek the number of non-negative integer solutions to $a + 2b + 5c = 100$ . Thus $c\leq 20$ .

For a fixed $c$ , we seek the number of solutions to $a + 2b = 100-5c$ . We notice that $2b$ is always even, thus $a$ and $100-5c$ must have the same parity.

If $100-5c \$ is odd then $a = 1, 3, 5, \ldots 100-5c$ gives valid solutions for $a + 2b = 100 - 5c$ , thus there are $\frac{101-5c}{2}$ pairs of $(a,b,c)$ for $c = 1, 3, 5, \ldots, 17, 19$ . Hence the total number of solutions for this case are $\frac{101}{2}\times 10 - \frac{5}{2}\times 20\times 5 = 255$ .

If $100-5c \$ is even then $a = 0, 2, 4, 6, \ldots 100-5c$ gives valid solutions for $a + 2b = 100 - 5c$ , thus there are $\frac{100-5c}{2} + 1$ pairs of $(a,b,c)$ for $c = 0, 2, 4, 6, \ldots, 18, 20$ . Hence the total number of solutions for this case are $\frac{100}{2}\times 11 - \frac{5}{2}\times 22\times 5 + 11 = 286$ .

Therefore there are $255 + 286 = 541$ possible solutions.

Note: The possible solutions for $a+2b=100-5c$ for a fixed $c$ is equal to $\left \lfloor \frac{100-5c}{2} \right \rfloor + 1$ where $\lfloor x \rfloor$ denotes the greatest integer smaller than or equal to $x$ .

x+2y+5z=100 0≤x≤100⟹0≤100−2y−5z≤100⟹0≤2y+5z≤100 ⟹0≤y≤⌊100−5z2⌋ As 0≤5z≤100,0≤z≤20 If z is odd =2a+1,0≤y≤⌊100−5(2a+1)2⌋=47−5a,47−5a+1=48−5a values of z So, 0≤2a+1≤20⟹0≤a≤9 If z is even,=2b,0≤y≤⌊100−5(2b)2⌋=50−5b,50−5b+1=51−5b values of z So, 0≤2b≤20⟹0≤b≤10 So, the number of combinations =∑0≤a≤9(48−5a)+∑0≤b≤10(51−5b)=48⋅10+51⋅11−5∑0≤a≤9a−5∑0≤b≤10b=541

Let no of 1$ be 'x',2$ be 'y' and 3$ be 'z'. x+2y+5z=100 0≤x≤100=0≤100−2y−5z≤100=0≤2y+5z≤100 =0≤y≤⌊(100−5z)/2⌋ As 0≤5z≤100,0≤z≤20 If z is odd =2a+1,0≤y≤⌊(100−5(2a+1))/2⌋=47−5a,47−5a+1=48−5a values of z So, 0≤2a+1≤20=0≤a≤9 If z is even,=2b,0≤y≤⌊(100−5(2b))/2⌋=50−5b,50−5b+1=51−5b values of z So, 0≤2b≤20=0≤b≤10 So, the number of combinations =∑0≤a≤9(48−5a)+∑0≤b≤10(51−5b)=48⋅10+51⋅11−5∑0≤a≤9a−5∑0≤b≤10b=541

x+2y+5z=100 0≤x≤100.this implies 0≤100−2y−5z≤100.this implies 0≤2y+5z≤100 .this implies0≤y≤⌊(100−5z)/2⌋ As 0≤5z≤100,0≤z≤20 If z is odd =2a+1,0≤y≤⌊(100−5(2a+1))/2⌋=47−5a,47−5a+1=48−5a values of z So, 0≤2a+1≤20.this implies 0≤a≤9 If z is even,=2b,0≤y≤⌊(100−5(2b))/2⌋=50−5b,50−5b+1=51−5b values of z So, 0≤2b≤20.this implies 0≤b≤10 So, the number of combinations =∑0≤a≤9(48−5a)+∑0≤b≤10(51−5b)=48⋅10+51⋅11−5∑0≤a≤9a−5∑0≤b≤10b=541

x+2y+5z=100 0≤x≤100⟹0≤100−2y−5z≤100⟹0≤2y+5z≤100 ⟹0≤y≤⌊100−5z2⌋ As 0≤5z≤100,0≤z≤20 If z is odd =2a+1,0≤y≤⌊100−5(2a+1)2⌋=47−5a,47−5a+1=48−5a values of z So, 0≤2a+1≤20⟹0≤a≤9 If z is even,=2b,0≤y≤⌊100−5(2b)2⌋=50−5b,50−5b+1=51−5b values of z So, 0≤2b≤20⟹0≤b≤10 So, the number of combinations =∑0≤a≤9(48−5a)+∑0≤b≤10(51−5b)=48⋅10+51⋅11−5∑0≤a≤9a−5∑0≤b≤10b=541

x+2y+5z=100 0≤x≤100⟹0≤100−2y−5z≤100⟹0≤2y+5z≤100 ⟹0≤y≤⌊100−5z2⌋ As 0≤5z≤100,0≤z≤20 If z is odd =2a+1,0≤y≤⌊100−5(2a+1)2⌋=47−5a,47−5a+1=48−5a values of z So, 0≤2a+1≤20⟹0≤a≤9 If z is even,=2b,0≤y≤⌊100−5(2b)2⌋=50−5b,50−5b+1=51−5b values of z So, 0≤2b≤20⟹0≤b≤10 So, the number of combinations =∑0≤a≤9(48−5a)+∑0≤b≤10(51−5b)=48⋅10+51⋅11−5∑0≤a≤9a−5∑0≤b≤10b=541