How to make change for one dollar? [solved]

8 posts • viewed 243 times
I read that there are 294 ways to make change for a dollar. Given a decimal system with coins of 1 cent, 5 cents, 10 cents, 25 cents and 50 cents there are 294 different combinations of coins that add to one dollar. Can one of the mathematically inclined give a formula that can calculate the total combinations? For instance one combination would be 10x 1 cent, 1x 5 cent, 1x 10 cent, 1x 25 cent and 1x 50 cent. What is the formula, so that a country that has a 2 cent coin, one could add its denomination in the formula and get the answer to the number of combinations.
I started to write them out but it is a tedious task as you always miss one in the order and my list got messy. A formula of some sort would be easier.
Status changed to Solved (ThePoet, 11 Jun 2020, 03:55)
Should have searched before I asked. There are 293 combos. One site actually lists them all. Will take some time to see what the formula is actually doing.
We had a riddle last year with the similar problem
https://en.numista.com/forum/topic81032.html
I have often pondered the conundrum. For US coinage
If we are to include the half cent, two cent, three cent and twenty cent coins, the options increase.
And should the three cent nickel be considered separate from the three cent dime?
Is the nickel apart from the half dime?

A smart man learns from his mistakes.  A smarter man learns from someone else's.
New Zealand is much easier. Now that we've dumped the 1, 2 and 5 cent coins and just have 10, 20 and 50 there are only 10 different ways to make change for a dollar
What? Me Worry
I bet someone may program in basic something a bit like :

N=0 ‘number of occurrences for a sum equal to 100
For i=0 to 100
A=i
..For j=0 to 20
..B=5*j
....For k=0 to 10
....C=10*k
......For l=0 to 4
......D=25*l
........For m=0 to 2
........E=50*m
..........If A+B+C+D+E=100
..........N=N+1
..........Endif
........Endfor
......Endfor
....Endfor
..Endfor
Endfor
write N
Referee of south atlantic islands
In Canada I am still waiting for the nickel to be removed. I think they will go to a 20 cent coin if they do that instead if the 25 cent coin.
The programming solution is simple (elegant).
The link to the previous British solution boggled my mind. They must be glad they went to a decimal system. One could program a solution as above if you could decide which coins to use. Isn't that why America chose the decimal system to begin with? To be different than England or did they already know it was easier for accounting?
The mathematical solution still eludes me as the math language I am not conversant with. I did not think it would be so difficult to understand but looks like it is a normal problem for university level mathematics assignments. I do not understand what the link is to the denominations in the formula. I thought it would be some sort of choosing problem.
Quote: "ThePoet"​​The programming solution is simple (elegant).

​I'm not sure whether this is an optimal algorithm.
By the way, can anyone here write down the problem and/or the solution in pure mathematical notation, as formulae?
ūūūūū

» Forum policy

Used time zone is UTC+2:00.
Current time is 14:58.