Finding an "optimal" set of coin denominations 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.)
 A: 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$.
A: A simple heuristic is that we want to spread coins as evenly as possible.  If we are allowed $n$ coins of $d$ denominations, express $n=qd+r$ with $q=\lceil \frac nd \rceil-1$ and $1 \le r \le d$. We will have $r$ denominations with $q+1$ coins and $d-r$ denominations with $q$ coins.  We start with a coin of $1$ and each successive value is multiplied by one more than the number of coins of that value.  To have the maximum total value we have the smaller quantities of smaller coins.  The maximum value will then be $(q+1)^{d-r-1}(q+2)^r$ unless $r=d$ in which case the maximum value is $(q+2)^{r-1}$. With our parameters of $n=9,d=5$ we would have coins of $1,2,2,6,6,18,18,54,54$ which can make all values up to $161$.
