Please use latex: Octavio writes a integer $n \geq 1$ in a board and then he begins a process in which each step he erases the number $k$ written in the board and replaces it with one of the next numbers, as long as the result is integer: $3k-1, \quad 2k+1, \quad \frac{k}{2}$ Prove that for all integer $n \geq 1$, Octavio can get to write in the board the number $3^{2023}$ after a finite number of steps.

@hectorleo123 sorry, but the forum didn't let me because i'm new to the forum.

Sketch

kraDracsO wrote: Octavio writes a integer $n \geq 1$ in a board and then he begins a process in which each step he erases the number $k$ written in the board and replaces it with one of the next numbers, as long as the result is integer: $3k-1, \quad 2k+1, \quad \frac{k}{2}$ Prove that for all integer $n \geq 1$, Octavio can get to write in the board the number $3^{2023}$ after a finite number of steps. $\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ Let the $3$ operations be: $$k\overset 1\Rightarrow 3k-1$$$$k\overset 2\Rightarrow 2k+1$$$$k\overset 3\Rightarrow \frac{k}{2}$$$\color{red}\boxed{\textbf{Claim 1:}}$ $\color{red}\rule{24cm}{0.3pt}$ $$\textbf{If k is odd we can go from k to 3k}$$$\color{red}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{Proof:}}$ $\color{red}\rule{24cm}{0.3pt}$ $$k\overset 1\Rightarrow 3k-1 \overset 3\Rightarrow \frac{3k-1}{2} \overset 2\Rightarrow 3k_\blacksquare$$$\color{red}\rule{24cm}{0.3pt}$ Let the operation be $4$: $$k\overset 4\Rightarrow 3k$$$\color{red}\boxed{\textbf{Claim 2:}}$ $\color{red}\rule{24cm}{0.3pt}$ $$\textbf{Through the 4 operations we can get from k to 1}$$$\color{red}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{Proof:}}$ $\color{red}\rule{24cm}{0.3pt}$ Let us note that it is enough to prove that we can always decrease the number on the blackboard. If $k\equiv 0\pmod{2}: k\overset 3\Rightarrow \frac{k}{2}<k$ If $k\equiv 3\pmod{4}: k\overset 1\Rightarrow 3k-1 \overset 3\Rightarrow \frac{3k-1}{2}\overset 3\Rightarrow \frac{3k-1}{4}<k$ If $k\equiv 1\pmod{16}: k\overset 2\Rightarrow 2k+1\overset 2\Rightarrow 4k+3\overset 1\Rightarrow 12k+8\overset 3\Rightarrow 6k+4\overset 3\Rightarrow 3k+2\overset 1\Rightarrow 9k+5\overset 3\Rightarrow \frac{9k+5}{2}\overset 3\Rightarrow \frac{9k+5}{4}\overset 3\Rightarrow \frac{9k+5}{8}\overset 3\Rightarrow \frac{9k+5}{16}<k$ If $k\equiv 5\pmod{16}: k\overset 4\Rightarrow 3k\overset 1\Rightarrow 6k+2\overset 3\Rightarrow 3k+1\overset 3\Rightarrow \frac{3k+1}{2}\overset 3\Rightarrow \frac{3k+1}{4}<k$ If $k\equiv 9\pmod{16}: k\overset 4\Rightarrow 3k\overset 1\Rightarrow 9k-1\overset 3\Rightarrow \frac{9k-1}{2}\overset 3\Rightarrow \frac{9k-1}{4}\overset 3\Rightarrow \frac{9k-1}{8}\overset 3\Rightarrow \frac{9k-1}{16}<k$ If $k\equiv 13\pmod{16}: k\overset 4\Rightarrow 3k\overset 2\Rightarrow 6k+1\overset 2\Rightarrow 12k+3\overset 3\Rightarrow \frac{12k+3}{2}\overset 2\Rightarrow 12k+4\overset 3\Rightarrow 6k+2\overset 3\Rightarrow \frac{6k+2}{2}\overset 3\Rightarrow \frac{6k+2}{4}\overset 3\Rightarrow \frac{6k+2}{8}<k$ $$\Rightarrow \textbf{Claim 2}\text{ is proven}_\blacksquare$$$\color{red}\rule{24cm}{0.3pt}$ It is easy to see that repeating the operation $4$ $2023$ times from $1$ we can reach $3^{2023}_\blacksquare$ $\color{blue}\rule{24cm}{0.3pt}$

Nice problem! My solution is similar with #4

Lemma 1: we can obtain $3q+1$ Proof: $$q\stackrel{\text{2k+1}}{\rightarrow} 2q+1\stackrel{\text{3k-1}}{\rightarrow} 6q+2\stackrel{\text{/2}}{\rightarrow} 3q+1$$$\hspace{20cm}\blacksquare$ Lemma 2: If $q$ odd, then one of $3q-1$ and $3q+1$ is a multiple of 4 Proof: This is clear since are consecutive even integers $\hspace{20cm}\blacksquare$ Lemma 3: we can obtain $3^{2023}$ starting with $1$. Proof: Note that for $q$ odd $q\stackrel{\text{3k-1}}{\rightarrow} 3q-1\stackrel{\text{/2}}{\rightarrow} \frac{3q-1}{2}\stackrel{\text{2k+1}}{\rightarrow} 3q$, therefore we can do $1\rightarrow 3\rightarrow 3^2\rightarrow \cdots \rightarrow 3^{2023}$ $\hspace{20cm}\blacksquare$ By Induction, suppose the integers from $1$ to $k-1$ satisfies, we are gonna prove $k$ also satisfies. 1.- If $k$ is even then do, $k\stackrel{\text{/2}}{\rightarrow} \frac{k}{2}$, and by the hypothesis, this number satisfies 2.-If $k$ is odd, choose the one that is a multiple of $4$ between $3k-1$ and $3k+1$ and do the operation $/2$ two times, the result is a number less than $\frac{3k+1}{4}<k$, and by the hypothesis, this number satisfies. We are done. $\hspace{20cm}\blacksquare$

I somehow forgot to do this last year, but better late than never…. This cute problem was proposed by my friend Cristhian Gonzalez from Colombia. I hope that you enjoy his problem.