To start, we prove the following lemma which will be used in both parts. Lemma: Given $2^n < k < 2^{n+1}$, Santa can travel from $2^n$ to $k$ in $1$ ride. Proof: Write $k = 2^{a_1} + 2^{a_2} + \dots + 2^{a_i}$, where $0 \le a_1 < a_2 < \dots < a_i = n$ is the binary representation of $k$. As $2^{a_1},2^{a_2},\dots,2^{a_i}$ are distinct divisors of $2^n$, we have the ride $$2^n \rightarrow 2^{a_1} + 2^{a_2} + \dots + 2^{a_i} = k.$$This proves the lemma. a) We claim that this is possible. Write $n = \lfloor\log_2k\rfloor$. Claim: Santa can travel from $m$ to $2^a$ in at most $2a$ rides for $a \in \mathbb{N}$. Proof: We prove this by induction on $a$. For $a = 1$, if $m$ is even, we have $m \rightarrow 2$. Otherwise, we have $m \rightarrow m+1 \rightarrow 2$. Now, suppose that we may travel from $m$ to $2^a$ by $2a$ rides. From our lemma, Santa can travel from $2^a$ to $2^{a+1}-1$ in $1$ ride, and from $2^{a+1}-1$ to $2^{a+1}$ in $1$ ride. So, Santa can travel from $m$ to $2^a$ in $2a$ rides, and from $2^a$ to $2^{a+1}$ in $2$ rides. So, Santa may travel from $m$ to $2^{a+1}$ in $2(a+1)$ rides, proving the claim. From the above claim, Santa can travel from $m$ to $2^n$ in at most $2n$ rides. If $k = 2^n$, we're done. Otherwise, from our lemma, Santa can travel from $2^n$ to $k$ in $1$ ride. Overall, Santa can travel from $m$ to $k$ in at most $2n+1$ rides, so we're done. b) We claim this is possible as well. Once again, let $n = \lfloor\log_2k\rfloor$. Claim: If $m$ is not a power of $2$, Santa may travel to a bigger number, while increasing $\nu_2(m)$. Proof: Write $m = 2^a \cdot b$, where $b$ is odd. From our assumption, $b > 1$. Then, we have $m \rightarrow m + 2^a = 2^a(b+1)$. This is obviously a bigger number. As $b$ is odd, $b+1$ is even, so $\nu_2(2^a(b+1)) > a = \nu_2(m)$, proving the claim. Now, we'll call the following ride described above a super ride. Santa will perform super rides until the number $a$ Santa is on satisfies $\nu_2(a) \ge n$. This takes at most $n$ super rides; If $a$ ever becomes a power of $2$ in the first $n$ super rides (so Santa can't perform any more super rides), as $a > m \ge 2^n$, $\nu_2(a) \ge n$. Otherwise, $\nu_2(m)$ increases by at least $1$ after every super ride, so after $n$ super rides, $\nu_2(a) \ge n$. Then, we have the rides $a \rightarrow 2^n \rightarrow k$, where the latter follows from our lemma (and if $2^n = k$, we don't do that final move). So, Santa can go from $n$ to $k$ in at most $n+2$ rides, and we're done.