# 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!

• Are we to assume the statement "she has plenty of coins" is to mean the coin supply is always sufficient for any amount of change required? If not, then what if some coins have run out too?, in which case 20 pennies is the minimum. – Phil Nov 16 '17 at 6:11

[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:

1. 4 cents, 1 nickel, 1 dime and 14 quarters, OR
2. 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. • Thank you! What I finally believe is the correct answer haha! Something tells me my physics professor may not have this as his solution though... – Liam Cooney Nov 10 '17 at 20:03 • @Liam Cooney: But$3.44$can be done with$19$coins. If she always gives change with fewest possible coins, why would she use$20$coins? – Jens Nov 10 '17 at 20:15 • @Jens: If what you say is right, I made a mistake. How do you do$3.44 with 19 coins? – Rob Arthan Nov 10 '17 at 20:25
• 4 pennies, 1 nickel, 1 dime and 13 quarters. – Jens Nov 10 '17 at 20:27
• @Jens: thanks. The case I missed is that you might replace a larger coin with no coin. I have corrected my answer. – Rob Arthan Nov 10 '17 at 20:29

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 :-)

• Thank you! One point for me! – Liam Cooney Nov 10 '17 at 17:52
• Can't she replace the nickel and two dimes with a quarter? – Ned Nov 10 '17 at 17:54
• Oh shit... so now I’m thinking 4 pennies and 16 quarters? – Liam Cooney Nov 10 '17 at 18:06
• Yes, you are right. But the answer changes (I think) to 4 pennies, 1 nickel 1 dime and 14 quarters. – NickD Nov 10 '17 at 19:48
• Poor Nick haha...thanks for hanging in there!! – Liam Cooney Nov 11 '17 at 0:09

My guess is 4 pennies, a nickel, a dime, and 14 quarters for $3.69. • That’s what my friend said, but I can’t see how you could get away with only one dime. By what you commented above, I’m thinking it’d be 4 pennies and 16 quarters – Liam Cooney Nov 10 '17 at 18:25 • But 16 quarters and 4 pennies is 4.04 which is more than 3.69. See if you can make 3.69 in fewer than 20 coins. I don't see how! – Ned Nov 10 '17 at 18:59 • Yes I saw that shortly after I posted it but the process of reducing 2 dimes to 1 just seems sort of sketchy/ambiguous to me. Clearly it gives a better answer, but at first I feel like one’s intuition would say “well 2 dimes and a nickel is a quarter so we now have a quarter and everything else I guess must be a quarter too” until you realize that if you just replace two dimes with one, that you get a better answer. I feel like there’s got to be some other way to deduce that you want one dime. Am I making any sense? – Liam Cooney Nov 10 '17 at 19:02 • Try this. If you have two dimes then you can't have a nickel (else you can replace the 3 coins with one quarter). But if you have two dimes and no nickel, you can replace one of the dimes with a nickel and have the same number of coins with a lower sum. – Ned Nov 10 '17 at 19:05 • And if you have no dimes, then you have at most 5 non-quarters (given what you've already figured out), which means at least 15 quarters so you have more than$3.75. Finally, you don't want three dimes since those 3 coins can be replaced by quarter and nickel. So, you want exactly one dime. – Ned Nov 10 '17 at 19:14