23
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you want the fewest steps to get to exactly $200$ or at least $200$? $\endgroup$ – John Douma Mar 17 at 19:37
  • 1
    $\begingroup$ @JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice. $\endgroup$ – TonyK Mar 17 at 19:43
  • $\begingroup$ @TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise. $\endgroup$ – John Douma Mar 17 at 19:44
  • 2
    $\begingroup$ @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$. $\endgroup$ – jeremy radcliff Mar 17 at 19:48
53
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation. $\endgroup$ – Jared Goguen Mar 18 at 1:34
  • 2
    $\begingroup$ 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$$ $\endgroup$ – Kay K. Mar 18 at 2:13
  • 1
    $\begingroup$ @KayK.: Yes, but only because there are two ways of getting to 2. The rest is uniquely determined. $\endgroup$ – TonyK Apr 4 at 16:05
10
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jacob1729 Mar 17 at 22:55
4
$\begingroup$

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.

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

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 $+$

$\endgroup$
1
$\begingroup$

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}$enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.