You have access to $1, $5, $20, and $100 bills. What is the minimum number of bills you need to be able to make any amount from $1 to $100 using the fewest possible bills for each amount? For example, to make $4 you would need four $1 bills. You can reuse bills, so the total number of bills is not cumulative across amounts, just consider the minimum number needed for each specific value. Now, building on that: What is the smallest set of bills you need to always be able to make exact change for both a transaction of $x and a transaction of $(100 minus x), for any x less than 100?
Solution
Let the available bill denominations be
\[
1,\;5,\;20,\;100.
\]
For any amount \(n\) with \(1 \le n \le 99\), the optimal (fewest-bills) representation uses as many \(20\)'s as possible, then \(5\)'s, then \(1\)'s. We can write
\[
n = 20a + 5b + c
\]
with
\[
0 \le b \le 3, \qquad 0 \le c \le 4.
\]
Thus the largest number of each bill that could ever be required in an optimal construction is
\[
4 \text{ twenties}, \qquad 3 \text{ fives}, \qquad 4 \text{ ones}.
\]
To make \(100\) itself using the fewest bills requires
\[
1 \text{ hundred}.
\]
Therefore the smallest stock of bills that allows every value \(1\)–\(100\) to be made optimally is
\[
4(\$1),\;3(\$5),\;4(\$20),\;1(\$100).
\]
The total number of bills is
\[
4 + 3 + 4 + 1 = 12.
\]
Now we want one collection of bills that can simultaneously produce
\[
x \quad \text{and} \quad 100-x
\]
for every \(x<100\).
This means the entire collection must sum to \(100\), and every amount from \(0\) to \(100\) must be achievable as a subset sum.
Suppose the bill values in increasing order are
\[
v_1 \le v_2 \le \cdots \le v_k.
\]
A standard coverage condition states that to build every value from \(0\) up to the total sum, each new bill must satisfy
\[
v_i \le 1 + (v_1 + v_2 + \cdots + v_{i-1}).
\]
To introduce a \$5 bill, we must already be able to make up to \(4\).
Thus we need at least
\[
4 \text{ ones}.
\]
This gives total
\[
4.
\]
To introduce a \$20 bill, we must already be able to make up to \(19\).
Starting from \(4\), add three \(5\)-bills:
\[
4 + 5 + 5 + 5 = 19.
\]
So before any \(20\)-bill we must have
\[
4(\$1),\;3(\$5),
\]
which totals
\[
19.
\]
To reach \(100\) with as few additional bills as possible, use \(20\)-bills:
\[
4 \times 20 = 80.
\]
Adding this gives
\[
19 + 80 = 99.
\]
So one more dollar is needed, giving
\[
5(\$1),\;3(\$5),\;4(\$20).
\]
The total value is
\[
5 + 15 + 80 = 100.
\]
The total number of bills is
\[
5 + 3 + 4 = 12.
\]
Because the coverage condition holds, every value from \(0\) to \(100\) can be formed, so for any \(x\) we can choose a subset totaling \(x\), and the remaining bills total \(100-x\).