In a board, the positive integer $N$ is written. In each round, Olive can realize any one of the following operations: I - Switch the current number by a positive multiple of the current number. II - Switch the current number by a number with the same digits of the current number, but the digits are written in another order(leading zeros are allowed). For instance, if the current number is $2022$, Olive can write any of the following numbers $222,2202,2220$. Determine all the positive integers $N$, such that, Olive can write the number $1$ after a finite quantity of rounds.
Problem
Source: Rioplatense L-3 2022 #6
Tags: combinatorics, number theory
14.12.2022 02:21
Slightly scuffed, but I believe this works. We claim the answer is $\boxed{\text{all non-multiples of 3}}$. All multiples of $3$ fail due to the fact that this is an invariant of the process, so you can never reach $1$. Suppose a number is not a multiple of $3$. We now outline an algorithm to take this number to 1: If the number has $2^a$ and $5^b$ in its prime factorization, multiply it by $5^a$ and $2^b$, and move all $a+b$ 0's to the front. This effectively removes all instances of the prime factors $2$ and $5$ Now, all prime factors of the number are $7$ or above (or the number is just $1$ already). Now, if this number is $k$, then note that $k$ divides $10^{\varphi(k)}-1$ by Euler's Theorem. Let $d$ be the smallest number that is at least $k$ such that $\gcd(10^d-1,k)=1$ Now, consider the string of digits $S_k$ which consists of a $1$ followed by $k-1$ $1$'s padded to $d$ digits concatenated with $2$ padded to $d$ digits, $3$ padded to $d$ digits, and so on to $k$ (written out) padded to $d$ digits. For example, for $k=7$, we have $d=7$, and thus. \[S_7=1000000100000010000001000000100000010000001000000200000030000004000000500000060000007.\]Now, for this $k$, there exists an $n$ such that the leftmost digits of $2^n$ is $S_k$ (due to Kronecker's Approximation Theorem on $\log 2$). Now, with this power of two, we can make it a multiple of $k$ by swapping the $r-1$-th block of $000\dots 001$ with the block containing $r$ (padded with $0$'s) for some $2\leq r\leq k$. This will shift the number by $(r-1)(10^N-1)$, where $N$ is the distance between these two blocks. Over all $r$, this value acquires all non-zero residues modulo $k$ (unless $\gcd(10^N-1,k)\neq 1$, in which case we can pad $0$'s between the $1$'s and non-$1$'s, increasing $N$ until this is true), so exactly one of this shifts will result in a multiple of $k$ at the end. The next step in the algorithm is multiplying to this multiple of $k$, and un-swap the digits to get $2^n$. Multiply by $5^n$ and move the $0$'s to the front, leaving $1$.