AMC 8 · 2020 · #22
Grade 4 number-theorylogicProblem
When a positive integer N is fed into a machine, the output is a number calculated according to the rule shown below.
For example, starting with an input of N=7, the machine will output 3⋅7+1=22. Then if the output is repeatedly inserted into the machine five more times, the final output is 26.7→22→11→34→17→52→26When the same 6-step process is applied to a different starting value of N, the final output is 1. What is the sum of all such integers N?N→→→→→→1
Pick an answer.
AMC 8 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: A machine takes a positive integer $N$ and outputs $N/2$ if $N$ is even or $3N+1$ if $N$ is odd. The example $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ shows how the rule is applied $6$ times. We want every starting value $N$ such that after applying the machine $6$ times in a row, the result is $1$. Then we add up all such $N$.
Givens: Rule: if $N$ is even, output $N/2$; if $N$ is odd, output $3N+1$; Worked example: $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ (6 steps); For our problem, the chain $N \to \square \to \square \to \square \to \square \to \square \to 1$ ends at $1$ after $6$ steps; $N$ must be a positive integer; Answer choices: (A) $73$, (B) $74$, (C) $75$, (D) $82$, (E) $83$
Unknowns: The sum of every positive integer $N$ for which the 6-step process ends at $1$
Understand
Restated: A machine takes a positive integer $N$ and outputs $N/2$ if $N$ is even or $3N+1$ if $N$ is odd. The example $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ shows how the rule is applied $6$ times. We want every starting value $N$ such that after applying the machine $6$ times in a row, the result is $1$. Then we add up all such $N$.
Givens: Rule: if $N$ is even, output $N/2$; if $N$ is odd, output $3N+1$; Worked example: $7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26$ (6 steps); For our problem, the chain $N \to \square \to \square \to \square \to \square \to \square \to 1$ ends at $1$ after $6$ steps; $N$ must be a positive integer; Answer choices: (A) $73$, (B) $74$, (C) $75$, (D) $82$, (E) $83$
Plan
Primary tool: #11 Work Backwards
Secondary: #2 Make a Systematic List, #7 Identify Subproblems
The end-state ($1$) is given and the start ($N$) is unknown — that is the textbook trigger for Tool #11 (Work Backwards). To invert the machine: a number $O$ could have come from $2O$ (always a legal even predecessor since $2O$ is even) and possibly from $(O-1)/3$ (legal only when $O-1$ is divisible by $3$ AND the quotient is odd). At each backward step the number of candidates can branch, so Tool #2 (Systematic List) keeps the predecessor tree from missing or duplicating cases. Tool #7 (Identify Subproblems) makes "find every predecessor of $X$" a clean repeatable subroutine we apply $6$ times.
Execute — Answer: E
4.OA.B.4 Step 1 - Invert the machine.
- If the output is $O$, the input was either $2O$ (via the even rule, which is always valid because $2O$ is even) or $(O-1)/3$ via the odd rule.
- The odd-rule predecessor exists only when $O-1$ is divisible by $3$ and the resulting quotient is an odd positive integer.
💡 Asking "what could have produced this output?" is the inverse-operation idea; the divisibility-by-$3$ check is exactly the Grade 4 factors-and-multiples standard.
3.OA.A.3 Step 2 - Step back from $1$ once.
- Even-rule predecessor: $2 \times 1 = 2$ (valid).
- Odd-rule predecessor: $(1-1)/3 = 0$, not a positive odd integer (invalid).
- So after 5 steps the value must be $2$.
💡 Doubling $1$ and checking divisibility are basic Grade 3 multiplication / division facts.
3.OA.A.3 Step 3 - Step back from $2$.
- Even-rule: $2 \times 2 = 4$ (valid).
- Odd-rule: $(2-1)/3 = 1/3$, not an integer (invalid).
- So after 4 steps the value must be $4$.
💡 Same routine again — multiplication by $2$ and a divisibility check.
4.OA.B.4 Step 4 - Step back from $4$.
- Even-rule: $2 \times 4 = 8$ (valid).
- Odd-rule: $(4-1)/3 = 1$ (positive odd integer, valid).
- The tree now branches: after 3 steps the value is either $1$ or $8$.
💡 Once branching starts, we list candidates in a fixed order (smaller first) so nothing is missed — that is the Tool #2 systematic-list discipline.
4.OA.B.4 Step 5 - Step back from each of $\{1, 8\}$.
- From $1$ we already know the only predecessor is $2$.
- From $8$: even-rule gives $16$ (valid); odd-rule gives $(8-1)/3 = 7/3$ (not an integer, invalid).
- Combining, after 2 steps the value is $2$ or $16$.
💡 Each "find all predecessors of $X$" is its own little subproblem — Tool #7 — that we repeat for every node.
4.OA.B.4 Step 6 - Step back from each of $\{2, 16\}$.
- From $2$: only $4$.
- From $16$: even-rule gives $32$ (valid); odd-rule gives $(16-1)/3 = 5$ (positive odd integer, valid).
- After 1 step the value is in $\{4, 5, 32\}$.
💡 $16 - 1 = 15$ is divisible by $3$, so the odd branch fires — a Grade 4 factor / multiple check.
4.OA.A.3 Step 7 - Step back one more time to recover $N$ itself.
- From $4$: predecessors are $\{1, 8\}$ (already computed).
- From $5$: even-rule gives $10$ (valid); odd-rule gives $(5-1)/3 = 4/3$ (not an integer, invalid).
- From $32$: even-rule gives $64$ (valid); odd-rule gives $(32-1)/3 = 31/3$ (not an integer, invalid).
- So $N \in \{1, 8, 10, 64\}$.
💡 Tracking every branch over six backward steps is exactly the kind of multi-step whole-number problem Grade 4 students handle.
4.NBT.B.4 Step 8 Add the four valid starting values.
💡 Summing a short list of two-digit numbers is straightforward Grade 4 multi-digit addition.
4.OA.B.4 Invert the machine. If the output is $O$, the input was either $2O$ (via the eve 3.OA.A.3 Step back from $1$ once. Even-rule predecessor: $2 \times 1 = 2$ (valid). Odd-ru 3.OA.A.3 Step back from $2$. Even-rule: $2 \times 2 = 4$ (valid). Odd-rule: $(2-1)/3 = 1/ 4.OA.B.4 Step back from $4$. Even-rule: $2 \times 4 = 8$ (valid). Odd-rule: $(4-1)/3 = 1$ 4.OA.B.4 Step back from each of $\{1, 8\}$. From $1$ we already know the only predecessor 4.OA.B.4 Step back from each of $\{2, 16\}$. From $2$: only $4$. From $16$: even-rule giv 4.OA.A.3 Step back one more time to recover $N$ itself. From $4$: predecessors are ${1, 4.NBT.B.4 Add the four valid starting values. Review
Reasonableness: Spot-check $N = 10$: $10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$ — exactly $6$ steps to $1$. Spot-check $N = 64$: $64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$ — also $6$ steps. The other two, $N = 1$ and $N = 8$, walk down the $1 \to 4 \to 2 \to 1$ cycle in ways that also land at $1$ on step $6$. Four valid values summing to $83$ matches choice (E), and (E) is the only answer that is $\equiv 2 \pmod 3$ — a quick sanity flavor (each odd predecessor adds a multiple of $3$ plus $1$).
Alternative: Tool #1 (Draw a Diagram) supports this beautifully: draw a vertical tree with $1$ at the bottom and grow upward, branching whenever the odd rule also yields a valid predecessor. The leaves at depth $6$ are exactly $\{1, 8, 10, 64\}$. Some solvers prefer the diagram first and only then write Tool #2's list of leaves; the answer is the same.
CCSS standards used (min grade 4)
3.OA.A.3Solve multiplication and division word problems within 100 (Doubling small outputs ($2 \times 1$, $2 \times 2$) and checking whether $(O-1)/3$ is an integer for small $O$.)4.OA.A.3Solve multi-step word problems using four operations with whole numbers (Carrying the backward search through all $6$ steps while keeping the tree of intermediate values organized.)4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Deciding whether the odd-rule inverse $(O-1)/3$ is valid — i.e., whether $O-1$ is a multiple of $3$ — at each backward step.)4.NBT.B.4Fluently add and subtract multi-digit whole numbers (Computing the final sum $1 + 8 + 10 + 64 = 83$.)
⭐ This AMC 8 problem only needs Grade 4 multiplication, division-by-$3$ checks, and addition you already know — combined with the powerful 'work backwards' idea!
⭐ This AMC 8 problem only needs Grade 4 multiplication, division-by-$3$ checks, and addition you already know — combined with the powerful 'work backwards' idea!
More like this
Same archetype — closest grade level first.
