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 (Unrigorous)
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 
- 
.
Solution 2 (Bounding) - ike.chen
Clearly, there exists a construction for 
keystrokes, as shown above. Now, we show this is the smallest possible number of keystrokes.
If there are at most 
keystrokes, then the highest number we can reach is 
.
If there are 
keystrokes, then we consider the following cases:
- [x2]: This will clearly result in 
, which isn't desired.
- [x2], [+1]: The two largest numbers we can reach from this case are and 
, so we know this combination will not work.
- If we use at most 
repetitions of [x2], then our number will be at most 
, so all of these combinations are bad.
Hence, is the answer.
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. 
