Change For A Dollar

Let $p,$ $n,$ and $d$ be the number of pennies, nickels, and dimes, respectively, used when making change. We want to determine the number of non-negative integer solutions to $p + 5n + 10d = 100.$ The first thing we note is that the change from the pennies, $p = 100 - 5n- 10d = 5(20 - n- 2d),$ is divisible by 5. Thus, we write $p = 5P$ where $P$ is a non-negative integer.

Our equation then becomes $5P+5n + 10d = 100 \quad \Rightarrow \quad P+n+2d = 20.$ It is straightforward to see that the number of dimes, $d,$ can range from 0 to 10. Then, $P+n= 20-2d,$ so $P$ can be any of the $(21-2d)$ values $0,1,\ldots,20-2d$ at which point $n$ is uniquely determined as $20-2d-P.$

Thus, the total number of ways to make change is $\sum_{d=0}^{10}\left(21-2d\right) = 121.$

Let d be the number of dimes, and n the number of nickles. For any choice of d and n such that $0 \le 10d+5n \le 100$ , the dollar is completed by adding just enough pennies.

• For d=0, we can choose n anywhere from 0 through 20 (21 ways)
• For d=1, we can choose n anywhere from 0 through 18 (19 ways)
• ...
• For d=9, we can choose n=0, 1 or 2 ( 3 ways)
• For d=10, the only option is to have n=0 (1 way)

The total number of ways then is $21+19+...+3+1=\frac{22×11}{2}=\boxed{121}$ ways.