AMC 10 · 2012 · #24

Grade 8 number-theory

Archetype Branching State Enumeration └ Sub-archetype Rule-Governed Process Simulation

prime-factorizationdivisibility-rulesrecursive-sequenceinvariant-monovariant easier-related-problemidentify-subproblemssystematic-enumeration ↑ Prerequisites: prime-factorizationrecursive-sequence

📏 Long solution 💡 4 insights

Problem

A rule rewrites each prime power and is applied over and over. Count the starts whose outputs grow without bound.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Solve an Easier Related Problem

Testing 400 starting values by hand is hopeless, so shrink the problem until it is finite and mechanical (Tool #9). Two reductions do the shrinking. First, primes with exponent 1 vanish from the output, so only the part of N where every exponent is at least 2 matters (Tool #7). Second, the largest prime factor is forced strictly downward whenever it is 5 or more, so every sequence eventually lives inside the tiny world of numbers 2^a3^b (Tool #14, watching the extreme prime). Inside that world, name the exponents a and b (Tool #4): the rule becomes a two-number map, and two applications of it separate a from b completely, which pins down the exact growth thresholds. Finally, list the finitely many candidates below 400 and count (Tool #2). The thresholds must be proved in both directions -- above them the exponents provably explode, below them the exponents provably stay in a fixed box -- otherwise the count is only an upper estimate.

1STEP 1

Only the fat part of N matters

Only the repeated part of a number matters.

p ∥ N → f₁(N)=f₁ (N/p); N unbounded ⇔ R unbounded, R=Π_e_p ≥ 2p^e_p

2STEP 2

Big primes are pushed down and die

Large primes are pushed down and vanish.

P(n) ≥ 5 → P(f₁(n)) ＜ P(n), since q ∣ p+1, p odd → q ≤ (p+1)/2

3STEP 3

In the 2,3 world the rule is a two-number map

What is left is a plain two-number map.

f₁(2^a3^b) = 2²(b-1)^+ 3^(a-1)^+, T(a,b) = (2(b-1)^+, (a-1)^+), x^+=max(x,0)

4STEP 4

Two steps split the exponents, revealing the thresholds

Two steps reveal the growth thresholds.

T²(a,b)=(2(a-2)^+, (2b-3)^+); 2(a-2) ＞ a ⇔ a ≥ 5, 2b-3 ＞ b ⇔ b ≥ 4; T²(4,3)=(4,3)

5STEP 5

Multiples inherit unboundedness

Multiples inherit unbounded growth.

m ∣ n → f₁(m) ∣ f₁(n) → f_k(m) ∣ f_k(n) ∀ k

6STEP 6

Find the smallest unbounded starters

That leaves a short list of smallest starters.

f₁(7³)=8²=2⁶, f₁(2⁴5²)=3³ · 6=2 · 3⁴, f₁(2³5²)=54 → 16 → 27 → 16

7STEP 7

Count the multiples

Counting their multiples gives 18, choice (D).

12+4+1+1=18 → (D)

Answer

The criterion was proved in both directions, which is what makes the count exact rather than an estimate: above the thresholds the exponent map a↦ 2(a-2) or b↦ 2b-3 strictly increases, and below them the box a ≤ 4, b ≤ 3 is trapping because both maps are non-decreasing and fix a=4, b=3. The boundary cases confirm the thresholds are sharp: 16=2⁴ and 27=3³ sit exactly on the line and cycle forever, 16→ 27→ 16, while 32=2⁵ escapes at once, 32→ 81→ 64→ 243→ 256. The two exceptional starters also behave as claimed: 343→ 64 and 400→ 162→ 64, both landing on a power of 2 past the threshold, whereas the near miss 200=2³5² gives 200→ 54→ 16 and gets caught in the cycle. Independently re-adding the four disjoint families, 12+4+1+1, returns 18, matching choice (D). The distractors are exactly the traps of an incomplete sweep: missing both exceptional starters leaves 16, missing one leaves 17.

💡Key takeaway

Big primes shrink away until only 2s and 3s are left, and then the sequence blows up exactly when a term holds 2⁵ or 3⁴ -- so count multiples of 32, 81, 343, and 400: 12+4+1+1=18.

Only the fat part of N matters
Big primes are pushed down and die
In the 2,3 world the rule is a two-number map
Two steps split the exponents, revealing the thresholds
Multiples inherit unboundedness
Find the smallest unbounded starters
Count the multiples