binary representation shrinkage question

Question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times.

Prove:

• It is always possible to reduce the number to 1.
• Find the minimum $K$ in order to reduce the number to 1.

For example, for $n=13$, the operations can be $$13_{10}=1101_2\to(1+101)_2=110_2\to(1+1+0)_2=10_2\to(1+0)_2\to1$$

In this example, $K=3$.

Answer 1

Is it always possible? Yes. Adding the digits will make the number smaller, because the number of digits must be at most $\log_2(n)+1$, where $n$ is the number. Since these will be at most $1$, then the biggest the sum of the digits will be is $\log_2(n)+1$. But $\log_2(n)+1\leq n$. This holds for $n=2$ and an induction argument follows, I believe. As well the sum of the digits must be positive. So finite numbers will work their way down to one, eventually.

Answer 2

Finding the true minimum is probably difficult. If you have $n 1$'s, putting plus signs everywhere will reduce it to no more than $\log_2 n$, so in $k$ operations you can deal with $2\uparrow \uparrow (k-1) 1$'s with the $-1$ from needing a step from $10$ to $1$