21*. In how many ways can $n$ kopecks be made from coins:

a) of denomination 1 kopeck, 2 kopecks, and 3 kopecks?

b) of denomination 1 kopeck, 2 kopecks, and 5 kopecks?
21. a) When composing \( n \) kopecks from coins worth 1 kopeck, 2 kopecks, and 3 kopecks, we can either not use any 3 kopeck coins, use one such coin, use two, three, and so on up to \(\left[\frac{n}{3}\right]\) coins. In the first case, we need to compose \( n \) kopecks from coins worth 1 kopeck and 2 kopecks (this is possible in \(\left[\frac{n}{2}\right]+1\) ways; see problem 20); in the second case, we need to compose \( n-3 \) kopecks from such coins (this is possible in \(\left[\frac{n-3}{2}\right]+1\) ways); in the third case, \( n-6 \) kopecks (this is possible in \(\left[\frac{n-6}{2}\right]+1\) ways), and so on. In the last case, we need to compose \( k \) kopecks from coins worth 1 kopeck and 2 kopecks, where \( k \) is the remainder of the division of \( n \) by 3, which can be 0, 1, or 2 ( \( k \) kopecks can be composed in \(\left[\frac{k}{2}\right]+1\) ways). Thus, the total number of ways is

\[
\begin{array}{r}
\left(\left[\frac{n}{2}\right]+1\right)+\left(\left[\frac{n-3}{2}\right]+1\right)^{3}+\left(\left[\frac{n-6}{2}\right]+1\right)+\ldots \\
\cdots+\left(\left[\frac{k}{2}\right]+1\right)
\end{array}
\]

Let \( l \) be the quotient of the division of \( n \) by 3; then \( n=3 l+k \) and the desired number of ways can be represented as

\[
\begin{aligned}
&\left(\left[\frac{k}{2}\right]+1\right)+\left(\left[\frac{k+3}{2}\right]+1\right)+\ldots+ {\left.\left[\frac{k+3 l-3}{2}\right]+1\right)+ } \\
&+\left(\left[\frac{k+3 l}{2}\right]+1\right)
\end{aligned}
\]

We will prove that for each integer \( m \)

\[
\left[\frac{m}{2}\right]=\frac{m}{2}-\frac{1}{4}+\frac{(-1)^{m}}{4}
\]

Indeed, if \( m \) is even, then both the left and right sides of the equation are \(\frac{m}{2}\), and if \( m \) is odd, then both sides are \(\frac{m-1}{2}\).

Now we will transform the expression for the number of ways to compose \( n \) kopecks from coins worth 1, 2, and 3 kopecks. It can be rewritten as:

\[
\begin{aligned}
\left(\frac{k}{2}+\frac{3}{4}+\frac{(-1)^{k}}{4}\right)+\left(\frac{k+3}{2}+\frac{3}{4}+\frac{(-1)^{k+3}}{3}\right)+\ldots \\
\ldots+\left(\frac{k+3 l}{2}+\frac{3}{4}+\frac{(-1)^{k+k}}{4}\right)
\end{aligned}
\]

To compute this sum, it is convenient to rewrite it in a different order: first, write all terms equal to \(\frac{3}{4}\), then \(\frac{(-1)^{k}}{4} ; \frac{(-1)^{k+3}}{4} ; \ldots ; \frac{(-1)^{k+3 l}}{4}\), and finally, all other terms. Then we get the sum

\[
\begin{array}{r}
\left(\frac{3}{4}+\frac{3}{4}+\ldots+\frac{3}{4}\right)+\left(\frac{(-1)^{k}}{4}+\frac{(-1)^{k+3}}{4}+\ldots+\frac{(-1)^{k+3 l}}{4}\right)+ \\
+\left(\frac{k}{2}+\frac{k+3}{2}+\ldots+\frac{k+3 l}{2}\right)
\end{array}
\]

Here, in the first parentheses, the term \(\frac{3}{4}\) is repeated \( l+1 \) times; this gives \(\frac{3(l+1)}{4}\). In the last parentheses, there are \( l+1 \) terms of an arithmetic progression with a common difference of \(\frac{3}{2}\), the first term \(\frac{k}{2}\), and the last term \(\frac{k}{2}+\frac{3}{2} l\); the sum of this progression is \(\frac{\frac{k}{2}+\frac{3 l+k}{2}}{2}(l+1)\). Finally, in the middle parentheses, there is the sum of \( l+1 \) terms of a geometric progression with the first term \(\frac{(-1)^{k}}{4}\) and the common ratio \((-1)^{8}=-1\), i.e.,

\[
\left[\frac{(-1)^{k+3 l+3}}{4}-\frac{(-1)^{k}}{4}\right]:\left\lfloor(-1)-1 \left\lvert\,=\frac{(-1)^{k}}{8}\left[1-(-1)^{8 l+8}\right]\right.\right.
\]

this sum, which can be \(\frac{1}{4}, 0\) or \(-\frac{1}{4}\), we denote by \(\varepsilon\).

Thus, for the desired number of ways, we get the expression

\[
\frac{3(l+1)}{4}+\frac{(3 l+2 k)(l+1)}{4}+\varepsilon .
\]

But

\[
\begin{aligned}
& \frac{3(l+1)}{4}+\frac{(3 l+2 k)(l+1)}{4}+\varepsilon=\frac{(l+1)(3+3 l+2 k)}{4}+\varepsilon= \\
& =\frac{(3 l+3)(3 l+3+2 k)}{12}+\varepsilon=\frac{(n+3-k)(n+3+k)}{12}+\varepsilon= \\
& =\frac{(n+3)^{2}}{12}-\frac{k^{2}}{12}+\varepsilon .
\end{aligned}
\]

Notice now that if \( k \) is 0, then \(\frac{k^{2}}{12}=0\), and

\[
\varepsilon=\frac{1}{8}\left[1-(-1)^{3 l+8}\right]
\]

can be 0 or \(+\frac{1}{4}\); if \( k=1 \), then \(\quad \frac{k^{2}}{12}=\) \(=\frac{1}{12}\), and \(\varepsilon\) can be 0 or \(-\frac{1}{4}\), and if \( k=2 \), then \(\frac{k^{2}}{12}=\frac{1}{3}\), and \(\varepsilon\) can be 0 or \(\frac{1}{4}\). Therefore, \(-\frac{k^{2}}{12}+\varepsilon\) can take values lying between \(-\frac{1}{3}\) and \(+\frac{1}{4}\), i.e., this expression is always less than \(\frac{1}{2}\) in absolute value. Since the number of ways to compose \( n \) kopecks is an integer, it follows from our calculations that this integer is the closest integer to \(\frac{(n+3)^{2}}{12}\). Thus, the number of ways is given by the formula

\[
\left(\frac{(n+3)^{2}}{12}\right)
\]

b) Similarly, it can be proven that the number of ways to compose \( n \) kopecks from coins worth

\[
\left(\frac{(n+4)^{2}}{20}\right)
\]