Got Change for $10,000? A Mathematical Analysis

Overview

Objectives/Goals The objective is to determine how many ways there are to make change for a given amount of money using the following 5 coins: pennies, nickels, dimes, quarters, and half-dollars. Methods/Materials A Fortran program was written to determine the number of ways to make change for various amounts of money using the 5 U.S. coins by finding the maximum number of each coin needed, then testing all possible combinations and seeing if they matched the desired amount. This program ran very slowly. Patterns in the numbers of solutions were searched for and found, and a new program, based on the patterns, was written. It was verified that the results of the new (fast) program agreed with the old (slow) program. The reason why the algorithm works was found. Results The differences between the numbers of solutions in the 5 coin problem for amounts differing by $0.05 are the same as the number of solutions for the larger amount in the 4 coin problem. For example: In the 5 coin problems, there are 9 solutions for $0.20 and 13 solutions for $0.25, and there are 13-9=4 solutions for $0.25 in the 4 coin problem. The differences in the 4 coin problem are similarly related to the 3 coin problem solutions. A simple formula was found for computing the number of solutions for the 3 coin problem. Conclusions/Discussion An efficient algorithm was found that determined the number of solutions for the original 5 coin problem by relating it to the simpler 4 coin problem, and then to the even simpler 3 coin problem. For $5.00, the new program ran over 26,000 times faster than the original program and even faster for larger amounts. The number of solutions grows very quickly as the amount of money increases. For $1.00 there are 292 solutions, for $5.00 there are 59,576 solutions, and for $10,000 there are 666,794,085,020,860,416 solutions. This last number was computed in less than an hour using the new algorithm.

Competition history

• CSEF 2002 Mathematics & Software · Entry J1203

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2002 project