The Dwarves in the Land-under-the-Mountain have just adopted a completely decimal currency system based on the Pippin, with gold coins to the value of $1$ Pippin, $10$ Pippins, $100$ Pippins and $1000$ Pippins. In how many ways is it possible for a Dwarf to pay, in exact coinage, a bill of $1997$ Pippins?
We notice that for a coin value $v$ and some amount of Pippins $p<v$, a $v$ value coin cannot be used to pay for this amount. This motivates the following.
Obs 1: We have to pay
- $7$ Pippins using $1$ value coins only. (only $1$ way to do this.)
- $90$ Pippins using $1$ and $10$ value coins only. (only $10$ ways to do this.)
- $900$ Pippins using $1, 10$ and $100$ value coins only.
- $1000$ Pippins using $1, 10, 100$ and $1000$ value coins only.
This motivates the idea of considering the problem in simpler stages. First we restrict ourselves to paying with only $1$ value coins. Then we extend to the case of $1$ and $10$ value coins and so on until we can tackle all four coin values given in the problem.
From $(1)$, we can consider our bill to be of $1990$ Pippins since the $7$ Pippins can only be payed by $1$ value coins.
Let $a_n, b_n, c_n$ and $d_n$ be the number of ways to pay for a bill of $n$ Pippins using coin values $\{1\}, \{1,10\}, \{1,10,100\}$ and $\{1,10,100,1000\}$ respectively.
Clearly, $a_n=1$ for all $n$. For $b_n$ we can use the $10$ value coin any of $i\in\{0, 1, ..., n/10\}$ times. Thus $b_n= n/10 + 1$.
For $c_n$ we can use the $100$ value coin any of $i\in\{0,1,..., n/100\}$ times. The $n-100i$ remaining Pippins can be payed in $b_{n-100i}$ ways. Hence
$$c_n=\sum_{i=0}^{n/100}{b_{n-100i}}$$
Since $n=1990$ we can write $d_n = c_{990} + c_{1990}$. Now
$$c_{1990} = \sum_{i=0}^{19}{b_{1990-100i}} = b_{1990} + b_{1890} + ... + b_{90} = 200 + 190 +...+ 10 = (210)(20/2) = 2100$$
and finally
$$c_{990} = b_{990} + b_{890} + ... + b_{90} = 100 + 90 +...+ 10 = (110)(10/2) = 550$$
Hence we can pay a bill of $1997$ Pippins, in exact coinage, in exactly $2100 + 550 = 2650$ ways.
No comments:
Post a Comment