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

Solution. A natural number $s$ is called $n$-decomposable if the sum $s$ can be paid with coins of denominations $2^{n}, 2^{n-1} \cdot 3, \ldots, 3^{n}$ piastres, and $n$-indecomposable otherwise. For $n=1$, only coins of 2 and 3 piastres are available. If $s \geqslant 3$, there exists an $r \in\{0,1\}$ such that $(s-3 r)$ is even. Then $s$ can be expressed as $3 r+2 k$, meaning it is 1-decomposable. It is also clear that the number 2 is 1-decomposable, while 1 is not. Thus, the largest 1-indecomposable number is $1=3^{2}-2^{3}$.

We will prove that for any natural $n$, the number $3^{n+1}-2^{n+2}$ is $n$-indecomposable. We will do this by induction. The base case has already been verified. Suppose the statement is true for $n-1$. Assume that the number $s=3^{n+1}-2^{n+2}$ is $n$-decomposable. If the sum $s$ includes $m$ coins of $3^{n}$ piastres, then $m3^{n+1}-2^{n+2}$, meaning the number $s$ is $n$-decomposable. Again, we will use induction on $n$. The base case has already been verified. Assume the statement is true for $n-1$. Choose $r \in\{0,1\}$ such that $s-r \cdot 3^{n}$ is divisible by 2. Let $N=\frac{s-r \cdot 3^{n}}{2}$. Then

$$
N>\frac{3^{n+1}-2^{n+2}-r \cdot 3^{n}}{2}=\frac{(3-r) 3^{n}-2^{n+2}}{2} \geqslant \frac{2 \cdot 3^{n}-2 \cdot 2^{n+1}}{2}=3^{n}-2^{n+1}
$$

By the inductive hypothesis, $N$ is $(n-1)$-decomposable. Therefore, there exist non-negative integers $k_{1}, \ldots, k_{n}$ such that

$$
N=k_{1} \cdot 3^{n-1}+k_{2} \cdot 3^{n-2} \cdot 2+\ldots+k_{n} \cdot 2^{n-1}, \quad \text { that is } \quad s=r \cdot 3^{n}+k_{1} \cdot 3^{n-1} \cdot 2+\ldots+k_{n} \cdot 2^{n}
$$

Thus, the number $s$ is $n$-decomposable.

## Variant 5