Date: Mon, 23 Feb 1998 23:09:11 -0500
From: Alex Bogomolny
Hello:
I wonder where you found your equations.
The first problem first. f(n) = f(n-1) + f(n-2). That's correct. It's better to write F(N) = F(N-10) + F(N-20) meaning not the number of coins but the actual change.
However one pays Np, there had to be the last coin used. The latter may be either 10 or 20. For the remaining coins, we have F(N-10) and F(N-20) possibilities, correspondingly. This is how you arrive at the first equation.
In a similar way, for the second case you have f(n) = f(n-1) + f(n-5).
In general (if denominations are 10, 20, 30, ..., 70), then f(n) = f(n-1) + f(n-2) + ... + f(n-7).
This all are recurrent equations. The very first is Fibonacci's.
They are solved by trying f(n) = qn. For example, for the first problem, qn = q(n-1) + q(n-2). It follows that q satisfies q2 = q + 1. A quadratic equation with roots (1+sqrt(5))/2 and (1-sqrt(5))/2. The solution is a combination of two geometric terms corresponding to these roots.
For the second problem, the equation is of degree 5. I do not know whether it's solvable or not. Being of a very special form: q5 = q4 + 1, it might be.
The problem with 7 denomination leads to a 7 degree equation. If coins are 10, 20, 30, the equation is qubic: q3 = q2 + q + 1.
> Before this equation could be used, the first five in the series had > to be found out first.
You are right. But this is trivial. In small cases you may only use 10p.
If you plan to seek the problems out in literature or the Web, the key words are recurrence, recurrent, Fibonacchi. (Perhaps, recursive.)
Best regards,
Alexander Bogomolny
| 41169923 |
