In how many ways can you give change using coins of certain values?
Given a range of denominations of coins, find the number of ways to give change for a given amount using those
denominations (assuming there are always enough coins of each denomination).
This is called the Frobenius Coin-changing Problem.
If there is a coin of denomination 1, then all values are possible in change.
Otherwise some values are not possible: for example 1!
In general, for any set of denominations, there is a maximum impossible value beyond which all values are possible
using those denominations.
If all denominations have a common factor then only numbers with that factor are possible.
For just two (relatively prime) denominations A and B then all values from (A−1)(B−1) on are possible in change
and the maximum value not possible is (A−1)(B−1)−1 = AB−A−B.
The number of impossible values for this case is (A−1)(B−1)/2 (Sylvester, 1885; see Guy 2004).
A Coin Change Calculator
Coin Change C A L C U L A T O R
Coin denominations:
Separate the denominations (numbers only) by a comma
for up to
R E S U L T S
A Greedy algorithm solution?
If we are only interested in finding a way to make change for a given amount, then could we use a Greedy algorithm?
A Greedy algorithm is one that finds a solution by using first the largest value, as often as it can, then trying the smaller
values in turn on the remainder, each as often as they fit.
If it finally ends with a collection for the given number, it succeeds;
otherwise it fails.
If it fails, there is no going back to re-try other possibilities but when it works, it is fast.
For instance, with denominations 1 and 5 we can make 12 with 5+5+1+1 and this produces the fewest coins solution also.
However, if we introduce a new coin of value 4, the Greedy solution is the same but there is a shorter solution 4+4+4.
So the Greedy algorithm may find one solution but not always the best (if by that we mean the fewest coins).
However if we could also use coins of denomination 7 as well as 4 then the Greedy algorithm will find no solutions
(since it commits to including 7) whereas there is a solution of 4+4!
So a greedy algorithm for this problem will not work for all sets of denominations.
Variations
The Postage Stamp Problem
Suppose we have stamps of certain denominations and an envelope that only allows a certain maximum number of stamps.
What now is the smallest impossible value that we cannot made using those stamps?
The Chicken McNugget Problem
The Chicken McNugget problem is similar. If chicken nuggets are sold in packs of 9 or 20 what is the largest
number that cannot be bought? (151)
If they were also available in 6-packs, then we cannot buy 43 but all numbers beyond this are possible.
Lattice Lines
Consider a lattice of points which is a grid of whole-number coordinates (x,y) points
where x and y are zero or positive integers.
For two coins A and B (relatively prime) then to find a solution for value N we are finding integers x and y
(the number of As and Bs respectively)
for which xA + yB = N, a natural number.
This is equivalent to finding the coordinates of a point (x,y) on a line of slope -A/B whose equation is
y = N/B - xA/B.
When N gets larger, there is therefore always a lattice point on these lines for all N but for smaller
N there maybe lines that do not go through any grid point on the lattice.
References
The Frobenius Problem and its generalisations, J Shallit PDF
is a set of slides for a talk but it has several interesting variants of the Coin Change problem and a suggestion
as to how to improve the EU coins-and-notes system. Some of the talk is indeed at graduate level but there is
much here to interest the general reader.
Unsolved Problems in Number Theory (3rd edition 2004) by R Guy, Springer
Section C7 (pages 171-174) is all about the money-changing problem and has many references.
and there is also has an extensive bibliography on the subject.
This is essential reading for the serious researcher!
Question 7382 J J Sylvester Mathematical Questions from the Educational Times 1884 (37) page 26
This corrects the often seen (41) 1884 page 21 as in MathWorld and in Dickson - see Guy above, page 173.
Proves the results in section 1 above.
F G Frobenius (1849-1917) in a lecture posed the problem of
given n relatively prime numbers to find the largest number not representable by a sum of a whole-number of some or all of them,
called the Frobenius number of those numbers.
Dr Knott's Maths HOME page