The U.S. dollar has five coin denominations under a dollar (1¢, 5¢, 10¢, 25¢, 50¢).
To make sure you can make exact change for any amount up to (and including) 99¢, I believe that the fewest number of U.S. coins an optimal pocket would need is nine; for example: { 1¢, 1¢, 1¢, 1¢, 5¢, 10¢, 10¢, 25¢, 50¢ } or { 1¢, 1¢, 1¢, 1¢, 5¢, 5¢, 10¢, 25¢, 50¢ } would do the trick.
My first question then is: is there a set of five coin denominations with which we can make exact change up to and including 99¢ with fewer than nine coins? If not (as seems to me to be the case), can we prove that we cannot do better than nine coins in a manner more succinct than simply trying all the cases?
Following on, with the U.S. coin denominations, it seems possible to cover exact change up to and including 104¢ with nine coins.
My second question: can we find a set of five coin denominations that maximises the range of values covered with exact change using an optimal bag of nine coins?
My third question: can we generalise these previous questions for arbitrary values (i.e., an arbitrary number of coin denominations and/or an arbitrary target value)?
(This question comes from general curiosity mixed with ignorance of related problems. It seems to me the optimal coin values should follow some exponential function, but I am not quite sure what the base or the power should be.)
Best Answer
The following is a first stab at this problem.
If you have a fixed base $b$, then one can generate change up to $b^k-1$ with $k(b-1)$ coins. For instance, in binary, one can generate change up to $\$1.27$ with single coins each of denomination $1, 2, 4, 8, 16, 32, 64$ cents. In ternary, one can generate change up to $\$2.42$ with two coins each of denomination $1, 3, 9, 27, 81$ cents. And so on.
In that sense, the most bang for the buck (as it were) can be determined by identifying, for any given amount $M-1$ and base $b$, the required number of "stages" $k = \lceil \log_b M \rceil$, and then minimizing the number of coins $N = k(b-1)$. That is, we minimize
$$ N = (b-1) \lceil \log_b M \rceil $$
Note that this is something of an overestimate, since not all coins in the uppermost "stage" may be needed (for instance, for $\$1.00$ in ternary coins, we do not need two $81$-cent coins), but it will give us a general idea of the principles involved. Let us avoid the discrete niceties of $N$ and instead minimize
$$ N_0 = (b-1) \log_b M $$
and then
$$ \frac{dN_0}{db} = \frac{(1-b+b \ln b) \ln M}{b (\ln b)^2} $$
Since both $\ln M$ and $b (\ln b)^2$ are positive in the range in question, minimizing $N_0$ amounts to finding $1-b+b\ln b = 0$. But $1-b+b\ln b$ is also always positive, for $b > 1$, so our best bet (in discrete coins) is to choose the minimum $b$, which is $2$: We should use binary coins to minimize the number of coins needed to make change, for most amounts. The number of coins needed is then
$$ N = \lceil \lg M \rceil $$
where $\lg$ is log to the base $2$. It would be an interesting exercise (which I will defer for the moment) to determine for which amounts other coin configurations outperform binary.
ETA: Returning to think about this again, I think it must be that no other combinations can ever outperform binary (in the sense of requiring fewer coins); they might require as many, but never fewer.
One way to see this is to consider the cases where $M-1 = 2^k$—that is, situations where we must make change for all amounts up to a power of $2$. That is where binary coins are at their least efficient, since they include the single coin of that uppermost power of $2$, for a total of $k+1$ coins. For instance, to make change for $16$ cents, we must include a $16$-cent coin.
In order to outperform that, however, we must somehow make change with some other configuration for all amounts up to $2^k$ using only $k$ coins. But the number of non-empty subsets of a set of $k$ coins is only $2^k-1$. Therefore, there aren't enough selections of coins to make change in a way that is better than binary coins, so binary coins are always (among) the best.
Therefore, the answers to the first two questions are:
1. Coins of $1, 2, 4, 8, 16, 32, 64$ cents (seven in all) suffice to make change for any amount up to $\$1.27$, as noted above.
2. Nine coins, in binary configuration, suffice to make change for any amount up to $\$5.11$.