AMC 8 · 2005 · #24

Grade 6 arithmetic

optimization-countingparityrecursive-sequencesystematic-enumeration optimization-countingtree-enumeration ↑ Prerequisites: paritysystematic-enumeration

📏 Long solution 💡 4 insights

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"?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: A calculator has only two keys: $[+1]$ (add $1$) and $[\times 2]$ (double). The display starts at $1$. What is the fewest number of keystrokes needed to make the display read $200$?

Givens: Starting display $= 1$; Available keys: $[+1]$ and $[\times 2]$; Target display $= 200$; Answer choices: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$

Unknowns: The minimum number of keystrokes that takes the display from $1$ to $200$

Understand

Restated: A calculator has only two keys: $[+1]$ (add $1$) and $[\times 2]$ (double). The display starts at $1$. What is the fewest number of keystrokes needed to make the display read $200$?

Givens: Starting display $= 1$; Available keys: $[+1]$ and $[\times 2]$; Target display $= 200$; Answer choices: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$

Plan

Primary tool: #11 Work Backwards

Secondary: #9 Solve an Easier Related Problem

Going forward from $1$, every keystroke gives two choices ($+1$ or $\times 2$), so the forward search branches wildly. Tool #11 (Work Backwards) flips it: the inverse of $[\times 2]$ is $[\div 2]$ (only legal when the number is even) and the inverse of $[+1]$ is $[-1]$. Going from $200$ down to $1$, $[\div 2]$ cuts the number in half but $[-1]$ only chips off $1$, so to be fastest we should divide whenever the number is even and subtract $1$ only when it is odd. That makes the backward path uniquely forced. Tool #9 (Easier Related Problem) handles the "why not fewer?" half: if we only had $[\times 2]$, $k$ keystrokes turn $1$ into $2^k$, and $2^7 = 128 < 200 < 256 = 2^8$, so $7$ keystrokes can't reach $200$ even with the strongest key. Combined with the forced backward count, $9$ is both achievable and minimum.

Execute — Answer: B

#11 Work Backwards 4.OA.B.4 Step 1

Set up the reverse rules.
The inverse of $[+1]$ is $[-1]$, and the inverse of $[\times 2]$ is $[\div 2]$.
Halving is much faster than subtracting $1$, so whenever the current number is even, use $[\div 2]$; if it is odd, $[\div 2]$ is illegal, so we must do one $[-1]$ to make it even.

$$\text{even } n \to n \div 2, \qquad \text{odd } n \to n - 1$$

💡 Even-vs-odd is the Grade 4 factor idea: a number is divisible by $2$ exactly when it is even, so parity decides which inverse key is allowed.

#11 Work Backwards 4.OA.C.5 Step 2

Apply the rules starting at $200$ and count keystrokes until you reach $1$.

$$\begin{array}{c|c|c} \text{Step} & \text{Value} & \text{Key used}\\\hline 0 & 200 & \text{start}\\ 1 & 100 & \div 2\\ 2 & 50 & \div 2\\ 3 & 25 & \div 2\\ 4 & 24 & -1\\ 5 & 12 & \div 2\\ 6 & 6 & \div 2\\ 7 & 3 & \div 2\\ 8 & 2 & -1\\ 9 & 1 & \div 2\\ \end{array}$$

💡 Generating each new value from the previous one by a fixed rule is Grade 4 "number pattern from a rule." $9$ rule-applications take us from $200$ to $1$.

#11 Work Backwards 4.OA.C.5 Step 3

Reverse the backward path to get a forward keystroke sequence from $1$ to $200$.
Every $[\div 2]$ flips back to $[\times 2]$ and every $[-1]$ flips back to $[+1]$.

$$1 \xrightarrow{\times 2} 2 \xrightarrow{+1} 3 \xrightarrow{\times 2} 6 \xrightarrow{\times 2} 12 \xrightarrow{\times 2} 24 \xrightarrow{+1} 25 \xrightarrow{\times 2} 50 \xrightarrow{\times 2} 100 \xrightarrow{\times 2} 200$$

💡 A backward path of length $9$ becomes a forward path of length $9$ — same arrows, reversed direction.

#9 Solve an Easier Related Problem 6.EE.A.1 Step 4

Show that no shorter path can work.
Consider the easier problem in which only $[\times 2]$ exists: after $k$ keystrokes, the display is $2^k$.
Since $2^7 = 128 < 200$, even seven of the strongest possible keystrokes can't reach $200$.
With the real (weaker on average) rules, fewer than $8$ keystrokes is also impossible; and an $8$-keystroke path would have to land exactly on $2^8 = 256$ if it used all $[\times 2]$, so it cannot hit $200$ either.
So the minimum is at least $9$, and our path of length $9$ achieves it.

$$2^7 = 128 < 200 < 256 = 2^8 \;\Rightarrow\; \text{at least } 8 \text{ doublings needed}$$

💡 Replacing the rules with the simpler "only doubling" rule gives a clean lower bound using Grade 6 whole-number exponents — and that bound, combined with parity, forces $9$.

#11 Work Backwards 4.OA.C.5 Step 5

Read off the answer.
A path of $9$ keystrokes exists and no shorter path does, so the minimum number of keystrokes is $9$.

$$\text{minimum keystrokes} = 9 \;\Rightarrow\; \textbf{(B)}$$

💡 Backward search plus a lower-bound check pins the answer between "can we?" and "can we do better?"

[1] #11 4.OA.B.4 Set up the reverse rules. The inverse of $[+1]$ is $[-1]$, and the inverse of $[

[2] #11 4.OA.C.5 Apply the rules starting at $200$ and count keystrokes until you reach $1$.

[3] #11 4.OA.C.5 Reverse the backward path to get a forward keystroke sequence from $1$ to $200$.

[4] #9 6.EE.A.1 Show that no shorter path can work. Consider the easier problem in which only $[

[5] #11 4.OA.C.5 Read off the answer. A path of $9$ keystrokes exists and no shorter path does, s

Review

Reasonableness: Spot-check by walking the forward path one keystroke at a time: $1, 2, 3, 6, 12, 24, 25, 50, 100, 200$. That is $9$ arrows after the starting $1$, so $9$ keystrokes, landing on $200$ as required. Also, the path uses $7$ presses of $[\times 2]$ and $2$ presses of $[+1]$, and the doublings alone multiply $1$ by $2^7 = 128$; the two $[+1]$ presses then nudge the value up to $200$, which is consistent with $200 = 128 + \text{(some adjustment)}$ produced by the timing of the two $[+1]$s. The matching answer choice is (B).

Alternative: Tool #5 (Look for a Pattern) using binary. Write $200$ in binary: $200 = 128 + 64 + 8 = 11001000_2$. Reading the binary digits left to right, each digit costs one $[\times 2]$ (a shift) plus an extra $[+1]$ when the digit is $1$. There are $8$ digits, so $8$ shifts, but the very first shift on the leading $1$ is replaced by the starting $1$ itself — that saves one $[\times 2]$. So total keystrokes $= (\text{digits} - 1) + (\text{number of } 1\text{'s} - 1) = 7 + 2 = 9$. Same answer (B), reached via the binary representation.

CCSS standards used (min grade 6)

4.OA.B.4 Find all factor pairs for a whole number; determine whether a given whole number is prime or composite (Using even/odd (divisibility by $2$) to decide whether the inverse key $[\div 2]$ is legal at each backward step.)
4.OA.C.5 Generate a number or shape pattern that follows a given rule (Generating the backward sequence $200, 100, 50, 25, 24, 12, 6, 3, 2, 1$ by applying the rule "halve if even, else subtract $1$" at each step.)
6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (Comparing $200$ to $2^7 = 128$ and $2^8 = 256$ to prove no $7$- or $8$-keystroke sequence can reach $200$.)

⭐ Running the calculator in reverse turns this AMC 8 problem into a Grade 4 pattern rule ("halve if even, else minus $1$") — and a Grade 6 powers-of-$2$ check confirms $9$ keystrokes really is the fewest.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 6)

More like this