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

5 Answers 5

55
$\begingroup$

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

  • $[\times 2]$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;
  • if the final digit is $0$, then $[+1]$ increases the number of $1$'s by one, but doesn't change the length;
  • if the final digit is $1$, then $[+1]$ 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$
4
  • $\begingroup$ Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation. $\endgroup$ Mar 18, 2019 at 1:34
  • 3
    $\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, 2019 at 2:13
  • 3
    $\begingroup$ @KayK.: Yes, but only because there are two ways of getting to 2. The rest is uniquely determined. $\endgroup$
    – TonyK
    Apr 4, 2019 at 16:05
  • $\begingroup$ We can argue that we will never do $\times2,+1,+1$ because that’s the same as the shorter $+1,\times 2$. Hence after the first step, we use a sequence of $\times2+$append binary 0, and $\times2,+1=$append binary 1. So apart from the first step, there is no choice $\endgroup$ Nov 28, 2021 at 16:29
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$
1
  • $\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, 2019 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$
2
  • $\begingroup$ you just exactly reproduces the binary 200, why should we think it is not optimal? $\endgroup$
    – dEmigOd
    Mar 17, 2019 at 19:54
  • $\begingroup$ @dEmigOd: I didn't prove that inserting the bits one by one with $\times2$ or $\times2+1$ is optimal. $\endgroup$
    – user65203
    Mar 17, 2019 at 19:57
4
$\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$
3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .