\frac{N}{10}$.
For the optimal bound take $N=10^k+12$ with $k\geq 2$. Then $M_l(N)=10^{k-1}+4$ and we have
$$\lim\limits_{N\to+\infty}\frac{M_l(N)}{N}=\frac{1}{10}.$$
\end{proof}
\section{The graph $G$ of the Choix de Bruxelles operation of order three}
Let $G$ denote the undirected graph, whose vertices are positive integers and two vertices are connected by an edge if and only if one vertex (represented by a number or a string) can be obtained by a valid Choix de Bruxelles operation of order three from the other vertex. We have for instance the following partial graph of $G$ (see Figure \ref{SubgraphG}). The graph is undirected since the operation is symmetric (invertible). We do not draw edges corresponding to empty strings.
\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[every node/.style={rectangle, draw=black, thick, minimum size=0.8cm},x=1.2cm, y=1.2cm]
\node (5) at (0,0) {$5$};
\node (15) at (1,0) {$15$};
\node (35) at (2,0) {$35$};
\node (95) at (3,0) {$95$};
\node (275) at (4,0) {$275$};
\node (815) at (5,0) {$815$};
\node (85) at (6,0) {$85$};
\draw (5)--(15)--(35)--(95)--(275)--(815)--(85);
\end{tikzpicture}
\caption{Subgraph of $G$.} \label{SubgraphG}
\end{center}
\end{figure}
We also represent the graph with the following simplified notation, that we will use frequently throughout the article:
$$5-15-35-95-275-815-85.$$
We show that the graph has infinitely many components and we describe how to find the corresponding component for a given number $N$.
We start with the simple case -- the number which the right-most digit is $0$. Whenever we write ``number can be reduced to'' we mean that after some number of iterations, a given number can be reduced with the Choix de Bruxelles operations to another number. To ``reduce the number of digits'' means to iterate the operation on $N$ so that the number $M$ which we obtain has $|M|<|N|$.
Let $Z(\ell)$ denote a string of $\ell$ zeroes. For example, $Z(3)={\tt 000}$. The following lemma describes the numbers $N$ that are of the form $N=A\cdot Z(\ell)$.
\begin{lemma}\label{Zerosattheend}
Any number $N$ of the form $N=A\cdot Z(\ell)$ with $\ell>0$ and $k$ not divisible by $10$ cannot be reduced to $k'\cdot Z(\ell')$ with $\ell'<\ell$ and $k$ not divisible by $10$.
\end{lemma}
\begin{proof}
Note that the right-most digit of $k'$, say $d$, would have to satisfy $d\cdot 3\equiv 0 $ (mod $10$), which is impossible.
\end{proof}
Lemma \ref{Zerosattheend} says that the number of zeroes at the end of the number $N$ stays fixed under the operation. This has a major consequence for the graph of the operation.
\begin{theorem}
The graph $G$ has infinitely many connected components.
\end{theorem}
\begin{proof}
This is an obvious consequence of Lemma \ref{Zerosattheend}.
\end{proof}
Since the graph has infinitely many components, it is interesting to find a description for each component by some sort of ``root'' number, that is, the numbers $N$ that cannot be reduced to a lower number. We do that with the help of the following definition.
\begin{definition}
The vertices labeled with the numbers $1\cdot 10^\ell$, $2\cdot 10^\ell$ and $5\cdot 10^\ell$ where $\ell$ is a non-negative integer, are called \textit{the roots} of the graph $G$.
\end{definition}
We now describe all components of the graph $G$. Its partial description is based on Lemma \ref{Zerosattheend}. We show that each number can be reduced by the Choix de Bruxelles operation of order three to one of the roots of $G$ and each root describes a different connected component. According to Lemma \ref{Zerosattheend}, it is enough to solve the cases where $10$ does not divide $N$.
\begin{lemma} \label{impossiblereductions}
The number $2$ cannot be reduced to $1$ or $5$. The number $5$ cannot be reduced to $1$.
\end{lemma}
\begin{proof}
Any valid operation on $2$ or its iterates gives a number $m\equiv 0$ (mod $2$). Furthermore, any valid operation on $5$ or its iterates gives a number $m\equiv 5$ (mod $10$).
\end{proof}
Lemma \ref{impossiblereductions} and Lemma \ref{Zerosattheend} show that any number of the form $1\cdot 10^\ell$, $2\cdot 10^\ell$ and $5\cdot 10^\ell$ belongs to a different component of the graph. We now describe which numbers belong to which component. For this, it is enough to find all numbers that can be reduced to a given root.
\begin{lemma}\label{Fivesattheend}
Any number of the form $N=10a+5$ can be reduced to $5$.
\end{lemma}
\begin{proof}
The proof goes by induction on the number of digits of $N$. If $|N|\leq 2$, then we use Figure \ref{FigAll2Digit5} to reduce such number to $5$ (the reduction is optimal).
\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[every node/.style={rectangle, draw=black, thick, minimum size=0.8cm},x=1.2cm, y=1.2cm]
\node (5) at (0,0) {$5$};
\node (15) at (1,0) {$15$};
\node (35) at (2,0) {$35$};
\node (95) at (3,0) {$95$};
\node (275) at (4,0) {$275$};
\node (815) at (5,0) {$815$};
\node (85) at (6,0) {$85$};
\node (45) at (2,1) {$45$};
\node (125) at (3,1) {$125$};
\node (165) at (4,1) {$165$};
\node (55) at (5,1) {$55$};
\node (225) at (5,-1) {$225$};
\node (75) at (6,-1) {$75$};
\node (115) at (2,-1) {$115$};
\node (135) at (3,-2) {$135$};
\node (195) at (4,-2) {$195$};
\node (65) at (5,-2) {$65$};
\node (25) at (6,-2) {$25$};
\draw (5)--(15)--(35)--(95)--(275)--(815)--(85) (275)--(225)--(75);
\draw (15)--(45)--(125)--(165)--(55);
\draw (15)--(115)--(135)--(195)--(65)--(25);
\end{tikzpicture}
\end{center}
\caption{Subgraph of $G$ with optimal reduction path for all odd two-digit numbers divisible by $5$.}\label{FigAll2Digit5}
\end{figure}
If $|N|>2$ and $N=k\cdot 10^\ell+5$, then $\ell\geq 2$ and the number can be reduced by one digit as follows (first step is to multiply a whole number by $3$):
$$k\cdot Z(\ell-1)\cdot\mathtt{ 5}-(3k)\cdot Z(\ell-2)\cdot\mathtt{ 15}-k\cdot Z(\ell-2)\cdot\mathtt{ 15}-k\cdot Z(\ell-2)\cdot\mathtt{5}.$$
Obviously,
$$|k\cdot Z(\ell-2)\cdot\mathtt{ 5}|=|N|-1.$$
If $|N|>2$ and two right-most digits of $N$ differ from $\mathtt{05}$, then we can reduce the string of these digits to $5$ according to the subgraph (Figure \ref{FigAll2Digit5}). In this case we also reduce $N$ by one digit.
By the principle of induction the reduction is possible for an arbitrarily long number.
\end{proof}
\begin{example}
Let $N=705$. Then, according to Lemma \ref{Fivesattheend}, we need at most $9$ iterations to reduce the number to $5$. Indeed:
$$705-2115-715-75-225-275-95-35-15-5.$$
Interestingly, this back-and-forth jumping between two and three-digit numbers is an optimal path for $705$. This result comes from computer analysis of all possible numbers that can be reached in a specified number of steps.
\end{example}
We now consider the numbers that are not divisible by $5$. Among all numbers that have to be reduced to one of the roots, we find some cases that do not follow the general rule of reduction. These are the numbers which have a substring $w=d_p\ldots d_k$ with $d_k \neq 0$ and $d_{k-1}=0$. We cover them in the following two lemmas.
\begin{lemma}\label{StringsOfZeroesOdd}
Any number $N$ of the form $N=k\cdot 10^\ell+d$, where $d\in\{1, 3, 7, 9\}$ and $\ell\geq2$, can be reduced by at least one digit.
\end{lemma}
\begin{proof}
The proof uses induction and is similar to the one of Lemma \ref{Fivesattheend}.
Let $N=k\cdot Z(\ell-1)\cdot d$ and $d\in\{7,9\}$. Since $\ell\geq 2$, the number $N$ can be reduced by one digit as follows:
\begin{equation}\label{Eq1}
k\cdot Z(\ell-1)\cdot d
-(3k)\cdot Z(\ell-2)\cdot (3d)
-k\cdot Z(\ell-2)\cdot (3d)
-k\cdot Z(\ell-2)\cdot d
\end{equation}
and
$$|k\cdot Z(\ell-2)\cdot d|=|N|-1.$$
The remaining cases are when $d=3$ or $d=1$. Since we have the reduction
$$k\cdot Z(\ell-1)\cdot \mathtt{1}
-k\cdot Z(\ell-1)\cdot \mathtt{3}
-k\cdot Z(\ell-1)\cdot \mathtt{9},$$
we can use operations in \eqref{Eq1} to reduce the last number again to a shorter one.
\end{proof}
\begin{lemma}\label{StringsOfZeroesEven}
Any number $N$ of the form $N=k\cdot 10^\ell+d$, where $d\in\{2, 4, 6, 8\}$ and $\ell\geq 2$ can be reduced by at least one digit.
\end{lemma}
\begin{proof}
The proof is up to obvious modification the same as for Lemma \ref{StringsOfZeroesOdd}. The case $d=2$ can be reduced to the case $d=6$ and the cases $d\in\{4,6,8\}$ are reduced like in \eqref{Eq1}.
\end{proof}
\begin{theorem}\label{ArbitraryReductionOdd}
Any odd number $N$ that is not divisible by $5$ reduces to $1$.
\end{theorem}
\begin{proof}
Figure \ref{FigOptimalOdd} in Appendix A is a partial graph connecting all at most two-digit numbers (and some with more digits if necessary) to $1$.
By Lemma \ref{StringsOfZeroesOdd} it is enough to prove the result for at most two-digit numbers. Indeed, if the number has more digits, we either apply Lemma \ref{StringsOfZeroesOdd} to remove the string $\mathtt{0}\cdot d$ or use the diagram in Figure \ref{FigOptimalOdd} (see Appendix A) to reduce the number from right to left by at least one digit. Then we use recursion to reduce the number to $1$.
\end{proof}
\begin{theorem}\label{ArbitraryReductionEven}
Any even number $N$ that is not divisible by $5$ reduces to $2$.
\end{theorem}
\begin{proof}
Figure \ref{FigOptimalEven} in Appendix A is a partial graph connecting all two-digit numbers with $2$.
By Lemma \ref{StringsOfZeroesEven} it is enough to prove the result for at most two-digit numbers. Indeed, if the number has more digits, we either apply Lemma \ref{StringsOfZeroesEven} to remove the string $\mathtt{0}\cdot d$ or use the diagram in Figure \ref{FigOptimalEven} (see Appendix A) to reduce the number from right to left by at least one digit. Then we use recursion to reduce the number to $2$.
\end{proof}
Let us summarize the results obtained in this section.
\begin{theorem}
Let $N$ be a positive integer and $N=k\cdot 10^\ell$ for some $k>0$ and $\ell\geq 0$. Then:
\begin{enumerate}
\item if $k$ is odd and not divisible by $5$, then $N$ reduces to the root $10^\ell$,
\item if $k$ is even and not divisible by $5$, then $N$ reduces to the root $2\cdot 10^\ell$,
\item if $k$ is odd and divisible by $5$, then $N$ reduces to the root $5\cdot 10^\ell$.
\end{enumerate}
Furthermore, each root defines a distinct connected component of the graph $G$ of the Choix de Bruxelles operation of order three.
\end{theorem}
\section{Numbers that are reached in $n$ steps}
For the part of calculation presented in this article we used the script written in Python. The script is provided in the accompanying file. With the aid of that script we find the cardinality of the set of all numbers that can be reached in $n$ steps. We gather them in Table \ref{TableHowManyNumbers}.
\begin{table}[h!]
$$\begin{array}{c|r|r|r}
\multirow{2}{*}{\text{Iteration}}& \multicolumn{3}{c}{\text{Starting number}} \\
& 1 & 2 & 5\\ \hline
3 & 4 & 6 & 15\\
4 & 7 & 18 & 58\\
5 & 18 &74 & 269\\
6 & 58 & 368 & 1401\\
7 & 259 & 2128 & 8243\\
8 & 1534 & 14511 & 55438\\
9 & 11329 & 112298 & 423551\\
10 & 95438 & &
\end{array} $$
\caption{How many numbers can be reached in $n$ iterations?}\label{TableHowManyNumbers}
\end{table}
\section{Counting steps}
Let $\tau(N)$ be the minimal number of steps to reach $N$ from $1$, $2$ or $5$ using the Choix de Bruxelles operation of order three. The values for small $N$ are gathered in Table \ref{valuesTau}. Note that in this section we do not consider numbers that are divisible by $10$.
\begin{table}[h!]
$$
\begin{array}{r|rrrrrrrrrrrr} \hline
N & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\tau(N) & 0 & 0 & 1 & 8 & 0 & 1 & 10 & 9 & 2\\ \hline
N & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\
\tau(N) & 11 & 7 & 10 & 7 & 1 & 6 & 9 & 2 & 9 \\ \hline
N & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 \\
\tau(N) & 9 & 9 & 8 & 8 & 6 & 8 & 3 & 9 & 7 \\ \hline
\end{array}
$$
\caption{The number of steps to reach $N$ from one of the roots. Multiples of $10$ are not included.}\label{valuesTau}
\end{table}
We now provide upper and lower bounds on $\tau(N)$ for large values of $N$. Let $\tau_1$, $\tau_2$ and $\tau_5$ be the functions counting steps for those numbers which root is $1$, $2$ and $5$, respectively.
First, we discuss upper bounds.
\begin{lemma}
Any number of the form $N=10a+5$ can be reduced to $5$ in at most $6\cdot |N|-6$ operations. In particular, $\tau_5(N)\leq 6\cdot |N|-6$ for all admissible $N$.
\end{lemma}
\begin{proof}
It is enough to count the number of iterations required to reduce the number $N$ by one digit. We consider the cases and use Figure \ref{FigAll2Digit5} and Lemma \ref{Fivesattheend}:
\begin{enumerate}
\item the number that does not end with $\mathtt{05}$ requires up to $6$ operations to be reduced by one digit,
\item the number that does end with $\mathtt{05}$ requires exactly $3$ operations to be reduced by one digit.
\end{enumerate}
In any case reduction by at least one digit requires at most $6$ iterations, hence at most $6\cdot (|N|-1)$ operations are required to reach $5$ from $N$.
\end{proof}
\begin{proposition}\label{PropBetterFives}
The reduction of numbers of the form $N=10a+5$ can be improved to $2$ digits per at most $9$ iterations.
\end{proposition}
\begin{proof}
This proof is computer assisted. With the aid of the algorithm written in Python we can check that all three-digit numbers can be reduced to $5$ with at most $9$ iterations. Moreover, we can also check that all four-digit numbers of the form $d_1\cdot {\tt 0}\cdot d_3\cdot {\tt 5}$ can be reduced to a two-digit number with at most $9$ steps. Then, for the remaining numbers, we can use recursion to reduce the number from right to left by two digits unless string $Z(\ell)\cdot A$ with $|A|=2$ and $\ell\geq 2$ appears.
The case $A=\mathtt{05}$ is covered by Lemma \ref{Fivesattheend} and requires exactly $6$ iterations to reduce by $2$ digits.
The remaining cases are the numbers of the form $N=B\cdot Z(\ell)\cdot d\cdot \mathtt{5}$ with $d\in \{1, 2, \ldots, 9\}$ and $\ell\geq2$. If $d\geq 3$, then we use the following reduction:
\begin{multline*}
B\cdot Z(\ell)\cdot (10d+5)-(3[B])\cdot Z(\ell-1)\cdot (30d+15)-\\
-B\cdot Z(\ell-1)\cdot (30d+15)-B\cdot Z(\ell-1)\cdot (10d+5)
\end{multline*}
and we have
$$|B\cdot Z(\ell-1)\cdot (10d+5)|=|N|-1.$$
If $d<3$, then we multiply $d$ by $3$ once to get to the previous case.
From the above it follows that any string of the form $B\cdot Z(2)\cdot A$ can be reduced to $B\cdot A'$ with $|B\cdot Z(2)\cdot A|\geq |B\cdot A'|+2$ in at most $7$ iterations, which is sufficient for the statement of proposition.
\end{proof}
\begin{example}
We use Proposition \ref{PropBetterFives} to reduce $30015$ by two zeroes in $7$ steps. We have the following chain:
$$30015-30035-90105-30105-3035-9105-3105-335.$$
\end{example}
\begin{lemma}\label{StepsReductionOdd}
Any odd number $N$ that is not divisible by $5$ can be reduced to $1$ in at most $12\cdot |N|$ operations. In particular, $\tau_1(N)\leq 12\cdot |N|$ for all admissible $n$.
\end{lemma}
\begin{proof}
Follows directly from Theorem \ref{ArbitraryReductionOdd} and Lemma \ref{StringsOfZeroesOdd}, where the reduction by at least one digit of any at least two-digit number and the reduction of any single-digit number to $1$ can be can be done in at most $12$ iterations.
\end{proof}
\begin{lemma}\label{StepsReductionEven}
Any even number $N$ that is not divisible by $5$ can be reduced to $2$ in at most $10\cdot |N|$ operations. In particular, $\tau_2(N)\leq 10\cdot |N|$ for all admissible $n$.
\end{lemma}
\begin{proof}
Follows directly from Theorem \ref{ArbitraryReductionEven} and Lemma \ref{StringsOfZeroesEven}, where the reduction by at least one digit of any at least two-digit number and the reduction of any single-digit number to $2$ can be can be done in at most $10$ iterations.
\end{proof}
\begin{remark}
Bounds for $\tau_5$ can be improved via Proposition \ref{PropBetterFives}, giving the following:
\begin{displaymath}
\tau_5(N)\leq
\begin{cases}9k, & \text{if $|N|=2k+1$ for some $k\geq 0$};\\ 9k-3, & \text{if $|N|=2k$ for some $k>0$}. \end{cases}
\end{displaymath}
These imply the following simple estimation:
$$\tau_5(N)\leq 4.5\cdot|N|-3.$$
\end{remark}
Let us discuss lower bounds. To do this, we first look at the greedy algorithm described in Theorem \ref{largestMu}. With the aid of that algorithm we can reach the following numbers. Let $r_i(n)$ be the largest number obtainable according to that theorem after $n$ iterations with the starting number $i\in \{1, 2, 5\}$.
\begin{table}[h]
$$
\begin{array}{c|r||c|r}
n & r_1(n) & n & r_1(n) \\ \hline
0 & 1 & 10 & 61246189 \\
1 & 3 & 11 & 612461827 \\
2 & 9 & 12 & 6124618221 \\
3 & 27 & 13 & 61246124663 \\
4 & 221 & 14 & 612461246189 \\
5 & 663 & 15 & 6124612461827 \\
6 & 6189 & 16 & 61246124618221 \\
7 & 61827 & 17 & 612461246124663 \\
8 & 618221 & 18 & 6124612461246189 \\
9 & 6124663 & 19 & 61246124612461827
\end{array}
$$
\caption{Values of $r_1$ for small $n$.}\label{r1values}
\end{table}
\begin{table}[h]
$$
\begin{array}{c|r||c|r}
n & r(n) & n & r(n) \\ \hline
0 & 2 & 10 & 318936318 \\
1 & 6 & 11 & 3189363124 \\
2 & 18 & 12 & 31893631212 \\
3 & 124 & 13 & 318931893636 \\
4 & 1212 & 14 & 3189318936318 \\
5 & 3636 & 15 & 31893189363124 \\
6 & 36318 & 16 & 318931893631212 \\
7 & 363124 & 17 & 3189318931893636 \\
8 & 3631212 & 18 & 31893189318936318 \\
9 & 31893636 & 19 & 318931893189363124
\end{array}
$$
\caption{Values of $r_2$ for small $n$.}\label{r2values}
\end{table}
\begin{table}[h]
$$
\begin{array}{c|r}
n & r(n)\\ \hline
0 & 5 \\
1 & 15 \\
2 & 115 \\
3 & 1115 \\
4 & 11115\\
5 & 111115 \\
6 & 1111115 \\
\end{array}
$$
\caption{Values of $r_5$ for small $n$.}\label{r5values}
\end{table}
Notice that:
\begin{enumerate}
\item by Table \ref{r1values} we have
$$r_1(n+4)=[\mathtt{6124}\cdot (r_1(n))]\qquad \text{for each}\ n\geq 5,$$
\item by Table \ref{r2values} we have
$$r_2(n+4)=[\mathtt{3189}\cdot (r_2(n))]\qquad \text{for each}\ n\geq 5,$$
\item by Table \ref{r5values} we have
$$r_5(n+1)=[\mathtt{1}\cdot (r_5(n))]\qquad \text{for each}\ n\geq 1.$$
\end{enumerate}
The last case can be expressed for $n\geq 0$ as
$$r_5(n)=\sum\limits_{k=0}^n10^k+4=\frac{10^{n+1}-1}{9}+4=\frac{10^{n+1}+35}{9}.$$
With the above in mind we can formulate the range in which the numbers $r_i(n)$ are possible.
\begin{theorem}\label{boundsforri}
For all admissible $n$, the following estimates hold:
\begin{align*}
6.124\cdot 10^{n-3}&