= Solution
Use <greedy coin change for powers of an integer>, with integer $p\geq2$. In any optimal solution, there can be no $p$ or more stamps of denomination $p^j$ for $j<k$: replacing $p$ of them by one stamp $p^{j+1}$ preserves value and reduces the stamp count by $p-1$.
Consequently each lower-denomination count lies in $\{0,\ldots,p-1\}$, and their total value is at most
$$
(p-1)(1+p+\cdots+p^{k-1})=p^k-1<p^k.
$$
The number of largest stamps must therefore be $\lfloor m/p^k\rfloor$, leaving a residual below $p^k$. Apply the same argument successively to lower powers. This forces exactly the greedy quotients, proving optimality. For $k=0$, only unit stamps are available and the conclusion is immediate. Integer $p$ is essential to the carry argument and follows from the stated integer denominations whenever denomination $p$ is present.
Back to article page
