In how many ways can a $5 \mathrm{Ft}$ coin be exchanged for $2 \mathrm{Ft}$, $1 \mathrm{Ft}$, $50 \mathrm{f}$, $20 \mathrm{f}$, and $10 \mathrm{f}$ coins so that among the coins given in change, there are 3 types - possibly more - from which at least 2 are given?
a) Let's denote the 200, 100, 50, 20, and 10 fillér coins, and their values, respectively, with the letters $K, S, \ddot{O}, H, T$. Then, a one- or two-coin exchange can be written as: $500=2 K+S=5 S=10 \ddot{O}$, and one valid exchange is: $3 S+2 \ddot{O}+4 H+2 T$. We will write the exchanges even more concisely, in the style of chemical formulas, for example, the previous ones as: $K_{2} S, S_{5}, \ddot{O}_{10}, S_{3} \ddot{O}_{2} H_{4} T_{2}$. Furthermore, let's call the part of the set of coins given in exchange that satisfies the requirement the "obligatory part," and the remaining part the "free part"; then the last example can be broken down into the obligatory and free parts in four different ways:

$$
S_{3} \ddot{O}_{2} H_{4} T_{2}=(S \ddot{O} H)_{2}+S H_{2} T_{2}=(S \ddot{O} T)_{2}+S H_{4}=(S H T)_{2}+S \ddot{O}_{2} H_{2}=(\ddot{O} H T)_{2}+S_{3} H_{2}
$$

b) The obligatory part can be assembled in 5 ways:
I. $(K H T)_{2}$,
II. $(S \ddot{O} H)_{2}$,
III. $(S \ddot{O} T)_{2}$,
IV. $(S H T)_{2}$,
V. $(\ddot{O} H T)_{2}$,

indeed, $K$ cannot be accompanied by either $S$ or $\ddot{O}$, and the remaining four types of coins, by omitting one from each in turn, give the four remaining ways to assemble the obligatory part. The value of the corresponding free parts in fillérs is:

$$
\text { I. } 40, \quad \text { II. } 160, \quad \text { III. } 180, \quad \text { IV. } 240, \quad \text { V. } 340
$$

and by going through the cases, we will determine how many different ways these can be assembled. Adding these numbers will give us more than the number of valid exchanges we are looking for, because - as we have seen - there are also exchanges containing the $(S \ddot{O} H T)_{2}$ part, but we cannot give 2 of each of the other 4 types of coins for the 5 fillér. Therefore, we need to subtract three times the number of exchanges containing the $(S \ddot{O} H T)_{2}$ part from the sum.

The $K$ coin can only be used in the assembly of the IV. and V. free parts, but only 1 at a time. We will see that it is useful to divide these cases accordingly, let IV. and V. be the ones where $K$ is not used, and if $K$ is used, then the

$$
\text { VI. } K(S H T)_{2}, \quad \text { VII. } K(\ddot{O} H T)_{2}
$$

parts need to be assembled in addition to the (free) part, the value of which in fillérs is

$$
\text { VI. } 40, \quad \text { VII. } 140
$$

The last number (140) can be assembled in as many ways as the $(S \ddot{O} H T)_{2}$ part. Let $f_{n}$ denote the number of ways to pay $10 n$ fillérs (where $n$ is a natural number or 0) using only $S, \ddot{O}, H, T$ coins. According to the above, the answer to the question of the problem is given by the following number:

$$
\begin{aligned}
f & =\left(f_{4}+f_{16}+f_{18}+f_{24}+f_{34}+f_{4}+f_{14}\right)-3 f_{14}= \\
& =2 f_{4}-2 f_{14}+f_{16}+f_{18}+f_{24}+f_{34}
\end{aligned}
$$

Here, $f_{4}=3$, because only $H$ and $T$ are relevant, and we can take 2, 1, or 0 of $H$. It is useful to generalize our thought process: $10 m$ fillérs (where $m$ is a non-negative integer) can be paid in

$$
g_{m}=\left[\frac{m}{2}\right]+1
$$

ways using only $H$ and $T$ coins, where the square brackets indicate that we should take the integer part of the number inside, for example, for $10 m=90$, $g_{9}=\left[\frac{9}{2}\right]+1=5$, according to whether we take 4, 3, 2, 1, or 0 of $H$. In other words, $g_{m}$ is the number of solutions of the equation

$$
2 x+y=m
$$

in non-negative integers, where $x$ is the number of $H$ coins and $y$ is the number of $T$ coins.

In this form, we can also use our result to determine the values of the other $f_{n}$, when $S$ and $\ddot{O}$ coins are also relevant, based on the fact that the value ratio of $S$ to $\ddot{O}$ is also 2, just like the ratio of $H$ to $T$. We demonstrate this for the case of $f_{34}$, the other cases of $f_{n}$ are similar but shorter in calculation. Let's break down 340 into a part divisible by 50 and a remainder:

$$
\begin{aligned}
340=300+40 & =250+90=\ldots=50+290=0+340, \text { generally } \\
340 & =50 m^{\prime}+10 m, \quad \frac{310}{10}=5 m^{\prime}+m,
\end{aligned}
$$

where $m^{\prime}$ and $m$ are non-negative integers, and write it as follows: the part divisible by 50 can only be paid with $S$ and $\ddot{O}$ coins. Then the payments of this part are again given by (2) solutions, if $x$ is the number of $S$ coins and $y$ is the number of $\ddot{O}$ coins. Going through the

$$
\begin{array}{rllrrlll}
m^{\prime} & =6, & 5, & 4, & 3, & 2, & 1, & 0 \\
m= & 4, & 9, & 14, & 19, & 24, & 29, & 34
\end{array}
$$

value pairs, we take every desired (i.e., $K$-free) payment of 340 fillérs in turn and only once. And since we need to combine every payment of the part divisible by 50 with every possible payment of the remaining part, we have

$$
\begin{aligned}
f_{34} & =g_{6} g_{4}+g_{5} g_{9}+g_{4} g_{14}+g_{3} g_{19}+g_{2} g_{24}+g_{1} g_{29}+g_{0} g_{34}= \\
& =4 \cdot 3+3 \cdot 5+3 \cdot 8+2 \cdot 10+2 \cdot 13+1 \cdot 15+1 \cdot 18=130
\end{aligned}
$$

Similarly, $f_{14}=19, f_{16}=25, f_{18}=31, f_{24}=58$, and with these, according to (1),

$$
f=212
$$

This is the number of different ways to exchange a 5 fillér coin for the allowed coins, while maintaining the additional requirement.

Based on the work of Lóránt Perge (Eger, Gárdonyi G. Gymnasium II. class), with further simplifications.