A Number Game puzzle

Question

Our team has created 9 math puzzles with ranging difficulty. Let me share one of them.

At the beginning a number is given to you. Your objective is to get a different number by making choices. Here's the pseudo code.

Let's say your number is $3$ and you need to reach $56$.

Start

If your number is ODD.

1. Mr. Black multiplies it by $3$

2. Then you should add $2$ or add $3$

3. Go back to Start with your new number

Else (your number is EVEN)

1. Mrs. White offers you to divide it by $2$

2. If you accept the offer

   1. Mrs. White divides your number by $2$

   2. Go back to Start with your new number

   Else

   1. Mr. Black multiplies your number by $3$

   2. Then you should add $2$ or add $3$

   3. Go back to Start with your new number

If you've managed to get $56$ in Start step of this algorithm, then puzzle is solved.

As an example, here's the evaluation

$3 \to 9 \to \text{by adding 2} \to 11 \to 33 \to \text{by adding 3} \to 36 \to \text{by accepting offer} \to 18 \to \text{by declining offer} \to 54 \to \text{by adding 2} \to 56$

Here are some puzzles for you to think $$3 \to 1$$ $$65 \to 9$$ $$15 \to 128$$

My hypothesis is: You can reach from any natural number to any other natural number (so there can be infinite pack of "interesting" puzzles). What I have noticed, the more these numbers are far from each other, the harder it is to reach to solution. The puzzle is inspired from well known problem :)

I have 3 questions:

1. Can you solve all of them? :)

2. Is there a strategy or an algorithm, by which you can always reach to solution with any given source and target numbers?

3. Can you prove or disprove my hypothesis?

You can try this puzzle with a more interactive way here (since level 6)

P.S: This is my first puzzle question. Hopefully the formatting is correct.

Answer 1

[EDITED to add: When I wrote this, the original statement of the problem had an error in it. That's now been fixed and I've adjusted my answer accordingly.]

The most interesting of the questions originally asked is the third: is it possible to get from any number to any other number by this process?

The answer is

yes, you can get from anywhere to anywhere.

First, the easy bit.

You can get from 1 to anything. Proof: I claim that everything other than 1 can be reached from something smaller, which plainly suffices. That's certainly true for numbers of the form $3n+2$ or $3n+3$ (which can be reached from $n$). The number $3n+1$ can be reached from $6n+2$ (which is always even and therefore halveable), which in turn can be reached from $2n$, which is smaller than $3n+1$. The only positive integers we haven't covered yet are 2, which we can reach as follows: 1, 6, 20, 10, 32, 16, 8, 4, 2; and 3, which we can reach as follows: 1, 6, 3.

Now the not-so-easy bit.

You can reach 1 from everywhere. This is uncomfortably similar to the Collatz conjecture, but the fact that we have a choice of what to do seems like it should help. So, I claim that any number bigger than 1 can lead to something smaller than itself, which plainly suffices. Even numbers are immediately halveable. A number of the form $4n-1$ yields (via the $3x+3$ operation) $12n$, which we can halve twice to get $3n$, which is smaller. (Unless n=1, when it's equal, but direct search shows that 3 can in fact be reduced.) So let's suppose our number is $4n+1$.

Now

it will in fact be helpful to consider four separate cases: our number is $16n+1,5,9,13$. (Special small cases: brute force shows that 5 takes 9 steps to reduce, 9 takes 6 steps, and 13 takes 6 steps.) We will then split the first two a little further: $32n+1,17$ and $32n+5,21$. Here goes:
32n+1 96n+6 48n+3 144n+12 72n+6 36n+3 108n+12 54n+6 27n+3
32n+17 96n+54 48n+27 144n+84 72n+42 216n+128 108n+64 54n+32 27n+16
32n+5 96n+18 288n+56 144n+28 72n+14 36n+7 108n+24 54n+12 27n+6
32n+21 96n+66 288n+200 144n+100 72n+50 216n+152 108n+76 54n+38 27n+19
16n+9 48n+30 24n+15 72n+48 36n+24 18n+12 9n+6
16n+13 48n+42 144n+128 72n+64 36n+32 18n+16 9n+8
... and, phew, it turns out that every case is reducible. So everything bigger than 1 can be reduced in at most 9 steps (almost always in at most 8 steps), so everything eventually leads to 1. Since everything is obtainable from 1 as well, we're done.

This, of course, also answers the second question: whether there's a systematic way to get from one number to another.

I just described one, though surely one can usually do better.

Credit where due:

thanks to noedne for pointing out (in comments below) a gap: I hadn't shown that $1\rightarrow2$ is possible. (Now I have.)