Associated Topics || Dr. Math Home || Search Dr. Math

### Ways to Make Change for \$1.00

```
Date: 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.

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/
```
Associated Topics:
Elementary Puzzles
High School Calculators, Computers
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search