5. In the country of Lemonia, coins in circulation have denominations of $3n-1$, $6n+1$, $6n+4$, and $6n+7$ piastres, where $n$ is a natural number. A resident of the country went to the bank without any cash on hand. What is the largest amount that the bank will not be able to give him?
Answer: $6 n^{2}+4 n-5$.

Solution. Let's call a natural number $s$ decomposable if the bank can pay the sum $s$ using only coins of value $6 n+1, 6 n+4$, and $6 n+7$ piastres. For any $r=1, \ldots, 3 n-2$, let $m_{r}$ be the smallest decomposable number that gives a remainder of $r$ when divided by $3 n-1$. We will prove two statements.

1) If $r \in \{1, \ldots, 3 n-2\}$ and $s \bmod (3 n-1) = r$, then the bank can pay the sum $s$ if $s \geqslant m_{r}$, and cannot pay it if $s < m_{r}$. The first statement is obvious: one needs to pay the sum $m_{r}$ first, and then add some number of coins worth $3 n-1$ piastres. Suppose now that $s < m_{r}$ and the sum $s$ can be paid. In this case, several coins worth $3 n-1$ piastres must be used. Removing all these coins, we get a decomposable sum that is less than $m_{r}$ and also gives a remainder of $r$ when divided by $3 n-1$. This contradicts the minimality of $m_{r}$.
2) The numbers $3 k \bmod (3 n-1)$ take on the values $\{1, \ldots, 3 n-2\}$ for $k=1, \ldots, 3 n-2$. Indeed, it is sufficient to show that all of them are distinct. If $\left(3 k - 3 k'\right) \vdots (3 n-1)$, then $\left(k - k'\right) \vdots (3 n-1)$. Since $\left|k - k'\right| \leqslant 3 n-2$, we get $k = k'$.

Clearly, sums that are multiples of $3 n-1$ can be paid. Then, by 1), the answer to the problem will be $\max \left\{m_{1}, \ldots, m_{3 n-2}\right\} - (3 n-1)$. Let's find the largest of the numbers $m_{r}$. Let $r \in \{1, \ldots, 3 n-2\}$. Note that

$$
6 n + 1 = 2(3 n - 1) + 3, \quad 6 n + 4 = 2(3 n - 1) + 6 \quad \text{and} \quad 6 n + 7 = 2(3 n - 1) + 9
$$

By 2), there exists a unique number $k \in \{1, \ldots, 3 n-2\}$ such that $3 k \bmod (3 n-1) = r$. Since the remainders of the coins modulo $3 n-1$ take the values 3, 6, and 9, we need to represent $3 k$ as the sum of the smallest number of these numbers. This is achieved as follows: we add nines until we get the largest number not exceeding $3 k$, and then add 3 or 6 if necessary. In this sum, there will be $\left[\frac{k+2}{3}\right]$ terms. Then

$$
m_{r} = 3 k + \left[\frac{k+2}{3}\right] \cdot 2(3 n-1) \leqslant 3(3 n-2) + 2 n(3 n-1) = 6 n^{2} + 7 n - 6
$$

and equality is achieved when $k = 3 n - 2$. Therefore, the answer to the problem is

$$
\left(6 n^{2} + 7 n - 6\right) - (3 n - 1) = 6 n^{2} + 4 n - 5
$$

## Variant 6