XXIX Rioplatense Mathematical Olympiad

First let us observe that rearranging digits does not change its sum, hence it does not change the remainder upon division by $3$. It follows that if $N$ is divisible by $3$ then we will only get numbers divisible by $3$ and hence we will never get $1$.

We claim that if $N$ is not divisible by $3$ then it is possible to obtain $1$ after a sequence of operations.

For the rest of the proof we will use that by multiplying by $10$ and reordering we can add or delete digits equal to $0$ in any position. We proceed in steps. First, we can assume that $N$ ends with the digit $1$. For this we initially multiply by $2$ sufficiently many times until the result starts with $1$ and then switch the first and the last digits.

Second, if the digit of $N$ in position $m$ from left to right is greater than $1$, then we can subtract $1$ from it and add a digit $1$ at the beginning. Indeed, since our number is relatively prime to $10$, then by Fermat-Euler theorem there are infinitely many $n$ such that $10^{m+n}-10^m+N$ is a multiple of $N$ and hence we can add and subtract $1$ to the digits in position $m+n$ and $m$ respectively. If we do this for arbitrarily big $n$ and then rearrange digits we prove the claim.

Third, if we repeat the previous step as many times as possible we get a number with digits $0$ and $1$ only. After further rearrangement we can get a number with all of its digits equal to $1$ which is not divisible by $3$.

Let $A_n$ be the number with $n$ digits and all of them equal to $1$. The conclusion of the above is that we can get to $A_n$ for some $n$ not divisible by $3$.

We claim that we can go from $A_k$ to $A_{k+9}$ and from $A_{2k}$ to $A_k$ by a suitable combination of the operations. For the first claim we observe that $10^k\equiv 1(\mathrm{mod}{A}_k)$ and hence we are able to replace the number $A_k$ by the following multiple: $10^{10k}+10^{9k}+\cdots +10^{2k}+10^k+A_k-10$. Afterwards, we delete all digits $0$ to get $A_{k+9}$.

To prove the second claim we add digits equal to $0$ to get a number composed of $k$ blocks $0000000000011$ and then we do the following simultaneously in each block: $$11\to 8129\to 8192\to 10000000000000\to 1.$$ This way we get a number with $k$ blocks $00000000000001$. After deleting all zeroes, we are done.

To finish the solution we use the first claim in the previous paragraph to first replace $A_n$ by $A_{n+9m}$ for some natural number $m$ such that $n+9m$ is a power of two and then we use the second claim to get to $A_1=1$ as desired.

The above is possible because the integer number $n$ is not divisible by $3$ and powers of two are $1,2,4,8,7,5,1,2,4,\dots$ modulo $9$ so that infinitely many of them are in the arithmetic progression $n,n+9,n+18,\dots$.