= Solution
Write $c_j=2^j+1$ for $0\leq j\leq k$, with a separate unit denomination. Choose, among all <minimum>-coin representations of the target, one whose vector of counts is lexicographically largest when larger denominations come first. Such a choice exists because a fixed positive target has only finitely many representations.
There cannot be two unit coins: replacing them by one $c_0=2$ decreases the count. For $j<k$, two copies of $c_j$ can be exchanged using
$$
2c_j=c_{j+1}+1.
$$
This keeps the coin count unchanged but increases the first differing larger-denomination count, contradicting the chosen lexicographic <maximum>. Thus \b[there exists an optimal representation using at most one of each denomination below the largest]. The largest denomination may repeat.
It remains to show why that normalization implies greedy optimality; uniqueness alone is not enough for an arbitrary coin system. Fix a denomination $c_j$. Let $L$ be the total value of all coins smaller than $c_j$ in the chosen optimal representation, and let $r$ be their number. These smaller coins are distinct. If $I\subseteq\{0,\ldots,j-1\}$ records the selected non-unit denominations, then
$$
L=\sum_{i\in I}2^i+r,\qquad \sum_{i\in I}2^i\leq2^j-1.
$$
If $L\geq c_j$, replace all $r$ smaller coins by one $c_j$ and $L-c_j$ unit coins. The new number of coins is
$$
1+L-c_j=L-2^j\leq r-1,
$$
contradicting optimality. Therefore \b[the total value below every denomination $c_j$ is strictly less than $c_j$].
At the largest denomination, this forces its count to be $\lfloor n/c_k\rfloor$: its residual value is nonnegative and smaller than $c_k$. Remove those coins. The same smaller-denomination property then forces the next quotient, and so on down to the unit coin. These are exactly greedy's choices, proving \b[greedy is optimal for every positive target]. The argument also covers $k=0$, where the denominations are two and one. Independent comparison with coin-change <dynamic programming> confirmed the formula for all $0\leq k\leq8$ and targets from one to 2,000; that finite check supplements the proof.
Back to article page
