Ways to Make Change for $1.00Date: 10/02/97 at 06:19:13 From: Nancy O'Donnell Subject: Change for $1.00 A 4th grade class at our school recently read the book _Aliens for Breakfast_. The Alien in the story stated that there are 292 ways to make change for $1.00. The students want to know if this is true. They think that you would begin solving this problem by using 100 pennies and then substituting with larger coins, but they quickly become very confused. Thanks for your help. Nancy O'Donnell Library Media Specialist Theodore Roosevelt School Kenmore, N.Y. Date: 10/02/97 at 19:33:27 From: Doctor Tom Subject: Re: Change for $1.00 Hi Nancy, As your students have noticed, it's tough to keep track of what's going on. The answer for $1.00 is, in fact, 292 ways. To solve the problem in a reasonable way involves the use of generating functions, a topic from fairly advanced calculus. In case you're interested, here's a great reference: _Concrete Mathematics - A foundation for computer science_ by Graham, Knuth, and Patashnik, chapter 7, section 1. I wrote some recursive "C" code to calculate the numbers of ways of making change for all amounts less than or equal to $1.00 given that you can use anything up to half-dollars. I'll append the code and the output to the end of this note. It might be fun for your students to check some of the smaller numbers by hand. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ int p(int n) { return 1; } int n(int x) { if (x >= 0) return n(x-5) + p(x); return 0; } int d(int x) { if (x >= 0) return d(x-10) + n(x); return 0; } int q(int x) { if (x >= 0) return q(x-25) + d(x); return 0; } int c(int x) { if (x >= 0) return c(x-50) + q(x); return 0; } main() { int i; for (i = 1; i < 101; i++) printf("%d: %d\n", i, c(i)); } Output: 1: 1 2: 1 3: 1 4: 1 5: 2 6: 2 7: 2 8: 2 9: 2 10: 4 11: 4 12: 4 13: 4 14: 4 15: 6 16: 6 17: 6 18: 6 19: 6 20: 9 21: 9 22: 9 23: 9 24: 9 25: 13 26: 13 27: 13 28: 13 29: 13 30: 18 31: 18 32: 18 33: 18 34: 18 35: 24 36: 24 37: 24 38: 24 39: 24 40: 31 41: 31 42: 31 43: 31 44: 31 45: 39 46: 39 47: 39 48: 39 49: 39 50: 50 51: 50 52: 50 53: 50 54: 50 55: 62 56: 62 57: 62 58: 62 59: 62 60: 77 61: 77 62: 77 63: 77 64: 77 65: 93 66: 93 67: 93 68: 93 69: 93 70: 112 71: 112 72: 112 73: 112 74: 112 75: 134 76: 134 77: 134 78: 134 79: 134 80: 159 81: 159 82: 159 83: 159 84: 159 85: 187 86: 187 87: 187 88: 187 89: 187 90: 218 91: 218 92: 218 93: 218 94: 218 95: 252 96: 252 97: 252 98: 252 99: 252 100: 292 -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/