document.write( "Question 396775: Using only quarters, nickels, dimes and pennies--how many ways can I make 0.99? (99 cents) \n" ); document.write( "
Algebra.Com's Answer #284440 by richard1234(7193)\"\" \"About 
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.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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:\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Case 0: We wish to make 0 cents --> 1 way (just use no coins)
\n" ); document.write( "Case 1: We wish to make 1 cent --> 1 way 2*0 + 1*1
\n" ); document.write( "Case 2: We wish to make 2 cents --> 2 ways 2*1 + 1*0; 2*0 + 1*2
\n" ); document.write( "Case 3: We wish to make 3 cents --> 2 ways 2*1 + 1*1; 2*0 + 1*3
\n" ); document.write( "Case 4: We wish to make 4 cents --> 3 ways 2*2 + 1*0; 2*1 + 1*2, 2*0 + 1*4
\n" ); document.write( "Case 5: We wish to make 5 cents --> 3 ways 2*2 + 1*1, 2*1 + 1*3, 2*0 + 1*5\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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 \"floor%28k%2F2%29+%2B+1\" where \"floor%28z%29\" represents the floor value of z. Summing up from k = 0 to k = 19,\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "\"sum%28%28floor%28k%2F2%29%2B1%29%2C+k+=+0%2C+19%29+=+1+%2B+1+%2B+2+%2B+2+%2B+3+%2B+3\"+... +\"9+%2B+9+%2B+10+%2B+10\" = 110.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Now, suppose \"5+%3C=+k+%3C=+19\" 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\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "\"sum%28%28floor%28k%2F2%29%2B1%29%2C+k+=+0%2C+14%29+=+1+%2B+1+%2B+2+%2B+2\" + ... + \"7+%2B+7+%2B+8\" = 64\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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}.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "\"sum%28%28floor%28k%2F2%29%2B1%29%2C+k+=+0%2C+9%29+=+1+%2B+1+%2B+2+%2B+2\" + ... + \"4+%2B+4+%2B+5+%2B+5\" = 30\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "\"sum%28%28floor%28k%2F2%29%2B1%29%2C+k+=+0%2C+4%29+=+1+%2B+1+%2B+2+%2B+2+%2B+3\" = 9\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "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\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );