document.write( "Question 152564: how many ways to make change for one dollar using nickels, dimes and quarters \n" ); document.write( "
Algebra.Com's Answer #299461 by richard1234(7193)\"\" \"About 
You can put this solution on YOUR website!
You can compute the number of ways to make change for $1 using a bijection. We let n, d, q be the number of nickels, dimes, and quarters, and \"5n+%2B+10d+%2B+25q+=+100\", which implies \"n+%2B+2d+%2B+5q+=+20\". Hence, this is equivalent to finding the number of ways to make 20 \"cents\" using one-, two-, and five-cent pieces.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Suppose we want to find the number of ways to make 20 cents *without* using a five 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( "We can prove using either induction or modular arithmetic that the number of ways to make n cents in this way is \"floor%28n%2F2%29+%2B+1\", where \"floor%28x%29\" denotes the floor value of x. We can evaluate this at n = 20 to get \"floor%2820%2F2%29+%2B+1\", or 11.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Similarly, we can count the number of ways to obtain 20 cents using one five-cent piece. However, we can subtract off the five-cent piece and say that this is analogous to computing the number of ways to obtain 15 cents. Hence, this is equal to \"floor%2815%2F2%29+%2B+1+=+8\".\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "For 10, 5, and 0 cents, we have \"floor%2810%2F2%29+%2B+1+=+6\", \"floor%285%2F2%29+%2B+1+=+3\" and \"floor%280%2F2%29+%2B+1+=+1\". Therefore the total number of ways is 11 + 8 + 6 + 3 + 1 = 29 ways.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Note: the other tutor counted 293 ways, however this included pennies and half dollars, which was not stated in the question. To count the number of ways using pennies, nickels, dimes, and quarters, you can also use a bijection, but instead of counting the number of ways to obtain 20 cents, you evaluate at 20, 19, 18, ..., 0 since this will uniquely determine the number of pennies. We do the same with 15, 10, 5, and 0 to obtain sums:\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Then, if you want half dollars involved, it is equal to \"242+%2B+k%5B1%5D+%2B+k%5B2%5D\" where \"k%5Bi%5D\" is the number of ways to make a dollar using i half dollars, equivalently, the number of ways to make 50 cents and 0 cents without half dollars (here you should get 293!). \n" ); document.write( "
\n" );