
4. There is written a number $N$ (in the decimal representation) on the board. In a step we erase the last digit $c$ and instead of the number $m$, which is now left on the board, we write number $|m-3 c|$ (for example, if $N=1204$ was written on the board, then after the step there will be $120-3 \cdot 4=108)$. We continue until there is a one-digit number on the board. Find all positive integers $N$ such that after a finite number of steps number 0 is left on the board. (Peter Novotný)


Solution. Let us find $N$, which lead to zero on the board after only one step. Obviously $|m-3 c|=0$ iff $m=3 c$, which is $N=10 m+c=31 c$. All such $N$ are of the form $N=31 c, c \in\{1,2, \cdots, 9\}$.

We show that the solution of the problem are exactly all multiples of 31 . Since $c=N-10 m$, there is $m-3 c=31 m-3 N$, that is the divisibility by 31 is preserved in the step. Now we show, that a multiple of 31 actually decreases in the step. We have already shown that for $N \leqslant 31 \cdot 9$. Let $N=31 k$, where $k \geqslant 10$. Then $m \geqslant 31$, $m-3 c>0$, thus $|m-3 c|=31 m-3 N<4 N-3 N=N$ and we are done.
