Problem

Source: Serbia TST 2021, P5

Tags:



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$.