The following operation is allowed on the positive integers: if a number is even, we can divide it by $2$, otherwise we can multiply it by a power of $3$ (different from $3^0$) and add $1$. Prove that we can reach $1$ from any starting positive integer $n$.
Problem
Source: Serbia TST 2021, P5
Tags:
tigerzhang
26.10.2021 03:43
Beautiful problem . One of the hardest problems I've done!
Notice that $1$ is a power of $3$, so we're done.
Facejo
26.10.2021 03:48
tigerzhang wrote: Beautiful problem . One of the hardest problems I've done!
Notice that $1$ is a power of $3$, so we're done.
Wait... confusion?
Arrowhead575
26.10.2021 03:52
Isn't this a more general version of collatz
pog
26.10.2021 03:55
Let the starting number be $n$. If $n$ is even, we can divide it by $2$ until we get an odd number.
Thus, we can get to an odd number from all $n$. Now, we can just add to the next power of $2$ and divide by $2$ until we get to $1$.
As an example,
$$104 \to 52 \to 26 \to 13 \to 14 \to 15 \to 16 \to 8 \to 4 \to 2 \to 1$$
presumably this is just bad translation (or "powers" have a different definition in serbia i dunno)
megarnie
26.10.2021 03:58
pog wrote: Arrowhead575 wrote: Isn't this a more general version of collatz it's less general. also you can literally multiply by $1$ and add $1$ as $3^0 = 1$, so thus you just add to a power of $2$ and divide until you get to $1$ Maybe powers of $3$ are supposed to mean $3^n$, where $n$ is a positive integer.
tigerzhang
26.10.2021 04:06
Let $n \geq 11$ be an odd number. Notice that at least one of $3n+3$ and $3n+9$ is divisible by $4$. Thus, choose the one that is divisible by $4$, and divide that number by $4$. We end up with a number that is at most $\frac{3n+9}{4}$, which is less than $n$ when $n \geq 11$. So, we can reduce this problem to the case that $n \geq 9$ is an odd number. These can easily checked.
Justanaccount
26.10.2021 14:23
Bump this.