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.
Best Answer
Look at what the operations $[+1]$ and $[\times 2]$ do to the binary expansion of a number:
Therefore, with a single key press:
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.