Brain Teasers
Making Change
Canada and The United States have a quarter, dime, nickel, and penny (25, 10, 5, and 1 cent coins).
1. The minimum number of coins needed to make change for a dollar (i.e. to make any amount less than 100) is nine coins. For example, nine coins are required to make 99 cents: 3 quarters, 2 dimes, and 4 pennies. What is the only smaller amount that also requires nine coins?
2. Having a 20 cent coin instead of a dime would be more efficient; at most eight coins would be needed to make change for a dollar. See if you can make 89 cents with only eight coins (using 25, 20, 5, and 1 cent coins).
3. There are other coin values that are still more efficient, such as 25, 18, 5, and 1 cent coins. What is the fewest number of these coins needed to make 89 cents?
1. The minimum number of coins needed to make change for a dollar (i.e. to make any amount less than 100) is nine coins. For example, nine coins are required to make 99 cents: 3 quarters, 2 dimes, and 4 pennies. What is the only smaller amount that also requires nine coins?
2. Having a 20 cent coin instead of a dime would be more efficient; at most eight coins would be needed to make change for a dollar. See if you can make 89 cents with only eight coins (using 25, 20, 5, and 1 cent coins).
3. There are other coin values that are still more efficient, such as 25, 18, 5, and 1 cent coins. What is the fewest number of these coins needed to make 89 cents?
Hint
1. Take the answer for 99 cents and just replace one coin with a smaller one.2. Don't use as many quarters as possible (don't be "greedy").
3. You don't need any pennies.
Answer
1. 94 cents also requires nine coins: 3 quarters, 1 dime, 1 nickel, and 4 pennies.2. 89 cents can be made using 1 quarter, 3 twenty-cent coins, and 4 pennies. If you try to use as many quarters as possible (called a "greedy" algorithm), it actually takes more coins: 3 quarters, 2 nickels, and 4 pennies is nine coins. One advantage of the existing coin values is that the "greedy" algorithm always works: use as many coins of highest value first, then the next highest, and so on.
3. 89 cents can be made using only six coins: 1 quarter, 3 eighteen-cent coins, and 2 nickels. In fact, any amount under 100 can be made with just six coins. There are several other coin values (such as 24, 19, 4, and 1; or 28, 13, 6, and 1) that are just as efficient, but none is better. The problem with these "efficient" amounts is trying to figure out the best way to make change in your head.
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
I found this one lots of fun
9 cents also requires nine coins
9 cents can be made with 5 coins: 1 nickel and 4 pennies.
this was nice
Great teaser!
Got the first one without knowing it a few months ago, when my older brother asked me what amount of change takes the most coins.
Got the second one after about 3 minutes of calculating.
Then, I skipped the third one because it had 18-cent coins.
Got the first one without knowing it a few months ago, when my older brother asked me what amount of change takes the most coins.
Got the second one after about 3 minutes of calculating.
Then, I skipped the third one because it had 18-cent coins.
I think for #1 you meant to say "minimum". Maximum number would be 99 (99 pennies).
The key word is "needed" (you could use 99, but you only need 9 coins). There is only one correct value NEEDED, so maximum = minimum, but I agree with your point.
Making Change is all about efficiency, i.e. using the minimum number of coins possible. I submitted a change.
Making Change is all about efficiency, i.e. using the minimum number of coins possible. I submitted a change.
To post a comment, please create an account and sign in.
Follow Braingle!