Attribution: This is a cached copy of a third party project. Many of these sites are from 20 years ago and the majority are no longer running. We show only the first page of the project. We do not save all pages since copyright belongs to the third-party author.
Project Title: Got Change for $10,000? A Mathematical Analysis 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. Summary Statement The five coin problem (e.g., how many different ways can you make change for $5.00 using only the five U.S. coins) was investigated and a highly efficient algorithm was discovered. Help Received Father helped with Fortran programming and suggested looking for patterns in the data. Mother helped with the display board.