Minimum possible value of change My physics professor loves giving little logic puzzles at the end of our homework...
This weeks was “Sheila is a cashier at a convenience store and has run out of one-dollar bills, but she has plenty of coins - pennies, nickels, dimes, and quarters. She always gives the change with the fewest possible coins. The change she just gave a customer contained 20 coins. What is the minimum possible value of the change?” 
I’m asking this question here because a friend and I are disagreeing as to what the answer should be. Our general strategy is the same: we start by saying she gave 20 pennies since this is the least possible value of 20 coins. Then we note that this is impossible because Sheila wouldn’t give more than 4 pennies because she could just give a nickel instead (condition of least coins given). So now we have Sheila giving 4 pennies and 16 nickels. But this can’t be either because she would never give more than a nickel since she could just replace 2 nickels with a dime. And so on...but we’re getting a bit confused and have dissenting opinions when it comes to the dimes. 
Could someone help us out here? 
Thanks! 
 A: [Glossary for those who need it: a nickel is 5 cents, a dime is 10 cents and a quarter is 25 cents.]
We can't have 5 cents in the solution (because we could replace them with a nickel), so we have at most 4 cents. So we must actually have exactly 4 cents, because otherwise we could replace a larger coin by a cent and get a better solution.
If there is a nickel, there is exactly one nickel because 2 nickels can be replaced by a dime. In this case, there is also at most one and hence exactly one dime (because 2 dimes and a nickel can be replaced by a quarter, while if there are no dimes, a quarter can be replaced by a dime).
If there is no nickel, then there can be at most 2 dimes (because 3 dimes can be replaced by a nickel and a quarter).
So we have EITHER:


*

*4 cents, 1 nickel, 1 dime and 14 quarters, OR 

*4 cents, 2 dimes and 14 quarters. 


So option 1 wins, with the solution as $3.69. (And Ned's guess was right.)
Many thanks to Jens for pointing out an error in an earlier version of this answer.
A: She cannot give more than 4 pennies (otherwise, some of them could be replaced by nickels, reducing the count). She cannot give more than one nickel (otherwise, some of them could be replaced by dimes). She cannot give more than two dimes (otherwise some of them could be replaced by a nickel and a quarter). So far we have 4 pennies, 1 nickel, 2 dimes: the rest must be quarters since they cannot be replaced by anything bigger (she is out of dollar bills/coins). That makes for 13 quarters. The total amount is $3.54.
EDIT: as a comment makes clear, this is wrong: the nickel and two dimes could be replaced by a quarter. So we could either have one nickel and one dime OR two dimes. The coin count is the same in the two cases, but the former reduces the total change: 4 pennies, 1 nickel, 1 dime, 14 quarters = $3.69. That's my final answer :-)
EDIT2: I think this is wrong too: the 4 pennies/4 dimes/12 quarters solution in another answer minimizes the total change with the same number of coins.
EDIT3: There was a subtle error in the answer mentioned in EDIT2 - see the other answer for details. I should have stuck with my final answer :-)
A: My guess is 4 pennies, a nickel, a dime, and 14 quarters for $3.69. 
