Coin Combination Problem

Probability Level 3

Using only pennies, nickels, dimes, and quarters, what is the smallest number of coins Freddie would need so he could pay any amount of money less than a dollar?

Note: 1 penny = 1 cent, 1 nickel = 5 cents, 1 dime = 10 cents, 1 quarter = 25 cents, 1 dollar = 100 cents

6 10 25 15

2 solutions

Trevor B.
Sep 26, 2014

Motivation for this question: Collect as many as you can of a smaller denomination until you can replace them with a larger denomination. While you would have the same amount of money if you had five pennies or one nickel, it would be less coins to keep the nickel, but you need four pennies in order to account for amounts not divisible by $5$ .

To get an amount between $5$ and $9$ cents, you would need one nickel and some pennies, but a dime would be the easiest way to get $10$ cents. Combinations of $1$ dime, $1$ nickel, and $4$ pennies will get you to $19$ cents, but two dimes are required to get up to $24$ cents. Then you can use a quarter.

You can apply this same logic to the ranges of $25$ to $49$ cents, $50$ to $74$ cents, and $75$ to $99$ cents. In the end, you will have $3$ quarters, $2$ dimes, $1$ nickel, and $4$ pennies to be able to get to 99 cents, so the answer is $\boxed{10}$ coins.

@Trevor B. To get 99 cents is 3 quarters, 2 dimes and 4 pennies.

AhGuek Duck - 6 years, 8 months ago

@AhGuek Duck Yes but how will you be able to get $80$ cents out of that arrangement?

Trevor B. - 6 years, 8 months ago

I actually just want to mention that part, but for 80 cents, 2 quarters + 3 dimes or 3 quater + 1 nickel I guess?

By the way I also has a bit confuse about the question as English is not my native language. Is it means first you have the combination of coins you mentioned above, so with that combination you had, you can make 1~99 cents; or just the highest number among minimum number of coins needed for any amount, for example 80 cents need at least 4 coins, then 81 cents need at least 5 coins and take then highest number?

AhGuek Duck - 6 years, 8 months ago

Note that the greedy algorithm need not result in the minimal solution. Can you substantiate why this results in the "smallest number of coins"? Does this hold true for any starting value (a dollar) and any starting configuration (1, 5, 10, 25)?

Calvin Lin Staff - 6 years, 8 months ago

Ahmed Obaiedallah
Jul 11, 2015

4 pennies, 2 nickels, 1 dime, and 3 quarters

you can use them to pay any amount of money less than 1 dollar

Coin Combination Problem

2 solutions

0 pending reports