In how many different ways can you change a dollar?   Tuesday, 19 August 2008 00:00

In how many different ways can you change a dollar?

That is, in how many different ways can you pay 100 cents using five different kinds of coin, cents, nickels, dimes, quarters and half-dollars (worth 1, 5, 10, 25 and 50 cents, respectively?) There are several ways to solve this problem. There are a mathematical solution using recurrences as well a direct approach using Computer Science. Of course, both solutions are equivalents.

At first, we will suppose how to change 20 cents, instead of 100 cents.

So, we have coins of 1¢, 5¢, and 10¢.

Now, we will define An the number of 1¢ coins. Therefore, to change 5¢, 10¢, 15¢ or 20¢ we will have always one way. So, An=1.

Now, we will define Bn the number of 1¢ coins and 5¢ coins. We will start with 5¢. So, to change 5¢ coins, we have B5=2.
To change 10¢ we will have 3, and in general we will have Bn=An + Bn-5.

Now, we will define B(n) the number of 1¢, 5¢ and 10¢ coins. Here the formula is Cn = Bn + Cn-10

In other words, we create the following table:

 A B C 0 1 1 1 5 1 2 2 10 1 3 4 15 1 4 6 20 1 5 9

Therefore, there are 9 ways to change 20¢ using coins of 1¢, 5¢ and 10¢.

Now, we will extend the problem to 100¢ using coins of 1¢, 5¢, 10¢, 25¢ and 50¢.

So, we introduce Dn that is the number of 1¢, 5¢, 10¢ and 25¢coins and En the number of 1¢, 5¢, 10¢, 25¢ and 50¢ coins.

 A B C D E 0 1 1 1 1 1 5 1 2 2 2 2 10 1 3 4 4 4 15 1 4 6 6 6 20 1 5 9 9 9 25 1 6 12 13 13 30 1 7 16 18 18 35 1 8 20 24 24 40 1 9 25 31 31 45 1 10 30 39 39 50 1 11 36 49 50 55 1 12 42 60 62 60 1 13 49 73 77 65 1 14 56 87 93 70 1 15 64 103 112 75 1 16 72 121 134 80 1 17 81 141 159 85 1 18 90 163 187 90 1 19 100 187 218 95 1 20 110 213 252 100 1 21 121 242 292

Here are valid the relative formulae: Dn = Cn + Dn-25 and En = Dn + En-50

So, there are 292 ways to change 1 dollar or 100¢ using 1¢, 5¢, 10¢, 25¢ and 50¢ coins.

Last Updated on Tuesday, 19 August 2008 14:40