AMC 8 · 2020 · #22

Grade 4 number-theorylogic

Archetype Branching State Enumeration └ Sub-archetype Numeric Operation Tree

parityrecursive-sequencedivisibility-rulesfunction-evaluation tree-enumerationcaseworksystematic-enumeration ↑ Prerequisites: parityfunction-evaluation

📏 Long solution 💡 4 insights 📊 Diagram

📘 View easy version →

Problem

A machine takes a positive integer N and outputs

\frac{N}{2}

if N is even or 3N+1 if N is odd. The example 7 → 22 → 11 → 34 → 17 → 52 → 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.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

AMC 8 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Work Backwards

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 $\frac{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.

1STEP 1

Invert the machine: an output O came from 2O (always valid), or from $\frac{O-1}{3}$ only when that quotient is an odd positive integer.

predecessors(O) = { 2O } ∪ {

\frac{O-1}{3}

: 3 ∣ (O-1) and

\frac{O-1}{3}

is a positive odd integer }

2STEP 2

Predecessor of 1: only 2 (doubling 1; the odd branch gives 0, invalid).

predecessors(1) = {2}

3STEP 3

Predecessor of 2: only 4 (odd branch $\frac{2-1}{3}$ = $\frac{1}{3}$ is not an integer).

predecessors(2) = {4}

4STEP 4

Predecessors of 4: 1 and 8 — the odd branch $\frac{4-1}{3}$ = 1 now fires, splitting the tree.

predecessors(4) = {1, 8}

5STEP 5

Predecessors of {1, 8}: 2 and 16 (8's odd branch $\frac{7}{3}$ fails).

predecessors({1,8}) = {2, 16}

6STEP 6

Predecessors of {2, 16}: 4, 5, 32 — 16's odd branch $\frac{16-1}{3}$ = 5 is valid.

predecessors({2,16}) = {4, 5, 32}

7STEP 7

One more step back gives the starts 1, 8, 10, and 64; the odd branches of 5 and 32 both fail.

N ∈ {1, 8, 10, 64}

8STEP 8

Add the four starts 1 + 8 + 10 + 64 to get 83, choice (E).

1 + 8 + 10 + 64 = 83 → (E)

Answer

Spot-check N = 10: 10 → 5 → 16 → 8 → 4 → 2 → 1 — exactly 6 steps to 1. Spot-check N = 64: 64 → 32 → 16 → 8 → 4 → 2 → 1 — also 6 steps. The other two, N = 1 and N = 8, walk down the 1 → 4 → 2 → 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 ≡ 2 (mod 3) — a quick sanity flavor (each odd predecessor adds a multiple of 3 plus 1).

💡Key takeaway

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