Question 396775: Using only quarters, nickels, dimes and pennies--how many ways can I make 0.99? (99 cents)
Found 2 solutions by Edwin McCravy, richard1234:
Answer by Edwin McCravy(20054)   (Show Source):
Answer by richard1234(7193)  (Show Source):
You can put this solution on YOUR website! Note that this is equivalent to finding the number of ways to make 95, 90, 85, ..., 0 cents using quarters, nickels, and dimes since the pennies will be uniquely determined afterwards. Also, we can further reduce this to make 19, 18, 17, ..., 0 cents using 5 cent, 2 cent, and 1 cent pieces (for example, 3 quarters, 1 dime, 2 nickels making 95 cents is equivalent to 3 5-cent pieces, 1 2-cent piece, 2 1-cent pieces making 19 cents). In essence, we have established a bijective function that maps some set of numbers to a set that is a bit easier to count.
Therefore we want to find the number of ways to make 0 cents, 1 cent, ..., 19 cents (using 5-cent, 2-cent, 1-cent pieces), and add them up. Here, I will demonstrate the number of ways to make x cents *without* using a 5-cent piece:
Case 0: We wish to make 0 cents --> 1 way (just use no coins)
Case 1: We wish to make 1 cent --> 1 way 2*0 + 1*1
Case 2: We wish to make 2 cents --> 2 ways 2*1 + 1*0; 2*0 + 1*2
Case 3: We wish to make 3 cents --> 2 ways 2*1 + 1*1; 2*0 + 1*3
Case 4: We wish to make 4 cents --> 3 ways 2*2 + 1*0; 2*1 + 1*2, 2*0 + 1*4
Case 5: We wish to make 5 cents --> 3 ways 2*2 + 1*1, 2*1 + 1*3, 2*0 + 1*5
There is a pattern, which we can prove by a simple induction or modular arithmetic argument, that the number of ways to make k cents increments by 1 every 2 cents. We can generalize and say that the number of ways to make k cents without using a 5-cent piece is  where  represents the floor value of z. Summing up from k = 0 to k = 19,
 +... + = 110.
Now, suppose  and we wish to count the number of ways to make k cents using exactly one 5-cent piece. We can note that this is analogous to computing the ways of making 0 to 14 (subtracting 5 from all terms). In other words, we have
 + ... +  = 64
Repeat the same with the cases where two 5-cent pieces and three 5-cent pieces are used. Basically, only the bounds are changed to {0, 9}, {0, 4}.
 + ... +  = 30
 = 9
Adding all these values up, we get 110 + 64 + 30 + 9 = 213 ways. Since our function is bijective, we can say that the number of ways to make 99 cents is also equal to 213.
This solution required the use of a bijective function, which is normally not taught in a standard middle/high school curriculum. Here is a Wikipedia article in case you're interested: http://en.wikipedia.org/wiki/Bijection
|
|
|
