A positive integer $N$ is written on a board. In a step, the last digit $c$ of the number on the board is erased, and after this, the remaining number $m$ is erased and replaced with $|m-3c|$ (for example, if the number $1204$ is on the board, after one step, we will replace it with $120 - 3 \cdot 4 = 108$). We repeat this until the number on the board has only one digit. Find all positive integers $N$ such that after a finite number of steps, the remaining one-digit number is $0$.
Problem
Source: Argentina Cono Sur TST 2014, Problem 1
Tags: number theory proposed, number theory
08.09.2014 05:10
It divides the number you're looking at by $\pm10\mod 31$, so it must be $0\mod 31$. For $31n$ where $n$ is between 1 and 9, then we get 0, and for $n$ greater than 9, we get a number greater than 0 but less than the number itself, and still divisible by 31. So the answer is all multiples of 31.
06.05.2018 23:52
Let N = an.10^n + a(n-1).10^(n-1) + ... + a1.10 + a0 and N = x (mod.31). When you operate, the remainder number is: N' = an.10^(n-1) + a(n-1).10^(n-2) + ... + a1 - 3a0. N' = (N - a0)/10 - 3a0. Then, 10N' = x - 31a0 (mod.31) N' = x /10 (mod 31). So it'll only remain 0 if N' = 0 (mod.31). Now, you can proof by induction that every multiple of 31 satisfies.
18.12.2018 17:51
Let's observe the last number: $|m - 3c| = 0 \implies m = 3c$, now consider $a_i = $ the number generated after $i-th$ operation, so $a_0 = N$ and consider we made $q$ operations, so $a_i = 10m + c$ and $a_{i+1} = |m-3c|$. If $|m-3c| = m-3c \implies a_i \equiv 10.(m - 3c) + 31c \equiv 10.a_{i+1} \pmod {31}$, but if $|m-3c| = 3c - m$, then $a_i \equiv -10(3c-m) + 31c \equiv -10.a_{i+1} \pmod {31}$. Now let's make an induction to prove that $a_i \equiv 0 \pmod {31}:$ Start Case: $i = q:$ We have that $|m - 3c| = 0$ for $i = q$, so $m = 3c$ and $a_n = 10m + c = 10.3c + c = 31c \equiv 0 \pmod {31} \longrightarrow OK!$ Induction Hypotesis: Suppose that $a_i \equiv 0 \pmod {31}$ for some $i \in (1, 2, ..., n)$, let's show that $a_{i-1} \equiv 0 \pmod {31}.$ Inductive Step: We have that $a_{i-1} \equiv \pm10.a_i \pmod {31}$, as $a_i \equiv 0 \pmod {31} \implies a_{i-1} \equiv 0 \pmod {31}.$ The induction is complete. Then, $31|N$, let's prove that every multiple of $31$ is solution: Lemma: $a_i < a_{i-1}$, for $i \in (1, 2, 3, ... , q)$ Proof: Call $d = $ the last digit of $a_{i-1}$ and $n$ such that $10n + d = a_{i-1}$, so $a_i = |n - 3d| \geq 0$. As $i-1 < q$, then $31|a_{i-1} \implies a_{i-1} \geq 31$, because $a_i \geq 0$ and the process stops when $a_i = 0,$ so $a_{i-1}$ shouldn't be $0$. Thus, $a_{i-1} = 10n + d \geq 31$, and $n \geq 3$, if $|n - 3d| = n - 3d \implies a_i = n - 3d$ and $a_i < a_{i-1} \iff n-3d < 10n + d \iff 0 < 9n + 4d,$ as $d \geq 0$ and $n \geq 3$ it's true. If $|n-3d| = 3d - n \implies a_i < a_{i-1} \iff 3d - n < 10n + d \iff 2d < 11n$, again $d < 10$ and $n \geq 3 \implies 2d < 20$ and $11n \geq 33$, so $2d < 11n.$ As desired. So $a_i < a_{i-1}$ as $a_j \equiv 0 \pmod {31}$, and $a_j = |m-3c| \geq 0,$ then after a finite number of operations we wil get $a_q = 0$, because it's $31|a_j$ and $a_n$ is a decreasing sequence, so we must have $a_q = 0$. Thus all multiples of $31$ are solution.