4th Grade Math Puzzler
Don Detweiler
which essentially turned into a challenge in tedium.
The question was simple enough: How many different ways are there to
make change for a dollar.
Presuming that we could use a silver dollar, half dollars, quarters,
dimes, nickels, and pennies, we counted 547 different ways to make change
for a dollar. Of course teachers workbook answer was off by a few
hundred.
Is there any mathematical formula that could be used to definitively
determine the correct answer?
Don
John McGowan
Newsgroups: sci.math
Subject: 4th Grade Math Puzzler
Date: 3 Dec 1995 00:41:48 GMT
> My fourth grade child recently came home with a "math challenge" problem,
> which essentially turned into a challenge in tedium.
>
> The question was simple enough: How many different ways are there to
> make change for a dollar.
>
> Presuming that we could use a silver dollar, half dollars, quarters,
> dimes, nickels, and pennies, we counted 547 different ways to make change
> for a dollar. Of course teachers workbook answer was off by a few
> hundred.
WOW! 547!? I get 293. Is that the answer given by the teacher's workbook?
> Is there any mathematical formula that could be used to definitively
> determine the correct answer?
Yes.
Consider the function G(x)=(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)
penny nickel dime quarter half dollar
and consider F(x)=1/G(x) which is:
(1+x+x^2+x^3...)(1+x^5+x^10+x^15...)(1+x^10+x^20...)(1+x^25+x^50...)*
(1+x^50+x^100+...)(1+x^100+x^200...)
and look at the coefficient of x^100 in F(x). It is obtained as the number
of ways one can choose a term from the first factor, second, etc. to get an
x^100 or the number of non-negative integral solutions to:
a + 5b + 10c + 25d + 50e + 100f = 100
and with a the number of pennies, b the number of nickels, etc. this is the
number you want.
Note that in F one can truncate the 1+x+x^2+x^3+x^4... term to
1+x+x^2+x^3+...+x^100 (and, say the 1+x^50+x^100+x^150+... to 1+x^50+x^100)
(that is stop each at x^100) since higher powers of x in these terms only
contribute to terms in x^n for n>100 (that is, the number of ways of making
change for numbers greater than 100 cents = 1 dollar). Thus, all one needs
is a package to multiply polynomials, or a short, say, QBasic routine to do
it.
The following routine in Qbasic is designed to produce the result.
penny() is the array of coefficients of 1/(1-x) for x up to 100 (pennies)
nickle() is " " " " " 1/(1-x^5) " " " " " (nickles)
quarter() is " " " " " 1/(1-x^25) " " " " " (quarters)
etc.
(the nickle() array is (1,0,0,0,0,1,0,0,0,0, 1,....)
0 1 2 3 4 5 6 7 8 9 10 <--exponent
(in 1/(1-x^5) the coefficient of x^0 is 1, of x^5 is 1, of x^10 is 1, etc.
while the coefficient of x^j is zero for j not divisible by 5)
pol starts as the coef. of the polynomial f(x)=1
(pol()=(1,0,0,0,0,0,0,0,0,...) for up to 100 terms (well, up to x^100,
which is 101 terms as the power goes from 1 to 100) and we calcluate:
pol <-- pol*penny
pol <-- pol*nickle
pol <-- pol*dime
pol <-- pol*quarter
pol <-- pol*half
pol <-- pol*dollar
to finally get pol=the polynomial corresponding to multiplying out the
penny, nickle, quarter, half (dollar) and dollar polynomials. The final
result for the terms in pol()=(1,1,1,1,1,2,2...) give the number of ways
0,1,2,3,4,5,6 <-- value
of representing a value in change (e.g. 0 can be represented only one
way... no change. One cent can be represented only by giving a penny's
worth of change so too up to five cents which can be represented as a
nickle or five pennies and then six cents which can be changed as six
pennies or a nickle and a penny, etc.
---------- RESULTS ----------
Amount Number Amount Number Amount Number Amount Number
of of of of of of of of
change ways change ways change ways change ways
0 1
1 1 26 13 51 50 76 134
2 1 27 13 52 50 77 134
3 1 28 13 53 50 78 134
4 1 29 13 54 50 79 134
5 2 30 18 55 62 80 159
6 2 31 18 56 62 81 159
7 2 32 18 57 62 82 159
8 2 33 18 58 62 83 159
9 2 34 18 59 62 84 159
10 4 (*) 35 24 60 77 85 187
11 4 36 24 61 77 86 187
12 4 37 24 62 77 87 187
13 4 38 24 63 77 88 187
14 4 39 24 64 77 89 187
15 6 40 31 65 93 90 218
16 6 41 31 66 93 91 218
17 6 42 31 67 93 92 218
18 6 43 31 68 93 93 218
19 6 44 31 69 93 94 218
20 9 45 39 70 112 95 252
21 9 46 39 71 112 96 252
22 9 47 39 72 112 97 252
23 9 48 39 73 112 98 252
24 9 49 39 74 112 99 252
25 13 50 50 75 134 100 293
(*) e.g. ten cents can be given in change as either:
ten pennies
a nickle and five pennies
two nickles or
a dime
4 ways
---------- QBASIC PROGRAMME ----------
REM 100 is hard coded into the programme for change up to 1 dollar.
REM How many ways can one make change for n cents for n=0 to 100.
REM This code is not the most efficient (e.g. in the for loops to set
REM up the dime array, one could have used "for i=0 to 100 step 10"
REM to set dime(i)=1 and could have used subroutines. This is written out
REM in all its gory detail to be as simple to understand as possible.
REM to multiply an array a() by b() to get c() one uses the fact that
REM c(i) = SUM(a(j)*b(i-j)) and below we use the temp array for the
REM result which is then moved into the pol array.
REM At the end, pol(n) is the number of ways of making change for n cents
REM for (and only for) n no larger than one dollar.
REM everything is an intger
DIM pol(100) AS INTEGER, temp(100) AS INTEGER
DIM penny(100) AS INTEGER, nickle(100) AS INTEGER, dime(100) AS INTEGER
DIM quarter(100) AS INTEGER, half(100) AS INTEGER, dollar(100) AS INTEGER
DEFINT I-J
REM set up f(x)=1, original
pol(0) = 1: FOR i = 1 TO 100: pol(i) = 0: NEXT i
REM pennies... all coefficients are 1
FOR i = 0 TO 100: penny(i) = 1: NEXT i
REM nickles... coefficients are 1 for exponents divisible by 5
FOR i = 0 TO 100
IF ((i MOD 5) = 0) THEN
nickle(i) = 1
ELSE
nickle(i) = 0
END IF
NEXT i
REM dimes... coefficients are 1 for exponents divisible by 10
FOR i = 0 TO 100
IF ((i MOD 10) = 0) THEN
dime(i) = 1
ELSE
dime(i) = 0
END IF
NEXT i
REM quarters... coefficients are 1 for exponents divisible by 25
FOR i = 0 TO 100
IF ((i MOD 25) = 0) THEN
quarter(i) = 1
ELSE
quarter(i) = 0
END IF
NEXT i
REM half dollars... coefficients are 1 for exponents divisible by 50
FOR i = 0 TO 100
IF ((i MOD 50) = 0) THEN
half(i) = 1
ELSE
half(i) = 0
END IF
NEXT i
REM whole dollars... coefficients are 1 for exponents divisible by 100
FOR i = 0 TO 100
IF ((i MOD 100) = 0) THEN
dollar(i) = 1
ELSE
dollar(i) = 0
END IF
NEXT i
REM pol <-- pol*penny
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * penny(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM pol <-- pol*nickle
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * nickle(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM pol <-- pol*dime
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * dime(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM pol <-- pol*quarter
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * quarter(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM pol <-- pol*half
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * half(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM pol <-- pol*dollar
FOR i = 0 TO 100: temp(i) = 0
FOR j = 0 TO i
temp(i) = temp(i) + pol(j) * dollar(i - j)
NEXT j
NEXT i
FOR i = 0 TO 100: pol(i) = temp(i): NEXT i
REM print results
FOR i = 0 TO 100
PRINT "For "; i; " cents one can make change "; pol(i); "ways"
NEXT i
---------- END ----------
--
John McGowan | jmcg...@inch.com [Internet Channel]
| jmcg...@mail.coin.missouri.edu [COIN]
--------------+-----------------------------------------------------
Kurt Foster
: The question was simple enough: How many different ways are there to
: ...we could use a silver dollar, half dollars, quarters,
: dimes, nickels, and pennies, ...
: Is there any mathematical formula that could be used to definitively
: determine the correct answer?
:
I don't know about "could use", but the number in question is the
coefficient of x^100 in
(1 + x + x^5 + x^10 + x^25 + x^50 + x^100)^100.
It is also th e number of distinct solutions in non-negative integers P,
N, D, Q, H, and D to
P + 5*N + 10*D + 25*Q + 50*H + 100*D = 100. Obviously D = 1 or 0, H is 0,
1 or 2, Q is 0, 1,2,3 or 4, D is from 0 to 10, and P is from 0 to 100.
If any of N, D, Q, H or D is nonzero, then P has to be divisible by 5.
There might be something useful in "Combinatory Analysis" by
Macmahon.
I seem to recall a similar problem in one of Henry Ernest Dudeny's
puzzle books, except that puzzle used the old British monetary system,
which was much more intricate than the decimal money system that has
since been established there.
Mark McConnell
>Don Detweiler (detw...@world.std.com) wrote:
>: The question was simple enough: How many different ways are there to
>: make change for a dollar.
>
>: ...we could use a silver dollar, half dollars, quarters,
>: dimes, nickels, and pennies, ...
>
>: Is there any mathematical formula that could be used to definitively
>: determine the correct answer?
>It is also th e number of distinct solutions in non-negative integers P,
>N, D, Q, H, and D to
>P + 5*N + 10*D + 25*Q + 50*H + 100*D = 100. Obviously D = 1 or 0, H is 0,
>1 or 2, Q is 0, 1,2,3 or 4, D is from 0 to 10, and P is from 0 to 100.
>If any of N, D, Q, H or D is nonzero, then P has to be divisible by 5.
The problem (I expect) was designed to make the 4th grader
think up the method kfoster gives here. Putting it in outline form:
How many ways using one silver dollar? Answer: 1. [100 = 100]
How many ways using no silver dollars? We have 3 cases to consider:
How many ways using two H's? Answer: 1. [100 = 50 + 50]
How many ways using one H? This equals the number of ways to make 50 cents
using only Q, D, N, P. We have 3 cases to consider:
How many ways using two Q's? Answer: 1. [100 = 50 + 25 + 25]
How many ways using one Q? This equals # ways to make 25 cents with
only D, N, P. We have 3 cases to consider:
How many ways using two D's? This = # ways to make 5 cents with only
N,P. Two cases:
One N: you're done. Answer: 1. [100 = 50 + 25 + 10 + 10 + 5]
No N: then you have to use all pennies. Answer: 1. [100 = 50 + 25 + 10
+ 10 + 1 + 1 + 1 + 1 + 1]
How many ways using only one D? ....
The original poster wrote that the problem had become an exercise in
tedium. It didn't have to. A 4th grader could get a kick out of seeing
a problem broken down into
a strict outline form this way. What control! A relentless march
of logic, until all 293 (or 500-something, whichever) cases are categorized
and explained.
If you have a taste for the abstract, this problem
is as cool as learning how to sandpaper is for someone who likes woodworking.
(Many adults find sandpapering tedious, but kids find it interesting
the first few times they do it. Ditto for this counting problem.)
John McGowan
> That should make it easier. If you like you can find the coefficient of
> x^100 in the product of three polynomials:
> 1 + x^25 + 2x^50 + 2x^75 + 3x^100
The first is the product of (1+x^25+x^50+x^75+x^100)(1+x^50+x^100) and
keeping only terms up to x^100 (the quarter and half-dollar polynomials)
> 1 + x^5 + 2x^10 + 2x^15 + 3x^20 + ... + 11x^100
I assume this is the product of the nickel and dime polynomials (keeping
terms only up through x^100 as they are all in which one is interested)
> 1 + x + x^2 + x^3 + x^4 + ... + x^99 + x^100
The pennies polynomial
(and multiplying by the "dollar" polynomial - 1+x^100 - only adds one to
the coefficient of x^100, so one can ignore that case and just add the
extra one rather than multiply by this polynomial)
Ray Steiner
>My fourth grade child recently came home with a "math challenge" problem,
>which essentially turned into a challenge in tedium.
>The question was simple enough: How many different ways are there to
>make change for a dollar.
>Presuming that we could use a silver dollar, half dollars, quarters,
>dimes, nickels, and pennies, we counted 547 different ways to make change
>for a dollar. Of course teachers workbook answer was off by a few
>hundred.
>Is there any mathematical formula that could be used to definitively
>determine the correct answer?
>Don
I did this problem with my students this term(all
prospective elementary teachers). We did it
by solving simpler problems first, and building up to
the required one,as ff:
a). How many ways can you make change for a quarter?
b). Use a to find out how many ways you can change a half
dollar.
c). Use a and b to solve your problem. In the course
of doing all these, some interesting sums will arise!
Ray Steiner
Dave Cromley
>My fourth grade child recently came home with ..
>The question was simple enough: How many different ways are there to
>make change for a dollar.
I hope I'm not giving a budding keen analytical mind some bad ideas.
My response was to write a QBASIC program to count.
There are 293 ways to make change for $1.00:
'--count number of ways to make change for $1.00 (in 10 sec)
' Dave Cromley
CLS : n = 0: k = 0
FOR i100 = 0 TO (100 - k) \ 100: k = i100 * 100
FOR i50 = 0 TO (100 - k) \ 50: k = k + i50 * 50
FOR i25 = 0 TO (100 - k) \ 25: k = k + i25 * 25
FOR i10 = 0 TO (100 - k) \ 10: k = k + i10 * 10
FOR i5 = 0 TO (100 - k) \ 5: k = k + i5 * 5
i1 = (100 - k) \ 1: k = k + i1 * 1
IF k = 100 THEN n = n + 1 ' (needed in case lowest coin is not 1)
PRINT USING "###(###) "; i100; i100 * 100; i50; i50 * 50;
PRINT USING "###(###) "; i25; i25 * 25; i10; i10 * 10;
PRINT USING "###(###) "; i5; i5 * 5; i1; i1 * 1;
PRINT USING " ### ###"; k; n
k = k - i1 * 1
k = k - i5 * 5: NEXT i5
k = k - i10 * 10: NEXT i10
k = k - i25 * 25: NEXT i25
k = k - i50 * 50: NEXT i50
k = k - i100 * 100: NEXT i100
END