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?

This problem is basically a trickle-down sort of thing. If you have any solution that uses a ten cent coin, the next in line can be solved as well, with a reduced count of the ten cent coins. Similarly, any solution N that uses a 25 cent coin will have a viable solution of N+2 simply by replacing the 25 with 10, 10, and 5.

Continually doing this, we can determine where the smallest number will not allow a sum of 100. As soon as we hit 21, we are required to use 1 cent coins in multiples of 5. This is determined by the maximum allowable number of fives, and so on. It turns out that 77 is the smallest number, since we are required to use 75 1 cent coins and no two coins add to 25 cents.

Posted by Eric on 2004-07-14 08:58:50