In the USA, there are coins of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents and 1 dollar.
You can pay one dollar using either one coin (100), or two coins (50 + 50), or three (50 + 25 + 25), or four (25 + 25 + 25 + 25), etc.

What is the smallest number such that you cannot pay $1 with that many coins?

Since all coins are multiple of 5 cents, you need 5P pennies to make a dollar, with P<20. The remaining 100-5P cents are 77-5P coins, worth at least 5 cents each,
100 - 5k >= 5 * (77 - 5k)
By algebra:
20 - k >= 77 - 5k
4k >= 57
k >= 57/4 = 14.25
Since k is an integer, k >= 15, i.e. we must have at least 5*15 = 75 pennies. We can't have more because 5*16 = 80 is already greater than
77. But then we must find exactly two coins to add up to the remaining 25 cents. By exhaustive search we show there is no such combination.

To complete the solution, it can be shown that for any number less than 77, there IS a solution... an exercise left to the reader!

Comments: (
You must be logged in to post comments.)