Optimal Coins for Exact Change Below $1?

[WannabeFeynman]

Homework Statement

What is the smallest number of coins needed to pay in exact change an change less then a dollar (coins are 1, 5, 10, 25 and 50 cents)?

Homework Equations

No relevant equations apart from a theorem:
Numbers between n and k inclusive, k>n, if k - n + 1

The Attempt at a Solution

I tried a variety of solutions such as going backwards. I looked that to make up to 4 cents, we needed 4 1cent coins. Then, for 9 cents we need either 1 5cent coin and 4 1cent or 9 1cent, and obviously it should be the former option. I tried going this way and messed up, so if anyone can clarify if this is the correct method or there is some other way. Thanks

Other info:
This is from a combinatorics textbook, by Niven. However, at this point, apart from the theorem above, we are assumed not to have learned any theory (i.e. permutations, combinations etc).

Thanks.

 

[Ray Vickson]

Homework Statement

What is the smallest number of coins needed to pay in exact change an change less then a dollar (coins are 1, 5, 10, 25 and 50 cents)?

Homework Equations

No relevant equations apart from a theorem:
Numbers between n and k inclusive, k>n, if k - n + 1

The Attempt at a Solution

I tried a variety of solutions such as going backwards. I looked that to make up to 4 cents, we needed 4 1cent coins. Then, for 9 cents we need either 1 5cent coin and 4 1cent or 9 1cent, and obviously it should be the former option. I tried going this way and messed up, so if anyone can clarify if this is the correct method or there is some other way. Thanks

Other info:
This is from a combinatorics textbook, by Niven. However, at this point, apart from the theorem above, we are assumed not to have learned any theory (i.e. permutations, combinations etc).

Thanks.

I won't present any kind of solution, but just point out to you that the well-studied "coin-changing problem" has some interesting and sometimes counterintuitive properties. A common way to make change is to use a so-called greedy algorithm; that is, to make change, start with as many as possible of the largest denomination, then as many as possible of the next largest, etc. (So, in your case, to make change for X cents the greedy algorithm would use as many 50-cent pieces as possible, then as many quarters as possible, then as many dimes, then as many nickels, then as many pennies until they all add up to X).

The interesting fact is that for some denomination sets the greedy algorithm produces provably optimal solutions (minimum number of coins), but for other denomination sets it does not---there are counterexamples. I won't spoil your fun by revealing whether or not greedy is optimal for the denomination set {50, 25,10,5,1} that you are using.

See, eg., http://en.wikipedia.org/wiki/Change-making_problem for a Knapsack formulation.

 

[WannabeFeynman]

Googling the problem led to some results which demonstrated that algorithm. Not really the solution, but thanks!

 

[haruspex]

a theorem:
Numbers between n and k inclusive, k>n, if k - n + 1

Something missing?

I looked that to make up to 4 cents, we needed 4 1cent coins. Then, for 9 cents we need either 1 5cent coin and 4 1cent or 9 1cent, and obviously it should be the former option. I tried going this way and messed up,

Seems like a good start. please post how far you got, and what makes you think you messed up.

 

[WannabeFeynman]

Sorry, I meant:
Numbers between n and k inclusive, where n and k are integers and k>n, is k - n + 1.

So, is the right approach? Is there a more algebraic solution to the problem? And then, how can I tell if I am getting the least amount of coins?

Thanks

 

[haruspex]

Sorry, I meant:
Numbers between n and k inclusive, where n and k are integers and k>n, is k - n + 1.

So, is the right approach? Is there a more algebraic solution to the problem? And then, how can I tell if I am getting the least amount of coins?

Thanks

I doubt there's a purely algebraic approach, but you can certainly deal with some of the simpler aspects quickly. If the smallest so many denominations are such that consecutive pairs are in whole number ratios then it's clear what to do there. What if this applies for some consecutive sequence somewhere, but not all the way from 1? Can you put upper limits on the number of each denomination (as you already did for the 1c coins) so that you get it down to a relatively small number of cases to check?

 

[willem2]

So after using a maximum of 4 1 cent coins, the change needed and all the values of the coins are divisible by 5, so you can reduce it to making 1-19 cents change, using 1,2,5,10 cent coins.