Question

What is the minimum number of coins you can use to come up with 67 cents out of quarters, dimes, nickels and pennies?

Answer 1

67=25+25+10+5+1+1

Answer 2

?

Answer 3

Six coins...?

Answer 4

i can see that...but how is this solved?

Answer 5

im pretty sure there's a better way than trial and error

Answer 6

you have minimum numbers of coins, you have to put the possible largest "cents" first.

Answer 7

Since 25>10>5>1, we have quarters first
then 67-25=42>25, then we have another quarter
42-25=17 where 25>17>10, then we have a dime
17-10=7, where 10>7>5, then we have a nickel
7-5=2, so we have another 2 pennies.
In total, 6 coins.

Answer 8

ah that's a much better explanation than giving an answer and solution. won't you agree?

Answer 9

I am lazy. :P

Answer 10

Wholeheartedly :)
I'd just like to note that in a freak case, where they mint coins of denominations which are relatively prime, using up the "highest valued" coins may not always be best...

Answer 11

For instance, how to get 40 cents using
13, 15, and 1 cent coins

Answer 12

I can show you an counter prove for "using up the "highest valued" coins may not always be best"

Answer 13

I thought you were lazy :)
All the same, I'd be happy to see it

Answer 14

We want to show that if we not using the "highest valued" coin first, we still can get minimum number of coins. Assume we have x cents with finite amount of coins. Suppose we have coins a>b>c and a>=b+c. If you do not use the "highest valued" a, then you have to use b and c instead of a which makes more amount of coins.