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?

Note that all numbers divisible by 4 are doable. This is because 20 involves 20 five-cent coins, and you can replace a five with five ones, each time increasing the count by 4. As long as two fives exist, you can do the one before it with a ten instead of two fives, and so on. The first time this breaks down is at 77.

Other numbers that are impossible are: 81, 85, 86, 89,90, 93, 94, 95, 97, 98, and 99.

Posted by Eric on 2004-07-14 09:10:53