Problem:
A certain calculator has only two keys [+1] and [×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 [×2], it would display "20." Starting with the display "1," what is the fewest number of keystrokes you would need to reach "200"?
Answer Choices:
A. 8
B. 9
C. 10
D. 11
E. 12
Solution:
One way to solve the problem is to work backward, either dividing by 2 if the number is even or subtracting 1 if the number is odd.
200/2→100/2→50/2→25−1→24/2→12/2→6/2→3−1→2/2→1
So if you press [×2][+1][×2][×2][×2][+1][×2][×2][×2] or 9 keystrokes, you can reach "200" from "1."
To see that no sequence of eight keystrokes works, begin by noting that of the four possible sequences of two keystrokes, [×2][×2] produces the maximum result. Furthermore, [+1][×2] produces a result larger than either [×2][+1] or [+1][+1]. So the largest possible result of a sequence of eight keystrokes is "256," produced by either
[×2][×2][×2][×2][×2][×2][×2][×2]
or
[+1][×2][×2][×2][×2][×2][×2][×2].
The second largest result is "192," produced by
[×2][+1][×2][×2][×2][×2][×2][×2].
Thus no sequence of eight keystrokes produces a result of "200."
Answer: B.
The problems on this page are the property of the MAA's American Mathematics Competitions