Problem 24 · 2005 AMC 8
Hard
Logic & Word Problems
reverse-from-target
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"?
Show answer
Answer: B — 9 keystrokes.
Show hints
Hint 1 of 2
Going forward from 1 you'd face two choices at every step — a branching mess. Going backward from 200, each step is forced, so there's nothing to guess.
Still stuck? Show hint 2 →
Hint 2 of 2
Reverse the keys: undoing ×2 is ÷2, undoing +1 is −1. At an even number, halving is the bigger leap toward 1, so prefer it; only subtract 1 when the number is odd and you have no choice.
Show solution
Approach: run the keys in reverse from 200 to 1
- Work down from the target. Halve whenever you can (the powerful move), and subtract 1 only when forced by an odd number:
- 200 → 100 → 50 → 25 (odd, so −1) → 24 → 12 → 6 → 3 (odd, so −1) → 2 → 1.
- That's 9 steps, and each reverse step is one forward keystroke.
- Why backward is optimal here: at an even number, halving always reaches 1 in fewer moves than peeling off 1's, and at an odd number you're forced to subtract 1 anyway — so this greedy reverse path can't be beaten. Working from the goal is the go-to trick whenever the forward direction branches but the backward one is determined.
Mark:
· log in to save