4. On the board, a natural number $n$ is written. At each step, the number on the board can be replaced by the sum of two natural numbers whose product is equal to the number on the board. Determine the smallest number that can be written on the board after a finite number of steps, in dependence on the initial number $n$.

## 58th Mathematical Competition for High School Students in Slovenia  Maribor, April 12, 2014

## Solutions to the problems and scoring system
IV/4. Let's first show that if the number on the board decreases during a swap, then the new number is greater than or equal to 5. The number 1 cannot be obtained after a swap, since the sum of two natural numbers is never equal to 1. The number $2=1+1$ can only be obtained from the number 1, the number $3=1+2$ only from the number 2, and the number $4=1+3=2+2$ only from the numbers 3 or 4. Therefore, if we get a number less than 5 after a swap, then the number did not decrease during the swap. This means that if the initial number is $n \geq 5$, we can always reduce it to 5 after a finite number of steps, and we cannot obtain a smaller number according to the above reasoning.

The smallest number that can be written on the board after a finite number of steps is therefore equal to $5$ in the case of $n \geq 5$ or $n$ in the case of $n < 5$. We can always reduce $n \geq 5$ to 5, and we cannot obtain a smaller number.

If $m$ is even, i.e., of the form $m=2k$, where $k>2$ is a natural number, then we can replace it with the number $k+2$. This gives us a number that is smaller than $m$, since the condition $k+2 < m$ holds for $k>2$. If $m$ is odd, i.e., of the form $m=2k-1$, where $k>3$ is a natural number, then we can first replace it with the number $(2k-1)+1=2k$ and then with the number $k+2$. This way, we again get a number that is smaller than $m$, since the condition $k+2 < m$ holds for $k>3$. This means that if the initial number is $n \geq 5$, we can always reduce it to 5 after a finite number of steps, and we cannot obtain a smaller number.

The smallest number that can be written on the board after a finite number of steps is therefore equal to $5$ in the case of $n \geq 5$ or $n$ in the case of $n < 5$. We can always reduce $n \geq 5$ to 5, and we cannot obtain a smaller number.

[^0]:    Result $\frac{n+1}{2}$ 1 point

    Construction of $\frac{n+1}{2}$ red vertices such that the polygon they define does not contain the center

    ![](https://cdn.mathpix.com/cropped/2024_06_07_2324ea98e20bf8c655d1g-13.jpg?height=49&width=1633&top_left_y=1049&top_left_x=220)

    Discovery that there exists a longest diagonal with red endpoints ................ 2 points Discovery that there exists a red point on the same side of the longest diagonal with red endpoints as the center of the $n$-gon 1 point Justification that the center of the $n$-gon lies inside the triangle formed by the red vertices 2 points

[^1]:    Discovery that $\triangle A M C$ and $\triangle B N C$ are isosceles 1 point Writing the fact that in an isosceles triangle, the altitude and the angle bisector coincide 1 point Discovery that due to the above fact, $\angle C P A = \angle B R C = \frac{\pi}{2} \ldots \ldots \ldots \ldots 1$ point Discovery that $\angle I E C = \angle C D I$ because $E$ and $D$ are the points of tangency of the incircle .... 1 point

    Conclusion that $P$ and $R$ lie on the circle with diameter $\mathbf{C l}$ 1 point

    Conclusion that $D$ and $E$ lie on the circle with diameter CI 1 point Final conclusion that $P, R, D, E$ are concyclic 1 point