Problem 22 · 2020 AMC 8
Hard
Number Theory
work-backwardcasework
When a positive integer N is fed into a machine, the output is calculated by the rule: if N is even, output N/2; if N is odd, output 3N + 1. Example: 7 → 22 → 11 → 34 → 17 → 52 → 26. When the same 6-step process is applied to a different starting N, the final output is 1. What is the sum of all such integers N?
Show answer
Answer: E — Sum is 83.
Show hints
Hint 1 of 2
Going forward you'd have to guess starting values and test each one. Flip the arrows: start at the known endpoint 1 and ask ‘what could come right before this?’ six times.
Still stuck? Show hint 2 →
Hint 2 of 2
Reverse each rule. A value k can come from 2k (undo the halving — always works) or from (k−1)/3 (undo the 3n+1 — but only when that's an odd whole number). Build the tree of possibilities 6 levels back from 1.
Show solution
Approach: invert the machine and grow the tree backward from 1
- Forward the rule is: even → halve, odd → 3n+1. Run it backward from a value k: a predecessor is 2k (always valid, since doubling lands on an even number that halves back to k), and also (k−1)/3 — but only if that comes out an odd whole number (so the odd rule really applied).
- Grow the tree 6 steps back from 1: 1 → {2} → {4} → {8, 1} → {16, 2} → {32, 5, 4} → {64, 10, 8, 1}. (At each value, double it, and divide-minus-one-by-three when that's an odd integer.)
- The four level-6 values are the starting numbers; their sum is 64 + 10 + 8 + 1 = 83.
- Why this transfers: when a process is easy to run forward but you're told the output, work backward and invert each rule — the branches that fail the ‘is it a valid integer / right parity’ check simply die off, pruning the tree to a small set you can sum.
Mark:
· log in to save