Change for a Dollar
Math brain teasers require computations to solve.
Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many ways are there to make change for a dollar?
HintThere are more than 200.
Hide
Answer
There are 292 ways.
Hide
Comments
Nike01
Aug 24, 2001
 wrong...192 
Mogmatt16
May 02, 2002
 explane please 
dewtell
Jul 25, 2002
 I get 292. Let N(a, c) be the number of ways
to represent an amount a using coins no larger than
value c. Then N(a, 1) = 1 (there is only one
way to represent any amount using only pennies), and N(0, c) = 1 (there
is only one way to represent an amount of zero, no matter what coins are available).
N(5n, 5) = n+1 (you can use anywhere from 0 to n nickels,
and then have to make the rest up in pennies).
N(10n, 10) = (n+1)^2 (the sum of N(0, 5), N(10,5), N(20, 5), ...,
N(10n, 5), which is the sum of the first n+1 odd numbers  it's
an old fact that this sum yields the perfect squares).
N(10n+5, 5) = (n+1)*(n+2).
Now go top down. We want N(100, 50). N(100, 50) = N(0, 25) + N(50, 25) + N(100, 25),
representing the use of 2, 1, and 0 fiftycent pieces, respectively.
N(50, 25) = N(0, 10) + N(25, 10) + N(50, 10).
N(100, 25) = N(0, 10) + N(25, 10) + N(50, 10) + N(75, 10) + N(100, 10).
Using our previous facts about N(a, 10), we find that
N(100, 25) = 1 + 12 + 36 + 72 + 121 = 242; N(50, 25) = 1 + 12 + 36 = 49;
and finally, N(100, 50) = 1 + 49 + 242 = 292.

dewtell
Jul 25, 2002
 Oops  reference to N(10n+5, 5) in the
previous comment should be N(10n+5, 10)
instead.

othbrady
Mar 07, 2003
 good 1 
GTregay
Jan 21, 2005
 I didn\'t take the time to follow the logic on this one  created an Excel spreedsheet, and it is indeed 292! 
darthforman
Apr 19, 2005

My head hurts.
It's the right answer but I don't really like the math ones. It takes too much work.

tdc_tmc
Aug 28, 2005
 woooooooow!!!!! too much for me 
hidentreasure
Nov 29, 2005
 Techer told me a while back. good teaser. 
irar1792
Dec 31, 2005
 AAAAAAAAAAAAAAAAAAggggggggghhhhhhhhhhhhh 
blackmarket69
Mar 08, 2006
 coins are shiny!!
i like things that r shiny 
Methlos
Mar 12, 2006
 it would be the same if you used GB pence 
spazzyjazzy93
Apr 05, 2006
 i got that but only because i read that fact on a snapple cap 
righteouschick2
Apr 08, 2006
 who has time for that stuff?Â¿? 
banzai
Jul 03, 2006
 my answer was 'alot"! 
hsbanana90
Aug 20, 2006
 that was hard. it would take forever to figure that out, unless you knew how to do the calculator functions. 
josty
Aug 27, 2006
 easy but long 
ari_1
Sep 04, 2006
 wooooah .....umm i got that wrong!! 
teasermaster
Oct 13, 2006
 Way to tough for me! 
kristybubba
Dec 06, 2006
 people call me the smart goddess of math but i aint that smart
it hurts my head 
kristybubba
Dec 06, 2006
 people call me the smart goddess of math but i aint that smart
it hurts my head 
QTkate
Jan 15, 2007
 um yeah well i agree with evryone else that was 2 hard foe my lil head 
bgil7604
Feb 23, 2007
 Wow, you must have WAY too much time on your hands if you know that answer! 
Brock
Jul 30, 2007
 nice 1 
Brock
Jul 30, 2007
 nice 1 
SuperDude512
Jul 31, 2007
 wow i jus realized how bad i am at math, NICE TEASER KID! 
Xosyaraiha
Aug 08, 2007
 they tried to ask that to my math class... and didn't succeed. glad SOMEONE could get the answer
thumbs up 
srpwuzhere
Nov 23, 2008
 I watched a Spongebob Squarepants episode where Spongebob was talking about change for $1 and $5. hehe. 
javaguru
Jan 11, 2009
 I did it similar to dewtell, slightly less formally.
The real break is between using dimes and smaller and using quarters and larger. So I broke the problem into making 100, 75, 50, 25 or 0 cents from dimes and smaller.
To make 100 cents from dimes and smaller start with 10 dimes and replace from 0 to 10 dimes with two 5s. Each 5 can be made from either a nickel or 5 pennies, so there is 1 way to replace 0 dimes, 3 ways to replace 1 dime, 5 ways for 2 dimes... giving the sum of the first 11 odd numbers, which as dewtell points out is 11^2 = 121. So making 100 cents with only dimes or less is 121.
75 cents has a 5 and 7 10s. From 0 to 7 10s can be replaced with two 5s. The extra 5 means that there is one extra way to make each value (because the first 5 can either be a nickel or 5 pennies). This gives 8^2 + 8 = 72 ways to do this. There is one way to make the 25 so there are 72 ways with 75 cents made from dimes and smaller.
50 cents is 6^2 = 36 times the two ways to make the 50 (50, 25 x 2) = 72.
25 cents is 3^2 + 3 = 12 times the two ways to make 75 (3x25, 50+25) = 2 x 12 = 24.
There are 3 ways to make a dollar with no dimes and pennies (2x50, 50 + 2x25, 4x25) = 3.
121 + 72 + 72 + 24 + 3 = 292

Jessiwa
Oct 20, 2011
 urgh.... math makes my head hurt soooo bad 
Back to Top
 

Follow Braingle!