5. In the country of Lemonia, coins in circulation have denominations of $6n+1$, $6n+3$, $6n+5$, 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: $12 n^{2}+8 n-1$.

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

1) If $r \in \{1, \ldots, 6 n\}$ and $s \bmod (6 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 of value $6 n+1$ piastres. Suppose now that $s < m_{r}$ and the sum $s$ can be paid. In this case, several coins of value $6 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 $6 n+1$. This contradicts the minimality of $m_{r}$.
2) The numbers $2 k \bmod (6 n+1)$ take all values $\{1, \ldots, 6 n\}$ for $k=1, \ldots, 6 n$. Indeed, it is sufficient to show that all these numbers are distinct. If $2 k - 2 k' \equiv 0 \pmod{6 n+1}$, then $(k - k') \equiv 0 \pmod{6 n+1}$. Since $|k - k'| \leqslant 6 n$, we get $k = k'$.

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

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

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

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

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

$$
12 n^{2} + 14 n - (6 n+1) = 12 n^{2} + 8 n - 1
$$

## Variant 2