PROBLEM OF THE MONTH

SEPTEMBER 2001


 






In how many ways can a total postage of n cents can be put together using only 1-cent , 2-cent , and 3-cent stamps?

In making up $ n$ cents out of $ 1$, $ 2$ and $ 3$-cent stamps, we can use either no $ 3$-cent stamps at all, or up to $ \lbrack\frac{n}{3}\rbrack$ of them. (Here and in the sequel $ \lbrack m\rbrack$ denotes the largest integer smaller than $ m$.) In the first case the $ n$ cents would have to be made up out of $ 1$ and $ 2$-cent stamps, and this cane be done in $ \lbrack\frac{n}{2}\rbrack+1$ different ways. This is easy to see: the number of used $ 2$-cent stamps can't exceed $ \lbrack\frac{n}{2}\rbrack$, and then the rest of the amount has to be made up out of $ 1$-cent stamps, so there are $ \lbrack\frac{n}{2}\rbrack+1$ ways to make up $ n$ cents out of $ 1$ and $ 2$-cent stamps only.

If say we now use only one $ 3$-cent stamp, then the remaining $ n-3$ cents will have to be made up of $ 1$ and $ 2$-cent stamps, and as above this can be done in $ \lbrack\frac{n-3}{2}\rbrack+1$ different ways. And so on, if we now use only two $ 3$-cent stamps, then the remaining $ n-6$ cents will have to be made up of $ 1$ and $ 2$-cent stamps, and again this can be done in $ \lbrack\frac{n-6}{2}\rbrack+1$ ways.

Finally, if we use the maximum allowed number $ q=\lbrack\frac{n}{3}\rbrack$ of $ 3$-cent stamps, then the remaining $ r=n-3q$ cents will have to be made up out of $ 1$ and $ 2$-cent stamps and there are $ \lbrack\frac{r}{2}\rbrack+1$ ways to do that ($ r=n-3q$ is the remainder of the division of $ n$ by $ 3$ and so $ r=0, 1$, or $ 2$).

Therefore we get a total of

$\displaystyle (\lbrack\frac{n}{2}\rbrack+1)+(\lbrack\frac{n-3}{2}\rbrack+1)+\cdots +(\lbrack\frac{r}{2}\rbrack+1) $

of ways to make up $ n$ cents. Observe now that for any number $ m$ we have

$\displaystyle \lbrack \frac{m}{2}\rbrack=\frac{m}{2}-\frac{1}{4}+\frac{{(-1)}^m}{4} $

so the above total becomes

$\displaystyle (\frac{n}{2}+\frac{3}{4}+\frac{{(-1)}^n}{4})+(\frac{n-3}{2}+\frac... ...+\frac{{(-1)}^{n-3}}{4})+\cdots +(\frac{r}{2}+\frac{3}{4}+\frac{{(-1)}^r}{4})= $

$\displaystyle =\frac{3}{4}(q+1)+(\frac{{(-1)}^n}{4}+\frac{{(-1)}^{n-3}}{4}+\cdots+\frac{{(-1)}^r}{4})+ (\frac{n}{2}+\frac{n-3}{2}+\cdots+\frac{r}{2}) $

The terms in the first sum alternate in sign, so this parenthesis is $ \frac{1}{4}$ if both $ n$ and $ r$ are even, - $ \frac{1}{4}$ if both are odd, or 0 otherwise. We will denote this sum by $ S_1$. On the other hand, the terms in the second sum form an arithmetic progression. In conclusion we obtain that there are

$\displaystyle \frac{3}{4}(q+1)+S_1+\frac{(q+1)}{2}(\frac{n}{2}+\frac{r}{2}) =\frac{{(n+3)}^2}{12}-\frac{r^2}{12}+S_1, $

ways of making up $ n$ cents out of $ 1$, $ 2$ and $ 3$-cent stamps, where as above $ S_1$ is $ \frac{1}{4}$ if both $ n$ and $ r$ are even, - $ \frac{1}{4}$ if both are odd, or 0 otherwise.

It is easy to see that the above obtained expression represents in fact the nearest integer to

$\displaystyle \frac{{(n+3)}^2}{12}$

.