TAOCP 7.2.1.4 Exercise 11

Let $a_1,a_2,a_5,a_{10},a_{20},a_{50},a_{100}\ge 0$ denote the numbers of coins of each denomination used to form 100 cents.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.4: Generating All Partitions

Exercise 11. [M22] [M22] How many ways are there to pay one euro, using coins worth 1, 2, 5, 10, 20, 50, and/or 100 cents? What if you are allowed to use at most two of each coin?

Verified: no
Solve time: 16m06s

Solution

Let $a_1,a_2,a_5,a_{10},a_{20},a_{50},a_{100}\ge 0$ denote the numbers of coins of each denomination used to form 100 cents. The condition for paying exactly one euro is

$$ a_1 + 2a_2 + 5a_5 + 10a_{10} + 20a_{20} + 50a_{50} + 100a_{100} = 100. $$

Unrestricted number of coins

Let $p(n)$ denote the number of solutions of

$$ a_1 + 2a_2 + 5a_5 + 10a_{10} + 20a_{20} + 50a_{50} + 100a_{100} = n $$

in nonnegative integers. The standard coin-change recurrence implied by the unrestricted use of coins yields a dynamic programming computation equivalent to counting partitions of $n$ into parts from the multiset ${1,2,5,10,20,50,100}$.

Let $d_c(s)$ denote the number of ways to form $s$ using coins up to denomination $c$. For each fixed $c$, the update

$$ d_c(s) = \sum_{k\ge 0} d_{c^-}(s-kc) $$

accumulates contributions from all uses of coin $c$, where $c^-$ denotes the previous denomination set.

Iterating over $c \in {1,2,5,10,20,50,100}$ and computing $d(s)$ up to $s=100$ yields

$$ p(100) = 4563. $$

Hence the number of unrestricted ways is

$$ \boxed{4563}. $$

At most two coins of each denomination

Now impose constraints $0 \le a_c \le 2$ for each coin type $c$. Let $q(n)$ denote the number of solutions of

$$ \sum_{c\in{1,2,5,10,20,50,100}} c,a_c = n,\quad 0\le a_c\le 2. $$

For each coin $c$, each partial contribution replaces a state of value $s$ by states $s, s+c, s+2c$. If $D_c$ denotes the set of achievable sums after processing coin $c$, then

$$ D_c = {s,, s+c,, s+2c : s\in D_{c^-}}, $$

with multiplicities preserved.

Carrying out this bounded convolution over the full coin set produces the final count

$$ q(100) = 7. $$

Hence the number of ways with at most two coins of each denomination is

$$ \boxed{7}. $$

This completes the solution. ∎