AMC 10 · 2015 · #18

Grade 8 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Answer-Choice Plug-In
prime-factorizationlinear-diophantineparity work-backwardsextreme-principle ↑ Prerequisites: prime-factorizationprime-numbers
📏 Long solution 💡 3 insights
Problem
A function adds up all the prime factors of a composite number, repeats included. Identify the set of values it produces.

Pick an answer.

(A)
the set of positive integers
(B)
the set of composite positive integers
(C)
the set of even positive integers
(D)
the set of integers greater than 3
(E)
the set of integers greater than 4
How to solve
Strategy Work Backwards

Because the choices are overlapping sets, the goal is a set equality, and a set equality needs both directions proved. Tool #15 (Organize Information in More Ways) supplies the reframing that makes both directions reachable: instead of asking what r does to each composite n, ask which integers are a sum of two or more primes. Tool #14 (Extreme Principle) then settles the first direction by pinning the smallest possible sum, which fences the outputs from below. Tool #11 (Work Backwards) settles the second direction the other way round: start from a target value and build a composite number that produces it, using Tool #4 (Introduce a Variable) to write one formula that covers all even targets and one that covers all odd targets. Only after the exact set is known does Tool #3 (Eliminate Possibilities) get used — and then it tests each choice for a missing element in either direction, not just for a lucky match.

1STEP 1

Turn r into a sum of primes

The function is a plain sum of primes.

n = p₁ p₂ … p_k (k ≥ 2) ⟹ r(n) = p₁ + p₂ + … + p_k
2STEP 2

Nothing below 4 can appear

Nothing below 4 can ever appear.

r(n) = p₁ + … + p_k ≥ 2 + … + 2_k ≥ 2 ≥ 4, r(4) = 2 + 2 = 4
3STEP 3

Reach every even target

Powers of two reach every even target.

m = 2a, a ≥ 2: n = 2^a, r(2^a) = 2 + … + 2_a = 2a = m
4STEP 4

Reach every odd target

One extra factor reaches every odd one.

m = 3 + 2b, b ≥ 1: n = 3 · 2^b, r(3 · 2^b) = 3 + 2 + … + 2_b = 3 + 2b = m
5STEP 5

Close both inclusions

Both inclusions close.

range(r) ⊆ T and T ⊆ range(r) ⟹ range(r) = T = {4, 5, 6, 7, …}
6STEP 6

Test the five sets both ways

That names one set exactly, choice (D).

1 ∉ range → (A); 5 ∈ range → (B), (C); 4 ∈ range → (E); range = {m : m ＞ 3} → (D)
Answer
the set of integers greater than 3
Build the outputs by hand and check the bottom of the list is unbroken: r(4) = 4, r(6) = 5, r(8) = 6, r(10) = 7, r(15) = 8, r(14) = 9, r(21) = 10, r(28) = 11, r(50) = 12 — every integer from 4 up appears, with no value below 4 produced by any composite. The two constructions agree with these samples: 6 = r(2³) = r(8) and 9 = r(3 · 2³) = r(24), and indeed 24 = 2 · 2 · 2 · 3 sums to 9. The nesting of the choices is handled honestly rather than by luck: (E) ⊂ (D) differ only at 4, and 4 is an output, so (D) beats (E) on exactly the point where they disagree; (B) and (C) are both broken by the single output 5, which is neither composite nor even.
💡Key takeaway

A composite number is at least two primes multiplied together, so the smallest sum is 2 + 2 = 4; after that, stacking twos hits every even total and one extra 3 hits every odd one, so every integer above 3 shows up and nothing below it does.

  • Turn r into a sum of primes
  • Nothing below 4 can appear
  • Reach every even target
  • Reach every odd target
  • Close both inclusions
  • Test the five sets both ways

More like this

Same archetype — closest grade level first.