EMAT 6690

ESSAY 3 Site

Making Change

The Basic Problem:

This is a fairly typical problem presented to students in middle school and high school. The problem consists being able to make change, given a limited number of coins.

A typical presentation would be:

Given that you need to be able to make change for any amount from $0.01 through $0.99, and,

You must have at least one coin of each denomination (penny, nickel, dime and quarter),

What is least number of coins can this be done?

How many of each coin denomination will be needed?

Adaptations will allow for the number of coins to be stated (10 or 11 is typical) rather than leave it open to the least number.

Strategies:

The problem lies in that we appear to have too many unknowns and not enough equations to solve for them.

For the student, we would either have to rely on their logic, or we can show them spreadsheet methods that can help.

Both methods need to have some of the basic understanding.

We know:

We have some other relationships...i.e.
 
Logical Approach, without the Spreadsheet
 
Since we need to minimize the number of coins, first one would look into using the greatest number of the largest coin, possible. If we can eliminate the largest coin from the mix, then our solution will get easier. In that case:
Since Q = 25P, then
Now we have:
 
Since we need to be able to make change for values between $0.01 and $0.04 and a nickel's value is at least $0.05, we can make some assumptions about the penny.
This leaves us with:
We now can solve for b and c (substitute $0.10 for D and $0.05 for N);
    c = 3 - b
0.10b + (3-b)0.05 = 0.20
0.10b + 0.15 - 0.05b = 0.20
    0.05b = 0.05
    b = 1; therefore c = 2.
     
Note 1: Another solution also exists. If we have 2 dimes and 1 nickel, we can obtain the same results. (b = 2, c = 1). For any combination, we do not have to use all the coins. We will still have that nickel left for us to use. (e.g. for values between $0.05 and $0.09)

Note 2: This solution works for $0.99. It remains to be shown that this will also work for all other amounts of change between $0.01 and $0.98.

Spreadsheet Approach

The spreadsheet allows us to quickly repeat tables and search functions throughout a table to sift through all combinations of a problem and point out a solution. In the case above, create a spreadsheet of the number of coins necessary to get to $0.25 and then can repeat the sequence over again 3 times to get the least number of coins for each value of change.

We would start with a spreadsheet with the value of the change in the first column (A), the numbers of pennies in the next column(B), number of nickels in column C, the number of dimes in column D and the number of quarters in column E.

The value we enter in A is a calculation:

=0.01<B1> + 0.05 <C1> + 0.10<D1> + 0.25<E1

Initially we would clear out all of the values in columns B, C, D and E and add values as we increas total change we're counting.

Column B would be populated with 1, 2, 3, 4, 0, in sequence until we reached 20 cycles of this. This is the penny column and we need to increment between the other coins.

Column C would be 0 to start, go to 1 at $0.05; go back to 0 at $0.10, back to 1 at $0.15, back to 0 at $0.20 and stay 0 through $0.25.

Note: This will give us a different result than was presented in the first approach. This will result in 2 dimes and 1 nickel being used. In the other approach, we ended up with 1 dime and 2 nickels.

Column D would be 0 to start, go to 1 at $0.10; increment to 2 at $0.20 and go back to 0 at $0.25.

After the first 25 cycles, columns B, C and D repeat the same cycles for 26 through 50, 51 through 75 and 76 through 100.

Column E, would be 0 for cycles 0-24; increment to 1 at cycle 25; stay at 1 through cycle 49; increment to 2 at cycle 50; stay at 2 through 74; increment to 3 at cycle 75 and stay at 3 through cycle 99.

Change Pennies Nickels Dimes Quarters Count
0.01 1 0 0 0 1
0.02 2 0 0 0 2
0.03 3 0 0 0 3
0.04 4 0 0 0 4
0.05 0 1 0 0 1
0.06 1 1 0 0 2
0.07 2 1 0 0 3
0.08 3 1 0 0 4
0.09 4 1 0 0 5
0.1 0 0 1 0 1
0.11 1 0 1 0 2
0.12 2 0 1 0 3
0.13 3 0 1 0 4
0.14 4 0 1 0 5
0.15 0 1 1 0 2
0.16 1 1 1 0 3
0.17 2 1 1 0 4
0.18 3 1 1 0 5
0.19 4 1 1 0 6
0.2 0 0 2 0 2
0.21 1 0 2 0 3
0.22 2 0 2 0 4
0.23 3 0 2 0 5
0.24 4 0 2 0 6
0.25 0 0 0 1 1
0.26 1 0 0 1 2
0.27 2 0 0 1 3
0.28 3 0 0 1 4
0.29 4 0 0 1 5
0.3 0 1 0 1 2
0.31 1 1 0 1 3
0.32 2 1 0 1 4
0.33 3 1 0 1 5
0.34 4 1 0 1 6
0.35 0 0 1 1 2
0.36 1 0 1 1 3
0.37 2 0 1 1 4
0.38 3 0 1 1 5
0.39 4 0 1 1 6
0.4 0 1 1 1 3
0.41 1 1 1 1 4
0.42 2 1 1 1 5
0.43 3 1 1 1 6
0.44 4 1 1 1 7
0.45 0 0 2 1 3
0.46 1 0 2 1 4
0.47 2 0 2 1 5
0.48 3 0 2 1 6
0.49 4 0 2 1 7
0.5 0 0 0 2 2
0.51 1 0 0 2 3
0.52 2 0 0 2 4
0.53 3 0 0 2 5
0.54 4 0 0 2 6
0.55 0 1 0 2 3
0.56 1 1 0 2 4
0.57 2 1 0 2 5
0.58 3 1 0 2 6
0.59 4 1 0 2 7
0.6 0 0 1 2 3
0.61 1 0 1 2 4
0.62 2 0 1 2 5
0.63 3 0 1 2 6
0.64 4 0 1 2 7
0.65 0 1 1 2 4
0.66 1 1 1 2 5
0.67 2 1 1 2 6
0.68 3 1 1 2 7
0.69 4 1 1 2 8
0.7 0 0 2 2 4
0.71 1 0 2 2 5
0.72 2 0 2 2 6
0.73 3 0 2 2 7
0.74 4 0 2 2 8
0.75 0 0 0 3 3
0.76 1 0 0 3 4
0.77 2 0 0 3 5
0.78 3 0 0 3 6
0.79 4 0 0 3 7
0.8 0 1 0 3 4
0.81 1 1 0 3 5
0.82 2 1 0 3 6
0.83 3 1 0 3 7
0.84 4 1 0 3 8
0.85 0 0 1 3 4
0.86 1 0 1 3 5
0.87 2 0 1 3 6
0.88 3 0 1 3 7
0.89 4 0 1 3 8
0.9 0 1 1 3 5
0.91 1 1 1 3 6
0.92 2 1 1 3 7
0.93 3 1 1 3 8
0.94 4 1 1 3 9
0.95 0 0 2 3 5
0.96 1 0 2 3 6
0.97 2 0 2 3 7
0.98 3 0 2 3 8
0.99 4 0 2 3 9

Once the columns are all filled, and we've checked the value of $'s in column A, we can check for the minimum number of coins needed....

At the end of each of the columns B through E, we will use the maximum function to determine the maximum number of coins we needed to use to get all the change values. The function entered will look like:

=MAX(B2:B100)

Where B2:B100 is the range of cells where the number of pennies are entered. Once the entry is made for column B, it can be copied to columns C, D and E.

Change Pennies Nickels Dimes Quarters Count
0.91 1 1 1 3 6
0.92 2 1 1 3 7
0.93 3 1 1 3 8
0.94 4 1 1 3 9
0.95 0 0 2 3 5
0.96 1 0 2 3 6
0.97 2 0 2 3 7
0.98 3 0 2 3 8
0.99 4 0 2 3 9
Maximum 4 1 2 3 10

As can be seen, we can then sum up the total of the max's for each coin to determine the total number of coins needed.

 

Summary/Conclusion

From a mathematical approach, the spreadsheet method is pretty brute force. The best part about it, is that it is easily seen how to make change for each of the desired values. This could be setup with a class to flow through the process and have the students determine what the least amount of change would be for the first 25-30 entries, as a check. After 25 have been entered, then it is easy to clone the entries for the remainder of the chart.

A simpler method could be used, by throwing out the quarters to start with and going with making change up to $0.24. The same methods can be used, but the spreadsheet is much smaller. You can even experiment with alternative change values to see what the difference makes on the number of coins required.

Change Quarters Dimes Nickels Pennies Count
0.01 0 0 0 1 1
0.02 0 0 0 2 2
0.03 0 0 0 3 3
0.04 0 0 0 4 4
0.05 0 0 1 0 1
0.06 0 0 1 1 2
0.07 0 0 1 2 3
0.08 0 0 1 3 4
0.09 0 0 1 4 5
0.1 0 0 2 0 2
0.11 0 0 2 1 3
0.12 0 0 2 2 4
0.13 0 0 2 3 5
0.14 0 0 2 4 6
0.15 0 1 1 0 2
0.16 0 1 1 1 3
0.17 0 1 1 2 4
0.18 0 1 1 3 5
0.19 0 1 1 4 6
0.2 0 1 2 0 3
0.21 0 1 2 1 4
0.22 0 1 2 2 5
0.23 0 1 2 3 6
0.24 0 1 2 4 7
Maximum 0 1 2 4 7

 

Return to Carl's EMAT 6690 Page