2005 AMC 8 Problems/Problem 24
Problem
A certain calculator has only two keys [+1] and [x2]. 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 [x2], it would display "20." Starting with the display "1," what is the fewest number of keystrokes you would need to reach "200"?
Solution 1 (Now rigorous)
We can start at 
and work our way down to 
. We want to press the button that multiplies by 
the most, but since we are going down instead of up, we divide by instead. If we come across an odd number, then we will subtract that number by . Notice
,
,
,
,
,
,
,
,
.
,
,
,
,
,
,
,
,
.
Since we've reached , it's clear that the answer should be 
- 
. Because we only subtracted when we had to, this is optimal. ~Roy2020
Solution 2 (Binary)
We make two key observations. First, pressing [x2] appends a 
to the end of a number's binary representation. Second, pressing [x2] and then pressing [+1] appends to the end of a number's binary representation.
The base-ten number is represented as 
in binary. Therefore, the five s contribute 
button presses. Similarly, each of the three s each contribute button presses, although we do not count one of them as the calculator initially starts with the number 
Thus, the answer is 
See Also
| 2005 AMC 8 (Problems • Answer Key • Resources) | ||
| Preceded by Problem 23 |
Followed by Problem 25 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
| All AJHSME/AMC 8 Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
