Brain Teasers
Change for a Dollar
Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many ways are there to make change for a dollar?
Hint
There are more than 200.Answer
There are 292 ways.Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
wrong...192
explane please
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 fifty-cent 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.
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 fifty-cent 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.
Oops - reference to N(10n+5, 5) in the
previous comment should be N(10n+5, 10)
instead.
previous comment should be N(10n+5, 10)
instead.
good 1
I didn\'t take the time to follow the logic on this one - created an Excel spreedsheet, and it is indeed 292!
My head hurts.
It's the right answer but I don't really like the math ones. It takes too much work.
woooooooow!!!!! too much for me
Techer told me a while back. good teaser.
AAAAAAAAAAAAAAAAAAggggggggghhhhhhhhhhhhh
coins are shiny!!
i like things that r shiny
i like things that r shiny
it would be the same if you used GB pence
i got that but only because i read that fact on a snapple cap
who has time for that stuff?¿?
my answer was 'alot"!
that was hard. it would take forever to figure that out, unless you knew how to do the calculator functions.
easy but long
wooooah .....umm i got that wrong!!
Way to tough for me!
people call me the smart goddess of math but i aint that smart
it hurts my head
it hurts my head
people call me the smart goddess of math but i aint that smart
it hurts my head
it hurts my head
um yeah well i agree with evryone else that was 2 hard foe my lil head
Wow, you must have WAY too much time on your hands if you know that answer!
nice 1
nice 1
wow i jus realized how bad i am at math, NICE TEASER KID!
they tried to ask that to my math class... and didn't succeed. glad SOMEONE could get the answer
thumbs up
thumbs up
I watched a Spongebob Squarepants episode where Spongebob was talking about change for $1 and $5. hehe.
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
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
urgh.... math makes my head hurt soooo bad
To post a comment, please create an account and sign in.
Follow Braingle!