What coins and how many of each are required to pay for any

What coins and how many of each are required to pay for any item from 1 cent to $1 included without receiving any change using the least number of coins.

Solution

You must have at least 4 pennies: this will cover items from 1-4 cents.

After that, you need a nickel: you now have items from 1-9 cents covered.

After this: you need a dime: you now have items from 1-19 cents covered.

Let\'s think about items between 20-24 cents. Adding a quarter would be too much, so we\'ll add another dime. We now have 1-29 cents covered.

Since we\'ve surpassed 25 cents, we can now add a quarter. We now have everything between 1-54 cents covered.

To cover the rest, we could add a half dollar.

Putting all the above together, we find the minimum required coins to have exact price between 1 cent and 1 dollar is 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1 half dollar.