Singapore has dollar notes in denominations of $1$ , $2$ and $5$ . How many ways are there to form exactly $\$100$ using just multiples of these notes?

**
Details and assumptions
**

The question does NOT state that you must use every denomination. Using 20 $5 notes (and 0 $1 and 0 $2 notes) to form exactly $100 is a valid way.

The answer is 541.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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.

11 Helpful
0 Interesting
0 Brilliant
0 Confused

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}$

11 Helpful
0 Interesting
0 Brilliant
0 Confused

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$

10 Helpful
0 Interesting
0 Brilliant
0 Confused

10 Helpful
0 Interesting
0 Brilliant
0 Confused

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$ .

10 Helpful
0 Interesting
0 Brilliant
0 Confused

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

10 Helpful
0 Interesting
0 Brilliant
0 Confused

5 Helpful
0 Interesting
0 Brilliant
0 Confused

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$ .

2 Helpful
0 Interesting
0 Brilliant
0 Confused

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$ .

2 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

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$ .