62nd Czech and Slovak Mathematical Olympiad

Question

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 - 3c| (for example, if N = 1204 was written on the board, then after the step there will be 120 - 3 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.

Accepted Answer

Let us find N, which lead to zero on the board after only one step. Obviously |m - 3c| = 0 iff m = 3c, which is N = 10m + c = 31c. All such N are of the form N = 31c, c 1, 2, , 9. We show that the solution of the problem are exactly all multiples of 31. Since c = N - 10m, there is m - 3c = 31m - 3N, 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 31 9. Let N = 31k, where k 10. Then m 31, m - 3c > 0, thus |m - 3c| = 31m - 3N < 4N - 3N = N and we are done.