Initially, a positive integer $N$ is written on a blackboard. We repeatedly replace the number according to the following rules: 1) replace the number by a positive multiple of itself 2) replace the number by a number with the same digits in a different order. (The new number is allowed to have leading digits, which are then deleted.) A possible sequence of moves is given by $5 \to 20 \to 140 \to 041=41$. Determine for which values of $N$ it is possible to obtain $1$ after a finite number of such moves.
Problem
Source: Dutch TST 2024, 3.4
Tags: number theory, number theory proposed, blackboard, Digits
29.06.2024 15:34
We claim $N$ can be reduced to $1$ if and only if $3\nmid N$. The only if direction is simple, as we notice if the starting number is divisible by $3$, then all numbers in the sequence are divisible by $3$. Now pick any $3\nmid N$, we prove after some moves it can be reduced to $1$. (The following method is very possibly not the quickest one.)Some quick observations: i) The rules allow us to erase any $0$ in the number or add any $0$ to it. ii) The rules allow us to divide by $2$ or $5$ if possible(multiply by $5$ or $2$ then deleting the rightmost $0$). Thus, dividing by $2^n$ or $5^n$ is also permitted. By ii) we can let $\gcd(N,10)=1$.
Now we take the following steps: \begin{align*} \underbrace{1\cdots1}_{3u+2}&\xrightarrow{\times 10^{u+1}+1}\underbrace{1\cdots1}_{u+1}\underbrace{2\cdots2}_{2u+1}\underbrace{1\cdots1}_{u+1}\\ &\xrightarrow{\text{rearrange}}1\underbrace{1212\cdots12}_{2u+1\text{ of 12}}\\ &\xrightarrow{\div 2}5\underbrace{606\cdots06}_{2u+1\text{ of 6}}\\ &\xrightarrow{\text{delete 0, rearrange}}\underbrace{6\cdots6}_{2u+1}5\\ &\xrightarrow{\div5}1\underbrace{3\cdots3}_{2u+1} \end{align*}Then we notice that, for a number $N'=\frac{4\times 10^n-1}3=1\underbrace{3\cdots3}_n$, it is always possible to reduce it to $1$. This is because $$ 1\underbrace{3\cdots3}_n\xrightarrow{\times4}5\underbrace{3\cdots3}_{n-1}2\xrightarrow{\text{rearrange}}\underbrace{3\cdots3}_{n-1}25\xrightarrow{\div 25}1\underbrace{3\cdots3}_{n-1} $$reduces the number of $3$-s until it reaches $1$.