← Sensim Lab Sensim Math

AMC 8 · 2020 · #22

Grade 4 number-theorylogic
Archetype Branching State Enumeration
parityrecursive-sequencedivisibility-rulesfunction-evaluation tree-enumerationcaseworksystematic-enumeration ↑ Prerequisites: parityfunction-evaluation
📏 Long solution 💡 4 insights 📊 Diagram
📘 View easy version →

Problem

When a positive integer NN 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,N=7, the machine will output 3⋅7+1=22.3 \cdot 7 +1 = 22. Then if the output is repeatedly inserted into the machine five more times, the final output is 26.26.7→22→11→34→17→52→267 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26When the same 66-step process is applied to a different starting value of N,N, the final output is 1.1. What is the sum of all such integers N?N?N→→→→→→1N \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to 1
(A) 73(B) 74(C) 75(D) 82(E) 83\textbf{(A) }73 \qquad \textbf{(B) }74 \qquad \textbf{(C) }75 \qquad \textbf{(D) }82 \qquad \textbf{(E) }83

Pick an answer.

(A)
73
(B)
74
(C)
75
(D)
82
(E)
83
View mode:

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

#11 Work Backwards 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.
$$\text{predecessors}(O) = \{\,2O\,\} \cup \{\,(O-1)/3 : 3 \mid (O-1) \text{ and } (O-1)/3 \text{ is a positive odd 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.

#11 Work Backwards 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$.
$$\text{predecessors}(1) = \{2\}$$

💡 Doubling $1$ and checking divisibility are basic Grade 3 multiplication / division facts.

#11 Work Backwards 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$.
$$\text{predecessors}(2) = \{4\}$$

💡 Same routine again — multiplication by $2$ and a divisibility check.

#2 Make a Systematic List 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$.
$$\text{predecessors}(4) = \{1,\,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.

#7 Identify Subproblems 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$.
$$\text{predecessors}(\{1,8\}) = \{2,\,16\}$$

💡 Each "find all predecessors of $X$" is its own little subproblem — Tool #7 — that we repeat for every node.

#2 Make a Systematic List 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\}$.
$$\text{predecessors}(\{2,16\}) = \{4,\,5,\,32\}$$

💡 $16 - 1 = 15$ is divisible by $3$, so the odd branch fires — a Grade 4 factor / multiple check.

#2 Make a Systematic List 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\}$.
$$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.

#11 Work Backwards 4.NBT.B.4 Step 8

Add the four valid starting values.

$$1 + 8 + 10 + 64 = 83 \;\Rightarrow\; \textbf{(E)}$$

💡 Summing a short list of two-digit numbers is straightforward Grade 4 multi-digit addition.

[1] #11 4.OA.B.4 Invert the machine. If the output is $O$, the input was either $2O$ (via the eve
[2] #11 3.OA.A.3 Step back from $1$ once. Even-rule predecessor: $2 \times 1 = 2$ (valid). Odd-ru
[3] #11 3.OA.A.3 Step back from $2$. Even-rule: $2 \times 2 = 4$ (valid). Odd-rule: $(2-1)/3 = 1/
[4] #2 4.OA.B.4 Step back from $4$. Even-rule: $2 \times 4 = 8$ (valid). Odd-rule: $(4-1)/3 = 1$
[5] #7 4.OA.B.4 Step back from each of $\{1, 8\}$. From $1$ we already know the only predecessor
[6] #2 4.OA.B.4 Step back from each of $\{2, 16\}$. From $2$: only $4$. From $16$: even-rule giv
[7] #2 4.OA.A.3 Step back one more time to recover $N$ itself. From $4$: predecessors are ${1,
[8] #11 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.3 Solve 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.3 Solve 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.4 Find 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.4 Fluently 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.