Competition · AMC preparation · step 4 of 4

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 (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 rule

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 } ∪ { (O-1)/3 : 3 ∣ (O-1) and (O-1)/3 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.

Every number the machine could have turned into an output O is either 2O, or — only when O-1 is a multiple of 3 and the share is odd — the number (O-1)/3.

▸ Why?

The machine has only two rules, so an input I that produced O came through one of them: the even rule O = I/2, which reverses to I = 2O, or the odd rule O = 3I+1, which reverses to I = (O-1)/3.

▸ Why?

The even rule halves the input, so to recover the input we do the opposite of halving and double the output: I = 2O.

Inverse operationsSubtraction undoes addition and division undoes multiplication — they reverse each other.

▸ Why?

The odd rule multiplies by 3 then adds 1, so to recover the input we undo those backwards: subtract 1, then divide by 3, giving I = (O-1)/3.

Inverse operationsSubtraction undoes addition and division undoes multiplication — they reverse each other.

▸ Why?

Trying both rules misses no predecessor, because every whole-number input is either even or odd, and those two cases split all possible inputs with no gaps and no overlap.

Even and odd (parity)A whole number is even when it splits into two equal whole groups (a factor of 2), else odd; odd×odd stays odd and even×anything is even.

▸ Why?

The doubled predecessor 2O is always a real even-rule input, while (O-1)/3 counts only when the subtraction leaves a multiple of 3 so the division comes out to a whole odd number.

▸ Why?

2O is a number split into two equal groups of O, and splitting into two equal groups is exactly what makes a number even, so 2O always fits the even rule that needs an even input.

Even and odd (parity)A whole number is even when it splits into two equal whole groups (a factor of 2), else odd; odd×odd stays odd and even×anything is even.

▸ Why?

Dividing by 3 undoes multiplying by 3, so (O-1)/3 lands on a whole input only when O-1 was itself 3 times a number, and that input must be odd for the odd rule to have used it.

Inverse operationsSubtraction undoes addition and division undoes multiplication — they reverse each other.

4.OA.B.4Work Backwards

2STEP 2

Step back from 1

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

predecessors(1) = {2}

3STEP 3

Step back from 2

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

predecessors(2) = {4}

4STEP 4

Step back from 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

Step back from 1 and 8

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

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

6STEP 6

Step back from 2 and 16

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

Take the final step back

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 starting values

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!

Invert the machine rule
Step back from 1
Step back from 2
Step back from 4
Step back from 1 and 8
Step back from 2 and 16
Take the final step back
Add the four starting values

A parent dashboard for the family lives at sensimlab.com.

Invert the machine rule

Step back from 1

Step back from 2

Step back from 4

Step back from 1 and 8

Step back from 2 and 16

Take the final step back

Add the four starting values

More like this