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. 

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/