Combinations and currency

Question

How many possible combinations are there to make $3? This includes pennies, nickels, dimes, quarters, half-dollars, silver dollars, $1 and $2 bills. I have tried to figure this out using combinations and the fundamental counting principle, but no luck. I know this is a counting problem, I just do not know how to solve this.

Answer 1

15634

The easiest way is with a computer program

We could consider all the possible amounts of each currency, loop through them, and see which adds up to 300. Note that we can eliminate the penny calculation, though, and check that our total from the others is less than 300.

nickels(n): 0 to 60 = 61

dimes(d): 0 to 30 = 31

quarters(q): 0 to 12 = 13

half-dollars(h): 0 to 6 = 7

dollar bills(b): 0 to 3 = 4

silver dollars(s): 0 to 3 = 4

2 dollar bills(t): 0 to 1 = 2

This would be a total of 61*31*13*7*4*4*2 = 5506592 calculations.

This program is simple to write.

counter <- 0

for (t in 0:1){

for(b in 0:3){

for(s in 0:3){

for(h in 0:6){

for(q in 0:12){

for(d in 0:30){

for(n in 0:60){

if(200*t + 100 * b + 100 * s + 50 * h + 25 * q + 10 * d + 5 * n <= 300)

{counter <- counter + 1}}}}}}}}

Alternatively, you could tweak the program, going from largest currencies down, restricting to values summing to less than or equal to 300, and noticing that once we reach the nickel loop, all the nickel values are possible and imply a particular value for the pennies

counter <- 0

for (t in 0:1){

bmax <- (300 - 200 * t)/100

for(b in 0:bmax){

smax <- floor((300 - 200 * t - 100 * b)/100)

for(s in 0:smax){

hmax <- floor((300 - 200 * t - 100 * (b+s))/50)

for(h in 0:hmax){

qmax <- floor((300 - 200 * t - 100 * (b+s) - 50 * h)/25)

for(q in 0:qmax){

dmax <- floor((300 - 200 * t - 100 * (b+s) - 50 * h - 25 * q)/10)

for(d in 0:dmax){

nmax <- floor((300 - 200 * t - 100 * (b+s) - 50 * h - 25 * q - 10 * d)/5)

counter <- counter + nmax + 1}}}}}}

At $3, the first method is fast. If we increased to $30, you would want to use the second method.