4. On a machine that operates with tokens of 1, 10, and 25 kuna, you can play this game: if you insert a 1 kuna token, you get one 10 kuna token; if you insert a 10 kuna token, you get one 1 kuna token and one 25 kuna token; if you insert a 25 kuna token, you get two 10 kuna tokens. At the beginning, you had one 10 kuna token. After some time, you found that you had exactly 100 1 kuna tokens and some other tokens. What is the smallest value of tokens you could have won by then?
4. First solution. Let $(a, b, c)$ denote the current number of tokens: $a$ of 1 kuna, $b$ of 10 kuna, and $c$ of 25 kuna. After

inserting a 1 kuna token, we will have $(a-1, b+1, c)$;

inserting a 10 kuna token, we will have $(a+1, b-1, c+1)$;

inserting a 25 kuna token, we will have $(a, b+2, c-1)$.

At the beginning, we had $(0,1,0)$. Suppose we inserted a 1 kuna token $x$ times, a 10 kuna token $y$ times, and a 25 kuna token $z$ times. After that, we will have

$$
(-x+y, 1+x-y+2z, y-z)
$$

Since we end up with exactly 100 tokens of 1 kuna, we get

$$
-x+y=100
$$

Let's find the smallest possible value for

$$
\begin{aligned}
S & =1 \cdot(-x+y)+10 \cdot(1+x-y+2z)+25 \cdot(y-z) \\
& =10+9x+16y-5z
\end{aligned}
$$

Since $x=y-100$, this expression becomes

$$
S=10+9y-900+16y-5z=-890+5(5y-z)
$$

This will be the smallest when $5y-z$ is the smallest possible. $y$ must be as small as possible, and $z$ as large as possible.

Notice that it must be: $1+x-y+2z \geq 0, y-z \geq 0$, i.e., $2z \geq 99, z \geq 50$ and $y \geq z$.

The result is smallest for $y=z=100$, and then $S=1110$.

Let's check if he could indeed win exactly 1110 kuna at the end. By inserting one 10 kuna token and then a 25 kuna token, a 1 kuna token and a 10 kuna token are obtained. Starting with one 10 kuna token and alternately inserting 10 and 25 kuna tokens, 100 tokens of 1 kuna and 101 tokens of 10 kuna are obtained. The total, minimum winnings of $M=1110$ kuna can indeed be achieved. 5 points

Second solution. Assume that during the game, $x$ tokens of 1 kuna, $y$ tokens of 10 kuna, and $z$ tokens of 25 kuna are inserted, and at the end, there are $X$ tokens of 1 kuna, $Y$ tokens of 10 kuna, and $Z$ tokens of 25 kuna. We know that $X=100$.

Each time a 10 kuna token is inserted, the number of 1 kuna tokens increases by one, and each time a 1 kuna token is inserted, the number of 1 kuna tokens decreases by one. Of course, inserting a 25 kuna token does not change the number of 1 kuna tokens. Since there were no 1 kuna tokens at the beginning, we have

$$
X=y-x
$$

Each time a 10 kuna token is inserted, the number of 25 kuna tokens increases by one, and each time a 25 kuna token is inserted, the number of 25 kuna tokens decreases by one. Inserting a 1 kuna token does not affect the number of 25 kuna tokens, and since there were no 25 kuna tokens at the beginning, we have

$$
Z=y-z
$$

Finally, let's express $Y$, considering that inserting a 1 kuna token increases the number of 10 kuna tokens by one; each time a 10 kuna token is inserted, their number decreases by one; and each time a 25 kuna token is inserted, the number of 10 kuna tokens increases by two. Since there was one 10 kuna token at the beginning,

$$
Y=1+x-y+2z
$$

10 points

From the equations derived, we get

$$
Y+2Z=1+y+x \geq 1+y-x=1+X
$$

where the inequality holds because $x \geq 0$. Let $S$ be the total value in kuna that he won at the end. Then

$$
\begin{aligned}
S & =X+10Y+25Z \geq X+10(Y+2Z) \\
& \geq X+10(X+1)=11X+10=1110
\end{aligned}
$$

Thus, he had a value of at least 1110 kuna in tokens.

10 points

To show that this is indeed the smallest winnings, it can be proven as at the end of the first solution.

## MINISTRY OF EDUCATION AND SPORT OF THE REPUBLIC OF CROATIA

 CROATIAN MATHEMATICAL SOCIETY
## MATHEMATICS