- #1
Goldenwind
- 146
- 0
Homework Statement
A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways to pay a bill of n pesos if the order in which the coins and bills are paid matters.
Reminder: I'm just asking for a hint, DO NOT solve this.
Homework Equations
To see an example of a recurrence relation, see my other thread.
The Attempt at a Solution
If I were approaching this in real life, I'd think of it like vending change after a customer bought something.
Say their change is 588 pesos.
I'd give them five 100 pesos bills, still owing 88 pesos.
Then give one 50 pesos bill, still owing 38 pesos.
Then give one 20 pesos bill, still owing 18 pesos.
Then give one 10 pesos bill/coin, still owing 8 pesos.
Then give one 5 pesos bill/coin, still owing 3 pesos.
Then give one 2 pesos coin, still owing 1 pesos.
Then give one 1 pesos coin.
But this is just one way. There are many, many, many other ways to do this, such as 588x1Pesos, 294x2Pesos, (5x100Pesos + 44x2Pesos), and so on.
I could program this in Java, using a method and multiple "Is a > b?" conditions, but clueless as to how to do this in a recursive formula [itex]a_n[/itex].
Another reminder: Hint only, don't solve.