# Fewest steps to reach $200$ from $1$ using only $+1$ and $×2$

This is a problem from the AMC 8 (math contest):

A certain calculator has only two keys $$[+1]$$ and $$[\times 2]$$. When you press one of the keys, the calculator automatically displays the result. For instance, if the calculator originally displayed “$$9$$” and you pressed $$[+1]$$, it would display “$$10$$”. If you then pressed $$[\times 2]$$, it would display “$$20$$”. Starting with the display “$$1$$”, what is the fewest number of keystrokes you would need to reach “$$200$$”?

Intuitively I worked back from $$200$$, dividing by $$2$$ until I reached an odd number, subtracting $$1$$ when I did, etc..to reach the correct answer of $$9$$ steps.

However, I can't figure out how to convince myself beyond any doubt that it is the optimal solution. In other words, I can't prove it mathematically. The best I can come up with is that beyond the first step from $$1$$ to $$2$$, multiplication by $$2$$ is always going to yield a larger step than addition by $$1$$ and therefore I should take as many $$[\times 2]$$ steps as I can. This doesn't feel rigorous enough, though.

EDIT: Just to be clear, I am asking for a proof or at least more rigorous explanation of why this is the optimal solution.

• Do you want the fewest steps to get to exactly $200$ or at least $200$? – John Douma Mar 17 at 19:37
• @JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice. – TonyK Mar 17 at 19:43
• @TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise. – John Douma Mar 17 at 19:44
• @JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$. – jeremy radcliff Mar 17 at 19:48

Look at what the operations $$+$$ and $$\times$$ do to the binary expansion of a number:

• $$\times$$ appends a $$0$$, and increases the length by one, leaving the total number of $$1$$'s unchanged;
• if the final digit is $$0$$, then $$+$$ increases the number of $$1$$'s by one, but doesn't change the length;
• if the final digit is $$1$$, then $$+$$ doesn't increase the total number of $$1$$'s (it may in fact decrease it), and doesn't increase the total length by more than $$1$$.

Therefore, with a single key press:

• you can increase the length by one, but this won't increase the number of $$1$$'s;
• you can increase the number of $$1$$'s by one, but this won't increase the length.

The binary expansion of $$200$$ is $$200_{10}=11001000_2$$. This has three $$1$$'s, and a length of eight. Starting from $$1$$, we must increase the length by seven, and increase the number of $$1$$'s by two. So this requires at least nine steps.

• Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation. – Jared Goguen Mar 18 at 1:34
• There actually exist two ways of getting $200$ using nine steps. $$1+1+1\times2\times2\times2+1\times2\times2\times2=200\\ 1\times2+1\times2\times2\times2+1\times2\times2\times2=200$$ – Kay K. Mar 18 at 2:13
• @KayK.: Yes, but only because there are two ways of getting to 2. The rest is uniquely determined. – TonyK Apr 4 at 16:05

You can proceed by induction on $$n$$, showing that the quickest way to reach any even number $$2n$$ involves doubling on the last step, which is clearly true for the base case $$n=1$$ (where doubling and adding $$1$$ have a tomato-tomahto relationship).

Now if the last step to reach $$2n+2$$ isn't doubling, it can only be adding $$1$$ from $$2n+1$$. But $$2n+1$$ can only be reached by adding $$1$$ from $$2n$$, at which point the inductive hypothesis says the next previous number was $$n$$. But you can get from $$n$$ to $$2n+2$$ more quickly in two steps: add $$1$$, then double. So the last step in the quickest route to $$2n+2$$ is doubling from $$n+1$$.

• This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue. – jacob1729 Mar 17 at 22:55

Setting the display to binary base, $$[\times2]$$ inserts a $$0$$ to the right and $$[+1]$$ increments; if the rightmost digit is a zero, it just turns it to a $$1$$.

Using these rules you build a number of $$o$$ ones and $$z$$ zeroes in $$o-1+z$$ keystrokes, starting from $$1$$. This seems close to optimal.

• you just exactly reproduces the binary 200, why should we think it is not optimal? – dEmigOd Mar 17 at 19:54
• @dEmigOd: I didn't prove that inserting the bits one by one with $\times2$ or $\times2+1$ is optimal. – Yves Daoust Mar 17 at 19:57

I'll make a try

Since $$200=2^7+2^6+2^3$$ you will need at least $$8$$ steps to reach $$200$$ (since we start from $$1$$ and we get a number of the form $$2^a+...+2^l$$) so it remains to show that $$8$$ steps are not enough.

Maybe you could try to show that if there was a solution with $$8$$ steps then it would contain only one $$+1$$ which contradicts the fact that in $$200=2^7+2^6+2^3$$ we have two $$+$$

Working backwards, use the tree diagram and stop lagging branches (e.g. if $$\color{red}{99}$$ in step $$3$$ leads to $$1$$, then it takes one more operation than $$\color{red}{99}$$ in step $$2$$):

$$\hspace{3cm}$$