What is the smallest number N such that it is impossible to have $1.00 in change consisting of preciseley N coins? You can use half-dollars, quarters, pennies, nickels, dimes and dollar coins. So N = 1 is the dollar coin. N = 2 is two half-dollars. N = 3 is a half-dollar and two quarters. Etc...
I'll give you a hint, it's lower than 100, but higher than you think!
This is a little confusing. The smallest number of coins that I can have without being able to make change for a dollar is 1 - the dollar coin.
ReplyDeleteHowever, based on the last sentence, "it's lower than 100", are you asking for the highest number of coins?
If so, wouldn't it be 99 pennies?
Certainly 101 cannot be done. But can we find smaller?
ReplyDelete1 - 4 are easy (quarters, dollars, and halfs).
HQDDN is 5, HDDDDD is 6, and we cover up to 11 by exchanging dimes for nickels 1 for 2.
Then 10D is good, and with the same exchange, 20 is covered.
3D5P can swap for 7N, bringing us from 20N to 6D6N10P for 22.
Swapping those 6D one at a time for 2N each gets us to 18N10P (28).
The 3D5P/7N swap brings us up to 6D4N20P (30).
D/2N shifts us to 16N20P (36).
3D5P/7N brings us back to 6D2N30P (38).
D/2N gets back to 14N30P (see the problems looming?)
3D5P/7N brings us back to 6D40P (46).
D/2N --> 12N40P (52)
3D5P/7N can be applied once: 3D5N45P (53).
D/2N --> 11N45P (56)
3D5P/7N --> 3D4N50P (57).
D/2N --> 10N50P (60)
3D5P/7N --> 3D3N55P (61).
D/2N --> 9N55P (64)
3D5P/7N --> 3D2N60P (65).
D/2N --> 8N60P (68)
3D5P/7N --> 3D1N65P (69).
D/2N --> 7N65P (72)
3D5P/7N --> 3D70P (73).
D/2N --> 6N70P (76)
Q75P is also (76)
2DN75P works, but that's (78).
That would make it 77
Mr Don, that last sentence was in the way of a hint. I was looking for the smallest number of coins that you can have such that you can't make a dollar in change. One dollar = one dollar coin is valid, since one dollar coin is change.
ReplyDeletejonathan, I believe that's a very thorough answer and I can't add anything else to it.