# Ways to deal money

1. Mar 14, 2008

### Goldenwind

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
To see an example of a recurrence relation, see my other thread.

3. 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 $a_n$.

Another reminder: Hint only, don't solve.

2. Mar 17, 2008

### Secui

Hi Goldenwind

Funny coincidence, but I've been dealing with the exact same problem and in fact I think I am in the same class as you because I have seen your posts before. I did manage to find a solution earlier on, and the resource I looked at that helped me is in the following link: